Utazó ügynök probléma
Utazó ügynök probléma (angl.Travellingsalesmanproblem, TSP) (eladó - ügynök) - az egyik legismertebb kombinatorikus optimalizálási probléma az, hogy megtalálják a legjövedelmezőbb út átmenő város legalább egyszer majd visszatér az eredeti város. Az összefüggésben a probléma azt jelzi, a nyereségesség a útvonal kritériumok (legrövidebb, legolcsóbb, meghatározott kritériumok, és hasonlók), és a megfelelő távolság mátrixot, költségeket és hasonlókat. Általános szabály, hogy azt jelzi, hogy az útvonal áthalad minden városban csak egyszer - ebben az esetben a kiválasztás között Hamilton-kör.
Számos különleges esetekben az általános megfogalmazása a probléma, különösen a geometriai utazó ügynök probléma (más néven egy sík vagy euklideszi amikor a távolság mátrix tükrözi a pontok közötti távolság a gépen), metrikus utazó ügynök probléma (ha a mátrix értékek a háromszög-egyenlőtlenség), szimmetrikus és aszimmetrikus utazó ügynök probléma. Van is egy általánosítása a problémát, az úgynevezett általános utazó ügynök probléma.
Optimization megfogalmazása a probléma osztályába tartozik NP-nehéz probléma, de mint a legtöbb különleges esetekben. Verzió «döntési probléma» (azaz, amelyben a kérdés az, hogy van egy út nem hosszabb, mint egy előre meghatározott érték k) osztályába tartozik NP-teljes problémák. Utazó ügynök probléma egyik transvychislitelnyh: már viszonylag kis számú városok (66 vagy több), akkor nem lehet megoldani nyers erővel bármilyen elméletileg elképzelhető változatait számítógépek kevesebb, mint néhány milliárd év.
A sine qua non, és az egyetlen oka az utazó ügynök probléma az, hogy megtaláljuk a leginkább jövedelmező módon. Ehhez keresse meg és tartalmazza az összes lehetséges módon bármelyik változatok módon, hogy megoldást találjanak. Ha még nem jött el egészen a kiválasztott változat a megoldást, nem állíthatja, hogy a talált megoldás a legelőnyösebb. Mi hitelesítési megoldások? - keresi a hibát ítélet vagy levezetését az eredményt egy ismert jobbra. A második lehetőség átmenetileg csökkent, mivel nincs gyakorlati értelme a probléma megoldásában, ha már van egy határozat (viszont a használata korábban tett a helyes döntés a része a már meglévő probléma - a módját, hogy csökkentsék a határozat). Ennek részeként a munka nem célja, hogy összehasonlítsuk a különböző módszerek és megoldások megoldások, így feltételezzük, hogy a recenzens is úgy véli, a választott útvonal optimális megoldás, és ellenőrzi, hogy azok helyességét. Mit kell tenni, hogy ellenőrizze? - ismételje meg a munkát a határozat teljes keresést hibák minden egyes szakaszában a döntést. Ha hibát talál, a vizsgáztató folytatni kell a folyamat megoldást találni jövedelmezőbb útvonalakra. Így azt látjuk, hogy az ellenőrzési megoldások utazó ügynök probléma egyenlő vagy nagyobb, mint maga a határozat.
Képviselet, mint egy grafikont.
Szimmetrikus problémát a négy városban.
Annak érdekében, hogy a matematikai eszközök, hogy megoldja a problémát, meg kell mutatni formájában matematikai modell segítségével. utazó ügynök probléma leírható, mint egy modell a grafikonon, azaz a csúcsok és az élek között. Így, a csúcsokat az egyes városok és a bordák (i, j) közötti i és j csomópontok - kétirányú kommunikáció a két város között. Minden éle (i, j)> = 0 lehet hasonlítani útvonalon nyereségesség kritériumokat, amely lehet érteni, mint például, a távolságot a városok, utazási idő vagy a költség. Útszakaszokat (Hamilton is) nevezik az útvonalat, mint egy grafikon, amely magában foglalja a egyszer minden csúcsa a grafikon. A kihívás az, hogy megtalálják a legrövidebb utat.
Annak érdekében, hogy egyszerűsítse a feladat, és garantálja a létezését az útvonal általában úgy, hogy a gráf modellje a probléma teljesen kötve, hogy van, hogy van egy él bármely két csúcsot. Azokban az esetekben, ahol az egyes városok, nincs üzenet, ezt el lehet érni megadásával a bordák maximális hossza. Mivel a nagy hosszúsága él soha nem lesz, hogy az optimális útvonalat, ha létezik.
Attól függően, hogy a kritérium érték leképezve útvonalon nyereségesség élek, megkülönböztetni a különböző kiviteli alakok a probléma, a legfontosabb az, amely szimmetrikus, és problémát metrikus.
Példa a megoldására utazó ügynök probléma python egy adott gráf (ábra. 3.2).
2. kódrészlet egy forgatókönyvet a feladat.
Ez a szkript a legtöbb „nyereséges” módon a felső 1 a tetejére 4.
