Új hozzászólás Aktív témák

• bambano titán

  #6952

  #6947 P.H.

  2013-04-16 21:19:27

  Új Válasz

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  

  bambano

  titán

  #6947 P.H.

  #6947 P.H.

  A gyűrű azt jelenti, hogy a lehető legrövidebb a 2D-távolság az összekötött pontok között, azaz az összekötések összhossza minimális, ezzel visszavezetted a TSP (Traveling Salesman Problem) szituációra a kérdést, ez pedig NP-teljes. Letehetsz róla, hogy egyszerűbb algoritmust találsz a pontos megoldásra, mint a TSP, ez a bonyolultságelmélet szépsége, a visszavezethetőség. NP-teljes problémára pedig n pont esetén - ahogy cucka és Jester01 is írta - n! nagyságrendű (azaz nem polinomiális) műveletigényű általános megoldás van. Ha találsz egyet, ami polinomiális lesz, akkor esély van a matematikai Nobel-díjra és pár egyéb nagy összegű pénzdíj elnyerésére is.

  Persze lehet keresni részben másképp is megoldást, nem kell végigpróbálni az összes n! megoldást - a metszés jó ötlet -, de akkor is kiszámíthatatlan lesz az időigény (pl. felveszel 100 pontot, arra x idő alatt talál megoldást a programod; elveszel belőle 20-at, azaz 80 marad és 3x-osára nő az időigénye).

  a tsp-re pont nem vezette vissza, mert a tsp arról szól, hogy adott gráfot kell bejárni, ez meg arról, hogy hogyan építs ponthalmazból gráfot. a tsp-nek nem része az útépítés, szemben pl. ezzel.

Új hozzászólás Aktív témák