SMA* algoritmus
Az SMA* vagy Simplified Memory Bounded A* egy, az A* algoritmus alapján működő legrövidebb út algoritmus. Az SMA* fő előnye, hogy korlátozott memóriát használ, míg az A* algoritmushoz szükség lehet exponenciális memóriára. Az SMA* összes többi jellemzőjét az A*-tól örökli.
Folyamat
Mint az A*, a heurisztika szerint kibővíti a legígéretesebb ágakat. Amitől különbözik, hogy az SMA* olyan csomópontokat vág le, amelyek bővítése a vártnál kevésbé ígéretesnek bizonyul. Ez a megközelítés lehetővé teszi az algoritmus számára az ágak felfedezését és a backtracking használatát más ágak felfedezésére.
A csomópontok kibővítését és metszését a két érték megtartása vezérli minden csomóponjátra. Az
csomópont
értéke becsüli meg a cél elérésének költségeit azáltal, hogy egy utat választ az adott csomóponton keresztül. Minél alacsonyabb az érték, annál nagyobb a prioritás. Mint az A*-ban, ez az érték
, de ezt követően frissíti, hogy tükrözze ezen becslés változásait, amikor gyermekei kibővülnek. A teljesen kibővített csomópont
értéke legalább olyan nagy, mint utódai. Ezenkívül a csomópont tárolja a legjobb elfeledett utódjának
értékét. Ez az érték helyreáll, ha az elfelejtett utód a legígéretesebb utód.
Az első csomóponttól kezdve fenntartja az OPEN-t, lexikográfiailag értéke és mélység szerint rendezve. Amikor kiválaszt egy csomópontot a kibővítéshez, e sorrend szerint választja meg a legjobbat. Amikor kiválaszt egy csomópontot a metszésre, akkor a legrosszabbat választja.
Tulajdonságok
Az SMA* a következő tulajdonságokkal rendelkezik:
- Heurisztikusan működik, csakúgy, mint az A*
- Teljes, ha az engedélyezett memória elég magas ahhoz, hogy a legkisebb megoldást tárolja
- Optimális, ha az engedélyezett memória elég magas ahhoz, hogy a legkisebb optimális megoldást tárolja, különben a legjobb megoldást adja vissza, amely belefér az engedélyezett memóriába.
- Elkerüli az ismétlődő állapotokat, mindaddig, amíg a memória megkötése lehetővé teszi
- Az összes rendelkezésre álló memóriát felhasználja
- Az algoritmus memóriatartományának kibővítése csak a számítás gyorsítását eredményezheti
- Ha elegendő memória áll rendelkezésre a teljes keresési fa tárolására, akkor a számításnak optimális sebessége van
Implementáció
Az SMA* megvalósítása nagyon hasonlít az A* alkalmazásához, az egyetlen különbség az, hogy ha nincs szabad hely, akkor a legnagyobb f-költségű csomópontokat kiteszik a sorból. Mivel ezeket a csomópontokat törli, az SMA*-nak meg kell jegyeznie a szülőcsomóponttal a legjobban elfeledett gyermek f-költségét. Amikor úgy tűnik, hogy az összes felfedezett útvonal rosszabb, mint egy ilyen elfeledett útvonal, az útvonal újragenerálódik.[1]
Pszeudokód:
function SMA-star(problem): path queue: set of nodes, ordered by f-cost;begin queue.insert(problem.root-node); while True do begin if queue.empty() then return failure; //there is no solution that fits in the given memory node := queue.begin(); // min-f-cost-node if problem.is-goal(node) then return success; s := next-successor(node) if !problem.is-goal(s) && depth(s) == max_depth then f(s) := inf; // there is no memory left to go past s, so the entire path is useless else f(s) := max(f(node), g(s) + h(s)); // f-value of the successor is the maximum of // f-value of the parent and // heuristic of the successor + path length to the successor endif if no more successors then update f-cost of node and those of its ancestors if needed if node.successors ⊆ queue then queue.remove(node); // all children have already been added to the queue via a shorter way if memory is full then begin badNode := shallowest node with highest f-cost; for parent in badNode.parents do begin parent.successors.remove(badNode); if needed then queue.insert(parent); endfor endif queue.insert(s); endwhileend
Fordítás
Ez a szócikk részben vagy egészben a SMA* című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.