Utazó ügynök probléma Online
Az utazó ügynök probléma kialakulásának az optimális útvonalat elkerülő n városok kell választani a legjobbat az (n-1)! lehetőségek az időbeli feltétel, költség vagy az útvonal hossza. Ez a probléma összefügg a meghatározása a Hamilton-kör minimális hosszúságú. Ezekben az esetekben a készlet minden lehetséges megoldásokat kell biztosítani a formájában egy fa - összefüggő gráf nem tartalmazó ciklus vagy hurkok. A gyökér a fa egyesíti az összes választási lehetőséget, és a tetején a fa - egy részhalmaza részben rendezett megoldásokat.
Utasításokat. Válassza ki a méretet a mátrix (a városok száma). A kapott oldatot tárolja az interneten Word és Excel fájlok (lásd. Például az utazó ügynök probléma megoldás).
Matematikai modellje az utazó ügynök probléma
A formulázott probléma - a probléma egész szám. Hagyja hij = 1, ha az utas mozog az i-edik város a j-edik és hij = 0. Ha ez nem így van.
Formálisan, bemutatjuk a (n + 1) város található, ugyanazon a helyen, és az első város, azaz a a távolság a (n + 1) a bármely más város, az elsőtől különböző, egyenlő a távolság az első város. Ebben az esetben, ha az első, a város csak akkor megy ki a (n + 1), a város csak akkor jöhet.
Bemutatjuk további integer egyenlő a több látogató a város az úton. u1 = 0, un + 1 = n. Annak érdekében, hogy elkerüljék a zárt pályák, hogy ki az első, a város és visszatér a (n + 1), bemutatjuk további kényszerek összekötő változók xij és változók ui. (Ui nemnegatív egészek).
ui -uj + nxij ≤ n-1, J = 2..n + 1, i = 1..n, i ≠ j, ahol i = 1, j ≠ n + 1
0≤ ui ≤ n, Xin + 1 = xi1. i = 2..n
- elágazás és korlátozás módszer (algoritmus vagy csak kis subcycles kivétel). Példa megoldások szétválasztás és korlátozás;
- Magyar módszer. Példa megoldások magyar módszer.
Példa. Minden példában, X0 = (1,2) van kiválasztva, mint a primer útvonal, (2,3), (3,4), (4,5), (5,6), (6,1). A minősítés az ehhez az útvonalon egyenlő F (X0) = 43 + 65 + 73 + 22 + 8 + 80 = 291. Annak meghatározására, az alsó határa a redukciós műveletet alkalmazunk. amelyre minden sorban a D mátrix minimális eleme: di = min (j) dij
Összeg vezetés állandók meghatározza az alsó határát H = Σdi + Σdj = 9 + 52 + 13 + 17 + 8 + 10 + 0 + 20 + 0 + 5 + 0 + 0 = 134. Az elemek dij mátrix megfelelnek a távolság i pont-pont j. Az útvonal által meghatározott expressziós: F (Mk) = Σdij. Minden sor és oszlop tartalmazza az útvonal csak egyszer az elem dij.
Ezután, a későbbi iterációk, az ág borda meghatározzuk. Minden sok útvonal ezen bordák törött két részhalmaza (i, j) és (i * j *).