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

• #6939 skoda12 aktív tag #89874944 #6934

  Új Válasz 2013-04-16 19:51:57 #6939

  Ú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

  

  skoda12

  aktív tag

  LOGOUT blog

  válasz #89874944 #6934 üzenetére

  Hello.

  Regen csinaltam hasonlot. Gyakorlatilag oramutato jarasaval megegyezo (vagy azzal ellentetes) iranyban kell sorba rendezni a pontokat. Az otlet a kovetkezo. Van P1, P2, ..., PN pontod. Kiszamitod a sulypontjukat, legyen ez S. Innentol kezdve ugy kezeled S-t mintha, az origo lenne, amin atmegy az x es y tengely. Minden P-re kiszamitod az x tengely es SP vector altal bezart szoget, legyen ez alfa es el is tarolod mondjuk a P pontban. Ezutan P-ket mar az igy kiszamolt szog alapjan sorbarendezed es kesz is vagy.

• #6935 Jester01 veterán #89874944 #6934

  Új Válasz 2013-04-16 17:08:07 #6935

  Ú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

  

  Jester01

  veterán

  válasz #89874944 #6934 üzenetére

  A favágó módszer (az összes lehetőség végigpróbálása) működik ha a pontok száma nem túl nagy

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