Programozás‎ > ‎Feladatok‎ > ‎

Utazó ügynök

Egy utazó ügynöknek N városba kell ellátogatnia, ahol értékesíti portékáit. Ismerjük a városok (euklideszi) koordinátái. Tervezzük meg a lehetséges legrövidebb útvonalat, amely során az ügynök minden városba eljut, majd visszatér a kiindulási városába!

Feladat

Írjunk programot, ami beolvassa a városok koordinátáit, majd kiír egy (kvázi) optimális megoldást.

Bemenet

A bemenet első sora a városok N számát tartalmazza, majd N sorban egy-egy város két koordinátája következik. A koordináták euklideszi geometriában értendők, eltekintünk a gömbi geometria távolságfüggvényének használatától.

Kimenet

Az első sorba az általunk talált megoldás hosszát kell írni. Ezután a városok indexének egy permutációja következik, az optimálisnak gondolt körüljárási sorrend szerint.

Példa

Bemenet  Kimenet
5
0 0 
2 0 
2 2 
1 2
0 2
8
1 2 3 4 5

Tesztadatok

Az alábbi linken egy olyan adatbázisból választhatunk teszteseteket, amelyet sokan használnak a különböző TSP-implementációk hatékonyságának mérésére. A fájlokat picit át kell formázni.
(TSP = Travelling Salesman = Utazó ügynök)

http://www.math.uwaterloo.ca/tsp/world/countries.html

Címkék

A feladat forrása: közismert feladat
Algoritmusok: összes eset generálása, optimalizáció: mohó algoritmussal készített megoldás lokális javítása