Rezolvarea problemei vânzătorului ambulant. Lista literaturii folosite. Plan general pentru rezolvarea problemei vânzătorului ambulant
X 0 = (1,2);(2,3);(3,4);(4,5);(5,1)
Atunci F(X 0) = 90 + 40 + 60 + 50 + 20 = 260
Pentru a determina limita inferioară a mulțimii, folosim operatie de reducere sau reducerea matricei rând cu rând, pentru care este necesar să se găsească elementul minim în fiecare rând al matricei D.
d i = min(j) d ij
| eu j | 1 | 2 | 3 | 4 | 5 | d i |
| 1 | M | 90 | 80 | 40 | 100 | 40 |
| 2 | 60 | M | 40 | 50 | 70 | 40 |
| 3 | 50 | 30 | M | 60 | 20 | 20 |
| 4 | 10 | 70 | 20 | M | 50 | 10 |
| 5 | 20 | 40 | 50 | 20 | M | 20 |
Apoi scădem d i din elementele rândului în cauză. În acest sens, în matricea nou obținută va exista cel puțin un zero pe fiecare rând.
| eu j | 1 | 2 | 3 | 4 | 5 |
| 1 | M | 50 | 40 | 0 | 60 |
| 2 | 20 | M | 0 | 10 | 30 |
| 3 | 30 | 10 | M | 40 | 0 |
| 4 | 0 | 60 | 10 | M | 40 |
| 5 | 0 | 20 | 30 | 0 | M |
Efectuăm aceeași operație de reducere de-a lungul coloanelor, pentru care găsim elementul minim în fiecare coloană:
d j = min(i) d ij
| eu j | 1 | 2 | 3 | 4 | 5 |
| 1 | M | 50 | 40 | 0 | 60 |
| 2 | 20 | M | 0 | 10 | 30 |
| 3 | 30 | 10 | M | 40 | 0 |
| 4 | 0 | 60 | 10 | M | 40 |
| 5 | 0 | 20 | 30 | 0 | M |
| d j | 0 | 10 | 0 | 0 | 0 |
După scăderea elementelor minime, obținem o matrice complet redusă, unde valorile d i și d j se numesc constante de turnare.
| eu j | 1 | 2 | 3 | 4 | 5 |
| 1 | M | 40 | 40 | 0 | 60 |
| 2 | 20 | M | 0 | 10 | 30 |
| 3 | 30 | 0 | M | 40 | 0 |
| 4 | 0 | 50 | 10 | M | 40 |
| 5 | 0 | 10 | 30 | 0 | M |
Suma constantelor de reducere determină limita inferioară a lui H:
H = ∑d i + ∑d j
H = 40+40+20+10+20+0+10+0+0+0 = 140
Elementele matricei d ij corespund distanței de la punctul i la punctul j.
Deoarece există n orașe în matrice, atunci D este o matrice nxn cu elemente nenegative d ij >=0
Fiecare rută valabilă reprezintă un ciclu în care vânzătorul ambulant vizitează orașul o singură dată și se întoarce în orașul inițial.
Lungimea traseului este determinată de expresia:
F(M k) = ∑d ij
Mai mult, fiecare rând și coloană este inclusă în traseu o singură dată cu elementul d ij .
Pasul 1.
Determinarea marginii de ramificare
| eu j | 1 | 2 | 3 | 4 | 5 | d i |
| 1 | M | 40 | 40 | 0(40) | 60 | 40 |
| 2 | 20 | M | 0(20) | 10 | 30 | 10 |
| 3 | 30 | 0(10) | M | 40 | 0(30) | 0 |
| 4 | 0(10) | 50 | 10 | M | 40 | 10 |
| 5 | 0(0) | 10 | 30 | 0(0) | M | 0 |
| d j | 0 | 10 | 10 | 0 | 30 | 0 |
d(1,4) = 40 + 0 = 40; d(2,3) = 10 + 10 = 20; d(3,2) = 0 + 10 = 10; d(3,5) = 0 + 30 = 30; d(4,1) = 10 + 0 = 10; d(5,1) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Cea mai mare sumă de constante de reducere este (40 + 0) = 40 pentru muchia (1,4), prin urmare, mulțimea este împărțită în două submulți (1,4) și (1*,4*).
H(1*,4*) = 140 + 40 = 180
Eliminam muchia (1,4) prin inlocuirea elementului d 14 = 0 cu M, dupa care efectuam urmatoarea reducere a matricei de distanta pentru submultimea rezultata (1*,4*), ca rezultat obtinem o matrice redusă.
| eu j | 1 | 2 | 3 | 4 | 5 | d i |
| 1 | M | 40 | 40 | M | 60 | 40 |
| 2 | 20 | M | 0 | 10 | 30 | 0 |
| 3 | 30 | 0 | M | 40 | 0 | 0 |
| 4 | 0 | 50 | 10 | M | 40 | 0 |
| 5 | 0 | 10 | 30 | 0 | M | 0 |
| d j | 0 | 0 | 0 | 0 | 0 | 40 |
Includerea marginii (1,4) se realizează prin excluderea tuturor elementelor din primul rând și a patra coloană, în care elementul d 41 este înlocuit cu M pentru a elimina formarea unui ciclu non-Hamiltonian.
Rezultă o altă matrice redusă (4 x 4), care este supusă operației de reducere.
∑d i + ∑d j = 10
| eu j | 1 | 2 | 3 | 5 | d i |
| 2 | 20 | M | 0 | 30 | 0 |
| 3 | 30 | 0 | M | 0 | 0 |
| 4 | M | 50 | 10 | 40 | 10 |
| 5 | 0 | 10 | 30 | M | 0 |
| d j | 0 | 0 | 0 | 0 | 10 |
Limita inferioară a submulțimii (1,4) este egală cu:
H(1,4) = 140 + 10 = 150 ≤ 180
Deoarece limita inferioară a acestei submulțimi (1,4) este mai mică decât submulțimea (1*,4*), includem muchia (1,4) în traseul cu nouă frontieră H=150
Pasul 2.
Determinarea marginii de ramificareși împărțiți întregul set de rute relativ la această margine în două subseturi (i,j) și (i*,j*).
În acest scop, pentru toate celulele matricei cu elemente zero, înlocuim zerourile unul câte unul cu M (infinit) și determinăm pentru ele suma constantelor de reducere rezultate, acestea fiind date în paranteză.
| eu j | 1 | 2 | 3 | 5 | d i |
| 2 | 20 | M | 0(20) | 30 | 20 |
| 3 | 30 | 0(10) | M | 0(30) | 0 |
| 4 | M | 40 | 0(30) | 30 | 30 |
| 5 | 0(30) | 10 | 30 | M | 10 |
| d j | 20 | 10 | 0 | 30 | 0 |
d(2,3) = 20 + 0 = 20; d(3,2) = 0 + 10 = 10; d(3,5) = 0 + 30 = 30; d(4,3) = 30 + 0 = 30; d(5,1) = 10 + 20 = 30;
Cea mai mare sumă de constante de reducere este (0 + 30) = 30 pentru muchia (3,5), prin urmare, mulțimea este împărțită în două submulți (3,5) și (3*,5*).
Limita inferioară pentru ciclurile hamiltoniene ale acestui submult este:
H(3*,5*) = 150 + 30 = 180
Eliminăm muchia (3.5) prin înlocuirea elementului d 35 = 0 cu M, după care efectuăm următoarea reducere a matricei distanțelor pentru submulțimea rezultată (3*,5*), ca urmare obținem o matrice redusă. .
| eu j | 1 | 2 | 3 | 5 | d i |
| 2 | 20 | M | 0 | 30 | 0 |
| 3 | 30 | 0 | M | M | 0 |
| 4 | M | 40 | 0 | 30 | 0 |
| 5 | 0 | 10 | 30 | M | 0 |
| d j | 0 | 0 | 0 | 30 | 30 |
Includerea marginii (3.5) se realizează prin excluderea tuturor elementelor din rândul 3 și coloana a 5-a, în care elementul d 53 este înlocuit cu M pentru a elimina formarea unui ciclu non-Hamiltonian.
Ca urmare, obținem o altă matrice redusă (3 x 3), care este supusă operației de reducere.
Suma constantelor de reducere ale matricei reduse:
∑d i + ∑d j = 10
După operația de reducere, matricea redusă va arăta astfel:
| eu j | 1 | 2 | 3 | d i |
| 2 | 20 | M | 0 | 0 |
| 4 | M | 40 | 0 | 0 |
| 5 | 0 | 10 | M | 0 |
| d j | 0 | 10 | 0 | 10 |
Limita inferioară a submulțimii (3.5) este egală cu:
H(3,5) = 150 + 10 = 160 ≤ 180
Deoarece limita inferioară a acestei submulțimi (3,5) este mai mică decât submulțimea (3*,5*), includem muchia (3,5) în traseu cu o nouă limită H = 160
Pasul 3.
Determinarea marginii de ramificareși împărțiți întregul set de rute relativ la această margine în două subseturi (i,j) și (i*,j*).
În acest scop, pentru toate celulele matricei cu elemente zero, înlocuim zerourile unul câte unul cu M (infinit) și determinăm pentru ele suma constantelor de reducere rezultate, acestea fiind date în paranteză.
| eu j | 1 | 2 | 3 | d i |
| 2 | 20 | M | 0(20) | 20 |
| 4 | M | 30 | 0(30) | 30 |
| 5 | 0(20) | 0(30) | M | 0 |
| d j | 20 | 30 | 0 | 0 |
d(2,3) = 20 + 0 = 20; d(4,3) = 30 + 0 = 30; d(5,1) = 0 + 20 = 20; d(5,2) = 0 + 30 = 30;
Cea mai mare sumă de constante de reducere este (0 + 30) = 30 pentru muchia (5,2), prin urmare, mulțimea este împărțită în două submulți (5,2) și (5*,2*).
Limita inferioară pentru ciclurile hamiltoniene ale acestui submult este:
H(5*,2*) = 160 + 30 = 190
Eliminăm muchia (5,2) prin înlocuirea elementului d52 = 0 cu M, după care efectuăm următoarea reducere a matricei distanțelor pentru submulțimea rezultată (5*,2*), ca urmare obținem o reducere redusă. matrice.
| eu j | 1 | 2 | 3 | d i |
| 2 | 20 | M | 0 | 0 |
| 4 | M | 30 | 0 | 0 |
| 5 | 0 | M | M | 0 |
| d j | 0 | 30 | 0 | 30 |
Includerea marginii (5.2) se realizează prin excluderea tuturor elementelor din al 5-lea rând și din a 2-a coloană, în care elementul d 25 este înlocuit cu M pentru a elimina formarea unui ciclu non-Hamiltonian.
Ca urmare, obținem o altă matrice redusă (2 x 2), care este supusă operației de reducere.
Suma constantelor de reducere ale matricei reduse:
∑d i + ∑d j = 20
După operația de reducere, matricea redusă va arăta astfel:
| eu j | 1 | 3 | d i |
| 2 | 20 | 0 | 0 |
| 4 | M | 0 | 0 |
| d j | 20 | 0 | 20 |
Limita inferioară a submulțimii (5,2) este egală cu:
H(5,2) = 160 + 20 = 180 ≤ 190
Deoarece limita inferioară a acestei submulțimi (5,2) este mai mică decât submulțimea (5*,2*), includem muchia (5,2) în traseu cu o nouă limită H = 180
În conformitate cu această matrice, includem muchiile (2,1) și (4,3) în traseul hamiltonian.
Ca rezultat, de-a lungul arborelui de ramificare al ciclului hamiltonian, muchiile formează:
(1,4), (4,3), (3,5), (5,2), (2,1),
Lungimea traseului este F(Mk) = 180
Rezolvarea problemei vânzătorului ambulant folosind metoda ramurilor și legaturilor
Definiții
Un grafic este o mulțime finită nevidă constând din două submulțimi și . Primul subset 
(vârfurile) constă din orice set de elemente. Al doilea submult (arcuri) este format din perechi ordonate de elemente ale primului submult 
. Dacă vârfurile şi 
astfel încât , atunci acestea sunt vârfuri adiacente.
O rută într-un grafic este o succesiune de vârfuri 
nu neapărat perechi distincte, unde pentru oricare 
adiacent la 
. O rută se numește lanț dacă toate marginile sale sunt distincte în perechi. Dacă atunci traseul este numit închis. Un circuit închis se numește ciclu.
Formularea problemei
Vânzătorul ambulant trebuie să călătorească n orase. Pentru a reduce costurile, vrea să construiască un traseu astfel încât să ocolească toate orașele exact o dată și să revină la cel inițial cu un minim de costuri.
În ceea ce privește teoria grafurilor, problema poate fi formulată după cum urmează. A stabilit n vârfuri și matrice ( c ij), unde c ij ≥0 – lungimea (sau prețul) arcului ( i,
j),
. Sub traseul vânzătorului ambulantz hai sa intelegem ciclul i 1 ,
i 2 ,…,
i n ,
i 1 punctele 1,2,…, n. Prin urmare, traseu este un set de arce. Dacă între orașe iȘi j nu există tranziție, atunci simbolul „infinit” este plasat în matrice. Acesta trebuie așezat în diagonală, ceea ce înseamnă că este interzis să te întorci într-un punct prin care ai trecut deja traseul vânzătorului ambulant, lungimea traseului l(z) este egală cu suma lungimilor arcurilor incluse în traseu. Lăsa Z– ansamblul tuturor rutelor posibile. Vârful inițial i 1 – fix. Trebuie să găsiți o rută z 0 Z, astfel încât l(z 0)= min l(z),
z
Z.
Rezolvarea problemei
Ideea principală a metodei de ramificare și legături este că mai întâi se construiește o limită inferioară φ pe lungimile setului de rute Z. Apoi setul de rute este împărțit în două subseturi, astfel încât primul submult 
a constat din trasee care conțin un arc (i, j) și o altă submulțime 
nu conținea acest arc. Pentru fiecare dintre subseturi, limitele inferioare sunt determinate în conformitate cu aceeași regulă ca și pentru setul original de rute. Limitele inferioare rezultate pentru submulțimi 
și se dovedesc a fi nu mai puțin decât limita inferioară a setului tuturor rutelor, adică φ(Z)≤ φ (), φ(Z) ≤ φ ().
Compararea limitelor inferioare φ () Și φ (), putem selecta subsetul de rute care este mai probabil să conțină o rută de lungime minimă.
Apoi, unul dintre subseturi, sau conform unei reguli similare, este împărțit în două noi 
Și 
. Limitele inferioare sunt din nou găsite pentru ei φ
(), Și φ
() etc. Procesul de ramificare continuă până când este găsită o singură rută. Se numește prima înregistrare. Apoi se uită printre ramurile rupte. Dacă limitele lor inferioare sunt mai mari decât lungimea primei înregistrări, atunci problema este rezolvată. Dacă există acelea pentru care limitele inferioare sunt mai mici decât lungimea primei înregistrări, atunci submulțimea cu cea mai mică limită inferioară suferă o ramificare suplimentară până când se convinge că nu conține cel mai bun traseu.
Dacă se găsește unul, atunci analiza ramurilor rupte continuă în raport cu noua valoare a lungimii traseului. Se numește a doua înregistrare. Procesul de soluție se încheie când toate subseturile au fost analizate.
Pentru implementarea practică a metodei ramificație și legat în raport cu problema vânzătorului ambulant, vom indica o tehnică de determinare a limitelor inferioare ale submulților și de împărțire a setului de rute în submulțimi (ramificare).
Pentru a găsi limita inferioară, folosim următoarea considerație: dacă se adună sau se scade un anumit număr din elementele oricărui rând din matricea problemei vânzătorului ambulant (rând sau coloană), atunci optimitatea planului nu va Schimbare. Lungimea oricărui traseul vânzătorului ambulant se va modifica cu această sumă.
Scădeți din fiecare linie un număr egal cu elementul minim al acestei linii. Scădeți din fiecare coloană un număr egal cu elementul minim al acelei coloane. Matricea rezultată se numește redusă prin rânduri și coloane. Suma tuturor numerelor scăzute se numește constantă de reducere.
O constantă de turnare ar trebui aleasă ca limită inferioară a lungimii traseelor.
Împărțirea unui set de rute în subseturi
Pentru a identifica candidații pentru includerea în setul de arce de-a lungul căruia se realizează ramificarea, luăm în considerare în matricea dată toate elementele egal cu zero. Să găsim gradele Θ ij ale elementelor zero ale acestei matrice. Gradul elementului zero Θ ij este egal cu suma elementului minim din rând iși elementul minim din coloană j(la alegerea acestor minime c ij – neluat în calcul). Cu cea mai mare probabilitate, traseul necesar aparține arcelor cu gradul maxim zero.
Pentru a obține matricea de plată a rutelor, inclusiv arcul ( i, j) tăiem rândul din matrice i si coloana j, iar pentru a preveni formarea unui ciclu în traseu înlocuim elementul care închide la infinit lanțul curent.
Multe rute care nu includ un arc ( i, j) se obţine prin înlocuirea elementului c ij la infinit.
Un exemplu de rezolvare a problemei vânzătorului ambulant folosind metoda ramurilor și legaturilor
Un vânzător ambulant trebuie să călătorească 6 orase. Pentru a reduce costurile, vrea să construiască un traseu astfel încât să ocolească toate orașele exact o dată și să revină la cel inițial cu un minim de costuri. Orașul sursă A. Costurile deplasării între orașe sunt date de următoarea matrice:
Rezolvarea problemei
Pentru comoditatea prezentării, peste tot mai jos în matricea de plată vom înlocui numele orașelor (A, B, ..., F) cu numerele rândurilor și coloanelor corespunzătoare (1, 2, ..., 6).
Să găsim limita inferioară a lungimilor setului tuturor rutelor. Să scădem din fiecare rând un număr egal cu elementul minim al acestui rând, apoi să scădem din fiecare coloană un număr egal cu elementul minim al acestei coloane, și astfel să prezentăm o matrice în rânduri și coloane. Minime de rând: r 1 =15, r 2 =1, r 3 =0, r 4 =16, r 5 =5, r 6 =5.
După ce le scădem linie cu linie obținem:
Minimele coloanei: h 1 =5, h 2 =h 3 =h 4 =h 5 =h 6.
După scăderea lor pe coloane, obținem următoarea matrice:
Să găsim limita inferioară φ (Z) = 15+1+0+16+5+5+5 = 47.
Pentru a identifica candidații pentru includerea în setul de arce de-a lungul cărora se realizează ramificarea, găsim gradele Θ ij ale elementelor zero ale acestei matrice (suma minimelor din rând și coloană). Θ 14 = 10 + 0,
Θ 24 = 1 + 0, Θ 36 = 5+0, Θ 41 = 0 + 1, Θ 42 = 0 + 0, Θ 56 = 2 + 0, Θ 62 = 0 + 0,
Θ 63 = 0 + 9, Θ 65 = 0 + 2. Cel mai înalt grad este Θ 14 = 10. Efectuăm ramificare de-a lungul arcului (1, 4).
Limita inferioară pentru set 
rămâne egal cu 47. Pentru toate traseele setului
din orașul A nu ne mutăm în orașul D. În matrice acest lucru este indicat prin plasarea semnului ∞ în celula (1, 4). În acest caz, părăsirea orașului A se adaugă la estimarea limitei inferioare de macar cel mai mic element al primului rând. φ
()
= 47 + 10.
În matricea corespunzătoare punem c 14 = ∞.
După efectuarea procedurii de reducere cu r 1 = 10, obținem o nouă limită inferioară de 57 + 10 = 67.
În matricea corespunzătoare , tăiem primul rând și a patra coloană și punem c 41 = ∞ pentru a preveni apariția unui ciclu 1→ 4 → 1. Obținem o nouă matrice de profit ( c 1 ij):
Pentru a reduce, trebuie să scădeți minimul din prima coloană: h 1 =1. În acest caz, limita inferioară va deveni egală cu 47 + 1 = 48. Compararea limitelor inferioare
φ
() = 67 și φ
() = 48, care este mai probabil să conțină o rută de lungime minimă.
Orez. 1 Ramificare în primul pas
În continuare continuăm procesul de ramificare. Să găsim gradele Θ ij ale elementelor zero ale acestei matrice Θ 21 =16, Θ 36 = 5, Θ 42 = 2, Θ 56 = 2, Θ 62 = 0, Θ 63 =9, Θ 65 = 2. gradul cel mai mare este Θ 21. Apoi setul este împărțit de-a lungul arcului (2, 1) în două noi 
Și 
.
În matricea pentru tăiem rândul 2 și coloana 1. arcurile (1, 4) și (2, 1) formează o cale conectată (2, 1, 4), să punem c 42 = ∞ pentru a preveni ciclul 2→1→ 4 → 2.
Pentru a reduce, trebuie să scădeți minimul din linia 4: r 4 =2. În acest caz, limita inferioară va deveni egală cu 48+2 = 50.
Limita inferioară pentru , obținut ca și în etapa anterioară de ramificare, este egal cu 48 + 16 = 64. Comparând limitele inferioare φ () = 64 și φ () = 50 .
Orez. 2 Ramificare în a doua etapă
Matricea de plată dată pentru
Pentru a reduce, trebuie să scădeți minimul de-a lungul liniei 3: r 3 =5. În acest caz, limita inferioară va deveni egală cu 50 + 5 = 55. Selectăm un subset de rute pentru partiţionare ulterioară.
Orez. 3 Ramificare în a treia etapă
Matricea de plată dată pentru
|
0 Cheat sheet >> Contabilitate și audit Activități, influență, participare la decizie sarcini. ÎN situatii diferite viata... Special sarcini programare matematică specială sarcini programare matematică. Sarcină O vânzător ambulant.Metodă ramuriȘi frontiere. Sarcină O vânzător ambulant Lasa... |
(5x5) (Contează pentru 4 probleme condiționate) timp pentru a completa 2 perechi) (Prezentare VÂNZĂTOR CALATOR) Cea mai dificilă problemă în cercetarea operațională
Folosind metoda ramificație și legat, trebuie să găsiți cea mai scurtă rută pentru a ocoli 5 orașe cu revenire la cel inițial, CARE FIECARE ORAȘ ESTE VIZITAT EXACT 1 dată (matricea arată prețurile pentru călătoria din orașul „stânga” la "superior").
Soluție ramificată și legată
Procesul se termină parțial după selectarea k-2 muchii, unde k este numărul total de vârfuri. Într-o problemă 2x2, soluția este unică (de obicei) duce la o corecție a limitei superioare. Dacă toate (celelalte) limite inferioare sunt mai rele, se obține răspunsul. Într-un exemplu precum cel dat în această sarcină, această situație apare de obicei, dar într-un grafic mai mare și mai complex (când se creează un algoritm universal), este necesar să se descrie acțiuni ulterioare. Dacă nu toate limitele inferioare sunt încă mai slabe decât limita superioară ajustată, atunci seturile netriviale supraviețuitoare vor trebui să fie ramificate până când fie dispar din cauza celei înalte, adică. estimare inferioară proastă sau (ceea ce este rar) înainte de a primi o nouă estimare superioară - solutie noua, superioară ca calitate celui precedent. Procesul continuă până când soluția rezultată rămâne necontestată.
Pasul nr. 0 Estimăm ciclul 1-2-3-4-5-1 - aceasta este prima aproximare a estimării superioare. În plus, dacă pe orice ramură a arborelui de ramificare estimarea inferioară a subsetului de soluții se dovedește a fi mai mare decât cea superioară, această ramură „se stinge”, deoarece toate soluțiile ei sunt mai rele decât cele existente.
Pasul nr. 1a) Scrieți constantele de reducere linie cu linie. Acestea sunt numerele minime din rânduri. Ele trebuie scăzute din elementele liniilor lor (în fiecare linie va apărea cel puțin un zero).
Pasul nr. 1b) În matricea tocmai obținută la pasul 1a) (cu zerouri în rânduri), efectuați exact aceeași operație de-a lungul coloanelor - căutați coloane în care minimul e este 0 și scădeți-l. În formatul de autotest, verificați dacă acum există cel puțin un zero în fiecare coloană și rând din matricea tarifelor.
Pasul nr. 1c) Se calculează suma constantelor de reducere obţinute în etapele a) şi b). Evident, nicio rută nu poate costa mai puțin - deci aceasta este o estimare mai mică. În continuare vom crește această estimare cu suma 
Și 
(vom descrie aceste cantități mai jos), unde 
- o pereche de indici ai muchiei de-a lungul căreia se alege să se ramifică.
Să descriem cum va avea loc ramificarea: selectăm muchia i, j (satisfăcând cerințele din următorul paragraf) setul de rute hamiltoniene poate fi gândit ca un set combinatoric mare de „mărgele” unice compus din legături precum St. Petersburg-Moscova, Moscova-Odesa, Odesa-Belgrad etc. Să adoptăm o metodă de împărțire a întregului set de poteci închise în cele unde există un drum Odesa-Belgrad și cele unde nu există (primul set este mai mic decât al doilea).
Teoretic, este posibil să se ramifice de-a lungul oricărei margini, dar sarcina noastră este să ne asigurăm că, pe un set, estimarea inferioară a prețului rutei nu se modifică, iar pe de altă parte, crește cât mai mult posibil - acest lucru poate contribui la faptul că în cele mai multe cazuri o căutare combinatorie, în general vorbind, a unui algoritm exponențial pentru rezolvarea NP completă sarcina nu va fi prea mare.
Pentru a face acest lucru: Pasul nr. 2. Calculăm costul traversării pentru fiecare element zero (dacă se transformă în infinit ∞) 
- cantitatea cu care sunt crescute constantele de reducere ale rândului și coloanei corespunzătoare.
Împărțim setul actual de soluții în două:
Luați în considerare matricea costurilor de călătorie din orașul „stânga” spre „sus”
Estimarea globală inițială Zupper=10+10+20+15+10 = 65 se obține prin ciclu. (marginile corespunzătoare sunt încercuite în pătrate în figură - unul în colțul din stânga jos, restul deasupra diagonalei).
Să începem să desenăm un copac ramificat
În matricea rezultată
vom calcula costul suplimentar al unui „ocol” pentru fiecare individ zero (adică cu cât va crește suma constantelor de reducere dacă drumul încetează să mai existe (prețul tarifului va fi înlocuit cu infinit)) și alegeți acel „zero” al cărui cost de ocolire este maxim.
(1,2)=0
(1,5)=1
(2,1)=0
(2,3)=5 (Maxim )
(3,1)=0
(3,4)=2
(4,2)=4
(5,2)=2
Deci, costul maxim al unui ocol este observat atunci când muchia este oprită (2,3)=5.
Cu algoritmul nostru, este firesc să împărțim toate ciclurile de ocolire în cele care conțin marginea (2,3) și cele care nu o conțin. Estimarea mai mică a costului primului grup de cicluri (o vom calcula mai târziu) cel mai probabil nu se va modifica, estimarea mai mică a ciclurilor fără (2,3) crește cu suma (2,3)=5.
Pe pagină separatăÎncepem să desenăm copacul ramificat.
Pe stadiul inițial conține setul tuturor ciclurilor, care este împărțit într-un set care conține (2,3) (sunt mai puține) în stânga și care nu conține (2,3) în dreapta.
Limita inferioară a mulțimii drepte (mai mari) se obține prin suma limitei vârfului precedent Z min=58 și(2,3)=5:Z min =58+5=63.
În setul din stânga, marginea (2,3) (relativ vorbind, calea Sankt Petersburg - Moscova) este obligatorie - în consecință, nu mai avem de ales unde să mergem din orașul 2 (ștergem linia 2) și cum pentru a ajunge in orasul nr.3 (stergem coloana).
Ultimul arbore de ramură:
Metoda finală.
Rezultatul este o matrice 2x2.
Mic exemplu.
În cele din urmă, să ne uităm la o matrice 3x3.
Atunci limita superioară a lungimilor tuturor rutelor este Z max = 4+9+8 = 21
Astfel, estimarea inferioară a lui Z este mai mică = 16 (6+3+4+3).
Estimăm constantele de bypass:
Să combinăm orașele 2 și 1 în ramura din stânga, în ramura din dreapta costul estimat mai mic va crește de la 16 la 5 la 21.
obținem matricea
Să interzicem scurt circuit- a evita 
și reduceți matricea
Pe ramura stângă ΔZ_=4, nouă estimare a funcției obiectiv Z_=16+ ΔZ_=16+4=20.
Marginea selectată
Coaste rămase 
.
Folosind principiul domino, restabilim ciclul minim pornind de la muchia incepand cu 1, cu aceasta muchie 
, parcă ar merge ca un „tren”.
Aceasta este o cale specifică de lungime 20, moment în care obținem o nouă limită superioară, care este mai bună decât vechea limită superioară de 21.
Pe arborele de ramificare al seturilor de enumerare, ramura cu estimarea mai mare inferioară 21 (ramura dreaptă) dispare.
În cazul nostru, opțiunea rezultată s-a dovedit a fi mai bună decât toate estimările inferioare pentru alte ramuri.
Răspuns: 
.
Examinare
Prezentare VÂNZĂTOR CALATOR.
Sarcina este verificată de profesor cu privire la proiectarea arborelui ramificat. Pentru ca acesta să prezinte cele mai complete informații necesare verificării, afișați estimările inferioare la vârfurile arborelui funcții țintă, toate θ (creșterea sumei constantelor de reducere la un viraj la dreapta), toate ΔZ (creșterea sumei constantelor de reducere la o viraj la stânga) trebuie afișate pe marginile arborelui. În timpul unui viraj la stânga, se selectează o muchie obligatorie (marcată pe arborele ramurilor) și se adaugă o muchie interzisă. Pentru a explica alegerea sa, lângă arborele de ramificare la nivelul corespunzător, ar trebui înfățișat un lanț în care muchia interzisă, împreună cu cele selectate anterior (inclusiv cea selectată în prezent), generează un ciclu care nu trece prin toate marginile (așa-numitul „scurtcircuit” al ciclului).
Răspunsul oferă un lanț de Muchii de forma (1,k)(k,l)(l,m)..(r,1)(în funcție de dimensiunea problemei), costul traseului constă din estimarea inferioară inițială și incrementele sale ΔZ (dacă au existat doar TRIGĂȚI - viraje la stânga) și - ceea ce se întâmplă foarte rar - ΔZ și θ, dacă, PE ÎN PLUS față de viraje la stânga, au existat unul sau mai multe viraje la dreapta. Verificați costul soluției OBȚINITE folosind matricea originală, explicați motivele discrepanței - dacă există (nu ar trebui să existe nepotriviri).
Bună, Habr! În timp ce implementam diverși algoritmi pentru găsirea ciclului hamiltonian la cel mai mic cost, am dat peste o publicație care oferă propria mea versiune. După ce am încercat, am primit un răspuns greșit:
Căutările ulterioare pe internet nu au adus rezultatul așteptat: fie o descriere teoretică dificilă pentru nematematicieni, fie de înțeles, dar cu erori.
Sub tăietură veți găsi un algoritm corectat și un calculator online.
Metoda în sine, publicată de Little, Murthy, Sweeney, Carell în 1963, este aplicabilă multor probleme NP-complete și este un material foarte teoretic care, fără cunoștințe bune în limba engleză iar matematica nu poate fi aplicată imediat problemei noastre de vânzător ambulant.
Pe scurt despre metodă - aceasta este o căutare completă a tuturor opțiuni posibile cu eliminarea soluţiilor clar suboptime.
Algoritm corectat pentru găsirea unei rute cu adevărat minime
Algoritmul constă din două etape:
Primul stagiu
Reducerea matricei costurilor și calcularea estimării inferioare a costului rutei r.
1. Calculați cel mai mic element din fiecare rând (constante de turnare pentru rând)2. Trecem la o nouă matrice de cost, scăzând constanta ei de reducere din fiecare rând
3. Calculați cel mai mic element din fiecare coloană (constanta de constrângere pentru coloană)
4. Trecem la o nouă matrice de cost, scăzând constanta ei de reducere din fiecare coloană.
Ca rezultat, avem o matrice de cost în care fiecare rând și fiecare coloană are cel puțin un element zero.
5. Calculați limita pe în această etapă ca sumă a constantelor de turnare pentru coloane și rânduri ( această hotar va fi costul sub care este imposibil să construiți traseul dorit)
A doua etapă (principală).
1. Calculul penalizării pentru neutilizare pentru fiecare element zero al matricei de cost date.Penalizarea pentru neutilizarea unui element cu indice (h,k) în matrice înseamnă că această margine nu este inclusă în traseul nostru, ceea ce înseamnă că costul minim de „neutilizare” a acestei margini este egal cu suma elementelor minime din rândul h și coloana k.
A) Căutăm toate elementele zero în matricea dată
b) Pentru fiecare dintre ele calculăm penalitatea pentru neutilizare.
c) Selectați elementul care corespunde pedepsei maxime (oricare, dacă sunt mai multe)
2. Acum împărțim setul nostru S în seturi - cele care conțin marginea cu penalitatea maximă (S w) și cele care nu conțin această margine (S w/o).
3. Calculul estimărilor de cost pentru rutele incluse în fiecare dintre aceste seturi.
a) Pentru mulțimea S fără totul este simplu: deoarece nu luăm marginea corespunzătoare cu penalitatea maximă (h,k), atunci estimarea costului pentru aceasta este egală cu estimarea costului mulțimii S + penalitatea pentru a nu folosi marginea (h,k)
b) La calcularea costurilor pentru mulțimea S w, ținem cont că, întrucât muchia (h,k) este inclusă în traseu, înseamnă că muchia (k,h) nu poate fi inclusă în traseu, deci în în matricea costurilor scriem c(k,h) =infinit, iar din moment ce am „plecat deja” din punctul h și „am ajuns deja” din punctul k, atunci nici o margine care pleacă de la h și nici o margine care sosește la k nu mai poate fi folosit, așa că tăiem din matricea costurilor rândul h și coloana k. După aceasta, reducem matricea, iar apoi estimarea costului pentru S w este egală cu suma costului estimat pentru S și r(h,k), unde r(h,k) este suma constantelor de reducere pentru matricea costurilor modificată.
4. De la toata lumea de seturi nepartiționate, se selectează cel cu cel mai mic scor.
Continuăm în acest fel până când în matricea costurilor rămâne un rând netașat și o coloană netașată.
Mică optimizare - adăugarea de euristici
Da, într-adevăr, de ce nu introducem euristica? Într-adevăr, în algoritmul branch and bound, construim de fapt un arbore, la nodurile căruia decidem să luăm marginea (h,k) sau nu și să atârnăm doi copii - Sw(h,k) și Sw/o( h,k). Dar cea mai bună opțiune pentru următoarea iterație selectăm doar prin estimare. Așa că să-l alegem pe cel mai bun nu numai din punct de vedere al ratingului, ci și din punct de vedere al adâncimii în copac, pentru că... Cu cât elementul selectat este mai adânc, cu atât este mai aproape de sfârșitul numărării. Astfel putem aștepta în sfârșit un răspuns.
Acum, de fapt, despre erorile din acea publicație
A existat o singură greșeală - ar trebui să alegeți pentru partiționarea setului cu limita minimă a tuturor moduri posibile, și nu de la cei doi copii obținuți în urma ultimei despărțiri.Dovada
Să revenim la poza de la începutul postării:
Și iată soluția cu algoritmul corectat:
Răspuns: calea:3=>4=>2=>1=>5=>3 lungime: 41
După cum puteți vedea, includerea marginii 5:2 în soluție ar fi o greșeală. Q.E.D
Grafic care compară metoda ramurilor și legate și timpul petrecut pentru tabel aleatoriu de la 5x5 la 10x10: 
Graficul timpului maxim și minim petrecut pentru matrice de la 5x5 la 66x66. 
Încearcă cu soluție detaliată Poate sa
Buna ziua! În timp ce implementam diverși algoritmi pentru găsirea ciclului hamiltonian la cel mai mic cost, am dat peste o publicație care oferă propria mea versiune. După ce am încercat, am primit un răspuns greșit:
Căutările ulterioare pe internet nu au adus rezultatul așteptat: fie o descriere teoretică dificilă pentru nematematicieni, fie de înțeles, dar cu erori.
Sub tăietură veți găsi un algoritm corectat și un calculator online.
Metoda în sine, publicată de Little, Murthy, Sweeney, Carel în 1963, este aplicabilă multor probleme NP-complete și este un material foarte teoretic care, fără cunoștințe bune de engleză și matematică, nu poate fi aplicat imediat problemei noastre de vânzător ambulant. .
Pe scurt despre metodă - este o căutare completă a tuturor opțiunilor posibile cu eliminarea soluțiilor clar neoptimale.
Algoritm corectat pentru găsirea unei rute cu adevărat minime
Algoritmul constă din două etape:
Primul stagiu
Reducerea matricei costurilor și calcularea estimării inferioare a costului rutei r.
1. Calculați cel mai mic element din fiecare rând (constante de turnare pentru rând)
2. Trecem la o nouă matrice de cost, scăzând constanta ei de reducere din fiecare rând
3. Calculați cel mai mic element din fiecare coloană (constanta de constrângere pentru coloană)
4. Trecem la o nouă matrice de cost, scăzând constanta ei de reducere din fiecare coloană.
Ca rezultat, avem o matrice de cost în care fiecare rând și fiecare coloană are cel puțin un element zero.
5. Calculăm limita în această etapă ca sumă a constantelor de reducere pentru coloane și rânduri (această limită va fi costul sub care este imposibil să construiți traseul necesar)
A doua etapă (principală).
1. Calculul penalizării pentru neutilizare pentru fiecare element zero al matricei de cost date.
Penalizarea pentru neutilizarea unui element cu indice (h,k) în matrice înseamnă că această margine nu este inclusă în traseul nostru, ceea ce înseamnă că costul minim de „neutilizare” a acestei margini este egal cu suma elementelor minime din rândul h și coloana k.
a) Căutăm toate elementele zero în matricea dată
b) Pentru fiecare dintre ele calculăm penalitatea pentru neutilizare.
c) Selectați elementele care corespund pedepsei maxime
2. Acum împărțim mulțimea noastră S în seturi - care conțin muchia cu penalitatea maximă (S w i) și care nu conțin aceste muchii (S w i /o).
3. Calculul estimărilor de cost pentru rutele incluse în fiecare dintre aceste seturi.
a) Pentru mulțimile S w i /o totul este simplu: deoarece nu luăm muchia corespunzătoare cu penalitatea maximă (hi ,k i), atunci pentru aceasta costul estimat este egal cu costul estimat al mulțimii S + penalizare pentru nu folosind marginea (hi ,k i)
b) La calcularea costurilor pentru mulțimea S w i, ținem cont că din moment ce muchia (hi i,k i) este inclusă în traseu, înseamnă că muchia (k i,hi) nu poate fi inclusă în traseu, prin urmare în matricea costurilor scriem c(k i,hi) =infinit, iar din moment ce am „plecat deja” din punctul hi și „am ajuns deja” din punctul ki, atunci nici o singură muchie care să plece din hi și nici măcar o singură muchie. marginea care ajunge la ki, poate fi deja utilizată, așa că tăiem din matricea costurilor rândul h i și coloana k i. După aceasta, dăm matricea, iar apoi estimarea costului pentru S w este egală cu suma estimării costurilor pentru S și r(hi,k i), unde r(hi,k i) este suma constantelor de reducere pentru matricea costurilor modificată.
4. Dintre toate seturile indivize, se selectează cel cu cel mai mic punctaj.
Continuăm în acest fel până când în matricea costurilor rămâne un rând netașat și o coloană netașată.
Mică optimizare - adăugarea de euristici
Da, într-adevăr, de ce nu introducem euristica? Într-adevăr, în algoritmul branch and bound, construim de fapt un arbore, la nodurile căruia decidem să luăm marginea (hi,k i) sau nu și să atârnăm doi sau mai mulți copii - Sw(hi,k i) și Sw/ o (bună, k i). Dar selectăm cea mai bună opțiune pentru următoarea iterație numai pe baza evaluării. Așa că să-l alegem pe cel mai bun nu numai din punct de vedere al ratingului, ci și din punct de vedere al adâncimii în copac, pentru că... Cu cât elementul selectat este mai adânc, cu atât este mai aproape de sfârșitul numărării. Astfel putem aștepta în sfârșit un răspuns.
Acum, de fapt, despre erorile din acea publicație
Aceste erori au un singur motiv - ignorarea posibilității apariției mai multor elemente zero cu penalizare maximă. În acest caz, este necesar să se împartă nu în două subseturi, ci în cantitate mare(2n). De asemenea, ar trebui să alegeți pentru partiționarea setului cu limita minimă din toate căile posibile, și nu dintre cei doi copii obținuți ca urmare a ultimei partiții.
Dovada
Să revenim la poza de la începutul postării:
Și iată soluția cu algoritmul corectat.
