Programozás‎ > ‎Feladatok‎ > ‎Utazó ügynök‎ > ‎

Megoldás

Algoritmusok

Ha kevés város van, akkor egyszerűen végignézzük az összes lehetséges permutációt (a kör miatt elég (n-1)! esetet nézni, mert feltehetjük, hogy 1-ből indulunk és 1-be érkezünk).

Nagy n-re ez nem megy. Ilyenkor megpróbálhatunk egy tetszőleges körútból kiindulni, és azt javítgatni. A legegyszerűbb javítás, ha kiválasztunk az út során egy ...->A -> B->... és egy ...->C->D->... párt, és megnézzük, hogy az ...->A->C->...->B->D->... körút rövidebb-e. (Itt az eredetihez képest a B és C közötti szakaszt fordított sorrendben járjuk be.)

Amíg találunk ilyen javítást, addig ismételgetjük. (Geometriai megfogalmazás: megszüntetjük a metsző szakaszpárokat. Ez nem teljesxen ekvivalens a fenti gondolatmenettel, de mutatja, hogy mi lehetett a módszer motivációja.)

Kódok

Nyers erő

Fehér Balázs (java): TSP.java

Közelítő megoldások

Forrás Bence (java): UtazóÜgynök.java
Hornák Bence (C++): hb_utazougynok.cpp
Tegzes Tamás (pascal): tt_ugynok.pas