Problém obchodního cestujícího: Porovnání verzí
Smazaný obsah Přidaný obsah
m {{Commonscat}}; kosmetické úpravy |
značka: revertováno |
||
Řádek 25:
Rozhodovací verze problému je [[NP-úplnost|NP-úplná]], tedy existuje Nedeterministický Turingův stroj (nedeterministický algoritmus), který vydá jak odpověď ANO, tak odpověď NE vždy po maximálně „polynomiálním počtu kroků“.
Peter, pozn. - Obavam se, ze na to jdete spatne. Nejkratsi cesta mezi body A-B nastane, kdyz vzdalenosti mezi vybranym bodem C, AC a CB bude nejkratsi. Nemusite projit vsechny cesty, staci z kazde pulky vybrat tu nejkratsi. A tak postupujete dal. Musite najit trojice mist, ktere maji nejkratsi vzdalenost. Seradit podle vzdalenosti a pak spojovat do vetsich celku. Velice to pripomina spojovanei serazenych seznamu, sortedlist-merging-sort
== Příklad nejkratší okružní cesty ==
| |||