Căi și cicluri hamiltoniene
Ciclul Hamiltonian (calea) este un ciclu simplu (cale) care conține toate vârfurile graficului. În graficul prezentat în Fig. 8.1 în stânga, ciclul Hamiltonian este, de exemplu, secvența ,,,,,. În graficul prezentat în centru, nu există cicluri hamiltoniene, dar există, de exemplu, căi hamiltoniene. În graficul din dreapta nu există căi hamiltoniene.
În exterior, definiția ciclului Hamiltonian este similară definiției ciclului Euler. Cu toate acestea, există o diferență fundamentală în complexitatea rezolvării problemelor corespunzătoare de recunoaștere și construcție. Am văzut că există un criteriu destul de simplu pentru existența unui tur Euler și algoritm eficient pentru construcția sa. Pentru ciclul hamiltonian (și modurile) pur și simplu nu știu condiții verificabile necesare și suficiente pentru existența lor, și toți algoritmii cunoscuți necesită unele grafice busting un număr mare de opțiuni.
Un ciclu hamiltonian este, cu punctul combinatorie de vedere, o permutare de noduri. Aici, ca și nodurile inițiale ale ciclului puteți selecta orice nod, astfel încât este posibil să se ia în considerare permutări cu primul element fix. Cel mai simplistă plan de cercetare ciclu hamiltonian este o examinare consecventă a tuturor acestor permutări și verificare pentru fiecare dintre acestea, dacă acesta este un ciclu în grafic. O astfel de procedură nu este deja la un număr foarte mare de noduri devine impracticabil din cauza creșterii rapide a numărului de permutări - acolo! permutări ale elementelor cu un element fix fix.
abordare mai rațională este să ia în considerare tot felul de moduri simple, pornind de la un vârf de pornire arbitrar, atâta timp cât nu există nici un ciclu hamiltonian este detectat sau toate căile posibile sunt explorate. De fapt, suntem, de asemenea, vorbim despre iterarea prin permutări, dar reduceri semnificative - de exemplu, în cazul în care vârful este adiacent la un nod, toate! permutații, în care primul loc este, și pe al doilea, nu sunt luate în considerare.
Să luăm în considerare acest algoritm mai detaliat. Vom presupune că graficul este dat de cartierele vârfurilor: pentru fiecare vârf se dă un set de vârfuri adiacente. La fiecare pas al algoritmului există deja o cale încorporată, este stocată în stivă PATH. Pentru fiecare vârf inclus în PATH. a stocat un set de toate vârfurile adiacente, care nu au fost încă considerate ca posibile extensii ale căii de la vârf. Atunci când un vertex este adăugat la o cale, setul este presupus a fi egal. În viitor, vârfurile considerate sunt eliminate din acest set. Următorul pas este să explorați cartierul ultimului punct al traseului PATH. Dacă există noduri care nu aparțin căii, atunci unul dintre aceste noduri este adăugat la cale. În caz contrar, vârful este exclus din stiva. Când, după adăugarea următorului vârf pe cale, se dovedește că această cale conține toate vârfurile graficului. Rămâne să se verifice dacă primii și ultimii vârfuri ale căii sunt adiacente și cu un răspuns afirmativ la emiterea următorului ciclu Hamiltonian.
Algoritmul 2. Căutați cicluri Hamiltonian
- selectați un vârf arbitrar
- whiledo
- dacă
- apoi luați
- dacă vârful nu este în PATH
- atunci
- dacă PATH conține toate vârfurile
- apoi este adiacent la
- apoi dați un ciclu
- altfel scoateți vârful din PATH
Acest algoritm este foarte similar cu algoritmul de căutare în profunzime și diferă de ea, în esență, numai prin aceea că partea de sus deschis. când este explorată întreaga sa vecinătate, nu se închide, ci devine din nou nouă (exclusă din stack). La început, toate nodurile sunt noi. Procesul se termină când toate nodurile devin din nou noi. De fapt, aceasta este căutarea în profunzime. numai nu în grafic, ci în arborele căilor. Vârfurile acestui copac sunt diferite moduri simple, pornind de la partea de sus și marginea copacului conectează cele două căi, dintre care unul este obținut dintr-un alt prin adăugarea unui nod la sfârșitul anului. În Fig. 8.2 arată graficul și arborele său de căi de la vârf.
Articole similare
Trimiteți-le prietenilor: