Rezolva problema folosind algoritmul de returnare a forței brute.
Sarcină după opțiune: Rezolvați problema vânzătorului călător prin recuperarea forței brute. Prețurile biletelor sunt specificate utilizând o matrice simetrică n'n.
Sarcina vânzătorului călător este următoarea: există orașe și prețurile biletelor sunt cunoscute. Un vânzător de călătorie trebuie să viziteze toate orașele odată, întorcându-se la cel de unde a început. Este necesar să găsiți o rută de trafic în care prețul total al biletului va fi minim. Schema de rutare este specificată de grafic (a se vedea figura 1). Această problemă reduce la căutarea unui ciclu Hamiltonian într-un grafic cu o sumă minimă de valori ale căilor între noduri.
Pentru a rezolva problema, este necesar să trecem prin toate ciclurile Hamiltonian și să găsim între ei ciclul de cea mai mică valoare.
Calea va fi reprezentată ca o succesiune de vârfuri (x1, x2, ..., xk). O astfel de cale va fi simplă dacă și numai dacă xi x xj pentru toate i j j, i, jV.
Pentru ca secvențele de vârfuri (x1, x2, ... xk) să satisfacă condiția xi ¹xj. vom colora vertexele acestor secvențe și vom ține cont de colorare atunci când alegem cozile de vârfuri. Ciclul Hamiltonian, cu începutul lui x1 = n0. reprezentăm secvența (x1, x2, ..., xn, xn + 1), unde xn + 1 = x1 = n0.
Fie Ak setul de vârfuri adiacente lui xk. cn este colorarea nodului n. Conform schemei generale a algoritmului de căutare cu întoarcere, obținem următorul algoritm pentru enumerarea ciclurilor Hamiltonian:
void Gamilton (int k)
Articole similare
-
Algoritm și exemple de probleme rezolvate folosind algoritmi - stadopedia
-
Pentru a ajuta un tânăr ofițer - garnizoana poliției rutiere și sarcinile ei
Trimiteți-le prietenilor: