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

• #6947 P.H. senior tag #89874944 #6934

  Új Válasz 2013-04-16 20:57:27 #6947

  Ú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

  Privát üzenet küldése

  

  P.H.

  senior tag

  válasz #89874944 #6934 üzenetére

  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).

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