AlgoritmusokHa 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ódokNyers erőFehér Balázs (java): TSP.java Közelítő megoldások
|