IDA*
El método IDA* (Iterative Deepening A*) és un algoritme de busca en grafos creat per Korf en 1985. Este método combina la aprofundiment iterativa en una variant del Depth-First Search (DFS). L'idea central és utilisar informació heurística disponible per a decidir qué nodo explorar i fins a quin punt alvançar en cada cicle del procés.
En este algoritme, cada iteración s'assembla a una busca en profunditat, a on la profunditat està determinada per l'informació heurística. La busca es deté quan s'alcança un nodo el cost total del qual de la funció heurística d'evaluació f=g+h és major que el llímit de cost actual f. En cada iteración, es revisen els nodos en un cost de f menor o igual al llímit actual.
L'algoritme
Per a desenrollar IDA* s'utilisa el plantejament heurístic d'A* que té una forma de busca semblant al BFS i es combina en IDA*. S'incrementa en cada iteración no la profunditat de nivells sino el cost total del camí i en el comportament següent: "en cada iteración es realisarà un DFS que s'interromprà si el cost total (g + h) excedix una variable memòria donada. Esta memòria comença en el cost estimat del primer estat i s'incrementa per cada iteración del algoritme. En cada iteración la memòria que s'utilisa per a la pròxima iteración és el mínim dels costs de tots els valors superiors a la memòria actual”.[1] Explicant l'algoritme deu recalcar-se que seguix conservant-se la condició hˆ(n) ≤ h(n) per a que siga admissible hˆ(n). L'autor de IDA* ademés planteja que l'algoritme troba el camí òptim i que expandix el mateix número de nodos que A*. De lo abans expost es deu remarcar que A* realisa una busca BFS informada, mentres que IDA* realisa DFS.[2] A* crea arbres de busca menors ya que es beneficia d'usar un registre d'almagasenament en forma de llistes obertes i tancades, lo que no realisa IDA*. Açò comporta a que IDA* utilise menys espai de memòria en realisar les seues busques, i no gasta recursos en mantindre estes dos llistes. No obstant, el prescindir d'un almagasenament du en si fortes desventages.[3]
Limitantes
- No pot detectar estats repetits ya que no conta en un almagasenament d'estats visitats a diferència de A*.
- A* manté una frontera de busca per mig de la llista oberta a on s'almagasenen els estats visitats, lo que no pot realisar IDA*.
- A* utilisa com a frontera una llista ordenada expandint els nodos en un orde, mentres que IDA* té que utilisar una busca d'esquerra a dreta simple.
Referències
- ↑ Korf, Richard E.«Depth-first iterative-deepening».Artificial Intelligence.27(1): 97–109.doi:10.1016/0004-3702(85)90084-0.Consultat el 29 d'octubre de 2017.
- ↑ Mager Hois, Jesús Manuel(2015).«L'Algoritme Fringe Search com a solució superior a A* en la busca de camins sobre gràfics de malla.».UNAM.
- ↑ Björnsson, Yngvi; Enzenberger, Markus; Holte, Robert C.; Schaeffer, Jonathan(2005).«Fringe search: beating A* at pathfinding on game maps».In Proceedings of IEEE Symposium on Computational Intelligence and Games.: 125–132.Consultat el 29 d'octubre de 2017.
Referències
- Este artícul conté una traducció derivada de «IDA*» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.