AzSMA* vagySimplified Memory Bounded A* egy, azA* 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.

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 abacktracking 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${\displaystyle f}$ minden csomóponjátra. Az${\displaystyle x}$ csomópont${\displaystyle f(x)}$ é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${\displaystyle h(x)+g(x)}$, 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${\displaystyle f}$ értéke legalább olyan nagy, mint utódai. Ezenkívül a csomópont tárolja a legjobb elfeledett utódjának${\displaystyle f}$ é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${\displaystyle f}$ é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.

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

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:

functionSMA-star(problem):pathqueue:setofnodes,orderedbyf-cost;beginqueue.insert(problem.root-node);whileTruedobeginifqueue.empty()thenreturnfailure;//there is no solution that fits in the given memorynode:=queue.begin();// min-f-cost-nodeifproblem.is-goal(node)thenreturnsuccess;s:=next-successor(node)if!problem.is-goal(s)&&depth(s)==max_depththenf(s):=inf;// there is no memory left to go past s, so the entire path is uselesselsef(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 successorendififnomoresuccessorsthenupdatef-costofnodeandthoseofitsancestorsifneededifnode.successors⊆queuethenqueue.remove(node);// all children have already been added to the queue via a shorter wayifmemoryisfullthenbeginbadNode:=shallowestnodewithhighestf-cost;forparentinbadNode.parentsdobeginparent.successors.remove(badNode);ifneededthenqueue.insert(parent);endforendifqueue.insert(s);endwhileend

Ez a szócikk részben vagy egészben aSMA* című angol Wikipédia-szócikkezen 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.

• Gráfalgoritmusok