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.