Căutare margine

În informatică , căutarea marginală este un algoritm de căutare grafică care găsește calea cu cel mai mic cost de la un nod de început dat la un singur nod de destinație .

În esență, căutarea marginii este calea de mijloc între algoritmul de căutare A* și varianta de aprofundare iterativă A* ( IDA * [1] ).

Dacă g ( x ) este costul căii de căutare de la primul nod la cel curent și h ( x ) este euristica costului de la nodul curent la țintă, atunci ƒ ( x ) = g ( x ) + h ( x ) este costul real al căii către obiective. Luați în considerare un IDA* care efectuează o căutare recursivă de la stânga la dreapta adâncime-prim de la nodul rădăcină, oprind recursiunea de îndată ce ținta este găsită sau nodurile ating valoarea lor maximă ƒ . Dacă ținta nu este găsită la prima iterație a lui ƒ , iterația este apoi incrementată și algoritmul caută din nou. Adică se repetă în iterații.

IDA* are trei dezavantaje majore. În primul rând, IDA* va repeta stările când există mai multe căi (uneori sub-optimale) către nodul țintă - acest lucru este adesea rezolvat prin menținerea unui cache de stări vizitate. Un IDA* modificat în acest fel este denumit IDA* cu memorie extinsă ( ME-IDA* [2] ) deoarece folosește o anumită memorie. În plus, IDA* repetă toate căutările anterioare iar și iar, ceea ce este necesar pentru a funcționa fără stocare. Prin păstrarea nodurilor frunze din iterația anterioară și folosindu-le ca poziție de pornire a următoarei, eficiența IDA* este mult îmbunătățită (altfel ar trebui să viziteze întotdeauna fiecare nod din arbore în ultima iterație).

Căutarea Edge implementează aceste îmbunătățiri în IDA* folosind o structură de date constând din mai mult sau mai puțin două liste pentru a itera peste granița sau marginea arborelui de căutare. O listă „acum” stochează iterația curentă, iar cealaltă listă „mai târziu” stochează cea mai apropiată iterație următoare. Astfel, nodul rădăcină al arborelui de căutare „acum” este rădăcina, iar „mai târziu” este gol. Algoritmul face apoi unul din două lucruri: dacă ƒ ( head ) este mai mare decât valoarea pragului, elimină capul din „acum” și îl adaugă la sfârșitul lui „mai târziu” , adică salvează capul pentru următoarea iterație. În caz contrar, dacă ƒ ( cap ) este mai mic sau egal cu pragul, desfășoară și aruncă capul , ia în considerare descendenții săi, adăugându-i la începutul „acum” . La sfârșitul iterației, pragul este incrementat, lista „mai târziu” devine lista „acum” și este golită.

O diferență importantă între edge-searching și A* este că conținutul listelor din edge-search nu trebuie să fie sortat - un câștig semnificativ față de A* , care necesită menținerea adesea costisitoare a ordinii în lista deschisă. Totuși , căutarea marginii va trebui să viziteze, spre deosebire de A* , aceleași noduri în mod repetat, dar costul fiecărei astfel de vizite este constant în comparație cu timpul de sortare logaritmică a listei din A* în cel mai rău caz.

Pseudocod

Implementarea ambelor liste într-o singură listă dublu legată, unde nodurile care preced nodul curent sunt partea „mai târziu” și orice altceva este lista „acum” . Prin utilizarea unei matrice de noduri prealocate în listă pentru fiecare nod din grilă, timpul de acces la nodurile din listă este redus la o constantă. În mod similar, o serie de markeri vă permite să căutați un nod într-o listă în timp constant. g este stocat ca tabel hash , iar ultimul tablou de token este stocat pentru a căuta constant dacă nodul a fost vizitat anterior și dacă intrarea în cache este validă .