← Toate simulatoarele
Metoda backtracking · problema comis-voiajorului

Comis-voiajorul — simulator pas cu pas

♛ Reginele Labirint Comis-voiajor
Graful orașelor: pas 0 / 0
startApasă „Pas înainte" ca să urmărești cum se construiește traseul oraș cu oraș. Un oraș se acceptă doar dacă e nevizitat și legat de cel precedent; când nu se mai poate continua, se revine.

Enunțul problemei

Un comis-voiajor pleacă din orașul de start și vrea să viziteze toate cele n orașe exact o dată, întorcându-se la final în orașul de plecare. Între unele orașe există legături directe. Se cer toate traseele (ciclurile hamiltoniene). Stiva st reține ordinea orașelor, cu st[1] = orașul de start.

Graful orașelor start = 1

matricea de adiacență a — celula verificată e evidențiată

Stiva st traseul curent

Starea execuției

nivel curent k–
orașe în traseu1
trasee găsite0
Trasee găsite (circuite)

Cod C++ codul verbatim · linia activă e evidențiată


    


    
    

      
Limbaj natural ce face pasul curent

      
start

      

      

    


    
    

      
Pseudocod schema recursivă backtracking

      

    


    
    

      
Parcurgerea (ilustrarea generării) rămâne tot șirul de stive încercate

      

      

        fiecare stivă = un traseu încercat (jos = st[1] = orașul de start) ·
        ■ oraș adăugat · ■ respins / nu se închide ·
        ■ circuit complet