Din punct de vedere conceptual, imaginați-vă că picurați o piatră într-un iaz și vă uitați la valuri. Traseele ar reprezenta iazul și piatra dvs. poziția de plecare.
Desigur, algoritmul ar trebui să caute o anumită proporție de căi n ^ 2 pe măsură ce distanța n crește. Vă luați poziția de plecare și verificați toate căile disponibile din acel moment. Apoi solicitați recursiv punctele de la sfârșitul acelor căi și așa mai departe.
Puteți crește performanța, fără a vă împiedica dublarea pe o cale, dacă nu re-verificați rutele într-un punct dacă a fost deja acoperită și renunțând la căile care durează prea mult.
Un mod alternativ este de a folosi abordarea feromonilor furnici, unde furnicile se târasc aleatoriu dintr-un punct de plecare și lasă un traseu de parfum, care construiește mai multe furnici care traversează o anumită cale. Dacă trimiteți (suficiente) furnici atât din punctul de început, cât și din punctele de sfârșit, atunci în cele din urmă calea cu cel mai puternic miros va fi cea mai scurtă. Acest lucru se datorează faptului că cel mai scurt drum va fi vizitat de mai multe ori într-o anumită perioadă de timp, dat fiind că furnicile se plimbă într-un ritm uniform.
EDIT @ Spikie
Ca o explicație suplimentară a modului de implementare a algoritmului de iaz - sunt evidențiate potențialele structuri de date necesare:
Va trebui să stocați harta ca rețea. Acesta este pur și simplu un set de nodes și edge între ele. Un set de nodes reprezintă un route . O margine se conectează la două noduri (poate la același nod) și are un cod cost asociat, cum ar fi distance sau time pentru a traversa marginea. O margine poate fi fie bidirecțională, fie unidirecțională. Probabil cel mai simplu este să aibă unități direcționale și să se dubleze pentru deplasarea în două direcții între noduri (adică o margine de la A la B și una diferită pentru B la A).
Ca exemplu, imaginați-vă trei stații de cale ferată aranjate într-un triunghi echilateral îndreptat în sus. Există și alte trei stații, fiecare la jumătatea distanței dintre ele. Marginile se alătură tuturor stațiilor adiacente împreună, diagrama finală va avea un triunghi inversat așezat în triunghiul mai mare.
Etichete noduri începând din stânga jos, mergând din stânga spre dreapta și în sus, ca A, B, C, D, E, F (F în partea de sus).
Presupunem că marginile pot fi traversate în ambele direcții. Fiecare margine are un cost de 1 km.
Ok, așa că dorim să călătorim din stânga jos A spre stația de sus F. Există multe căi posibile, inclusiv cele care se dublează înapoi pe ele însele, de ex. ABCEBDEF.
Avem o rutină de spus, NextNode , care acceptă un nod și un cost și se solicită pentru fiecare nod în care poate călători.
În mod clar, dacă lăsăm această rutină de rulare, în cele din urmă vom descoperi toate căile, inclusiv cele care sunt potențial infinite în lungime (de exemplu, ABABABAB etc.). Oprim acest lucru, verificând valoarea cost . Ori de câte ori vizităm un nod care nu a fost vizitat înainte, am pus atât costul, cât și nodul de la care am venit, împotriva acelui nod. Dacă un nod a fost vizitat înainte de a verifica costul existent și dacă suntem mai ieftini, atunci actualizăm nodul și continuăm (recursul). Dacă suntem mai scumpe, atunci sărim peste nod. Dacă toate nodurile sunt sărite, atunci ieșim din rutină.
Dacă ne atingem nodul țintă, atunci ieșim și din rutină.
În acest fel toate rutele viabile sunt verificate, dar în mod crucial numai cele cu cel mai mic cost. Până la sfârșitul procesului, fiecare nod va avea cel mai mic cost pentru a ajunge la acel nod, inclusiv nodul țintă.
Pentru a obține traseul vom lucra înapoi de la nodul nostru țintă. Din moment ce am stocat nodul de la care am venit, împreună cu costul, noi pur și simplu să ne întoarcem construirea traseului. Pentru exemplul nostru vom ajunge la ceva de genul:
Node A - (Total) Cost 0 - From Node None
Node B - Cost 1 - From Node A
Node C - Cost 2 - From Node B
Node D - Cost 1 - From Node A
Node E - Cost 2 - From Node D / Cost 2 - From Node B (this is an exception as there is equal cost)
Node F - Cost 2 - From Node D
Deci, cel mai scurt traseu este ADF.