Anar al contingut

Busca per franges

De L'Enciclopèdia, la wikipedia en valencià
Una llista despuix, ara (later, now) en les seues tres busques, un cap a l'inici de la llista, un atre cap al nodo actual a analisar i una al final. La funció Gamma evalua els veïns del cap i als nodos prometedors els inserta en now, mentres que als poc prometedores a l'inici de la llista, en el camp later.

En ciències de la computació, la busca per franges (fringe search en anglés) és un algoritme heurístic de busca sobre grafos, creat per Böjrnsson, Enzenberger, Holte i Schaeffer, que troba una ruta des d'un nodo inicial dau a un nodo objectiu. La busca per franges és un punt mig entre A* i la variant de aprofundiment iterativa A* (IDA*).

Descripció de l'Algoritme

L'algoritme requerix dos taules hash per a guardar g*(n) i h*(n), a on g*(n) és el cost del camí des de l'orige fins al nodo actual i h(n) és el cost estimat del nodo actual al destí. Per a cada nodo visitat es guardarà este valor en l'objectiu de mantindre una memòria per a millorar l'estimació del millor camí. El cost de consultar cada nodo és reduït, ya que la complexitat d'una busca en una taula hash és d'O(1). També es requerix una llista now-later la qual és una llista doblement lligada en tres busques: un cap al nodo inicial, un atre al nodo actual i un al nodo final. També s'utilisa una variable de portal que permetrà classificar als nous nodos en potencialment bons o mals. En estes estructures itera sobre la llista, a on la capçalera estarà a l'inici de la llista. Es recorre tota la llista, pero únicament s'expandix els nodos veïns al nodo que és el seu cost estiga per dalt de la variable portal. L'expansió es fa en la llista now (posterior al punter capçalera). Quan la llista es finalisa i no s'ha trobat al nodo objectiu, es torna a escomençar des de l'inici.

Per a estimar costs s'utilisa heurístiques, a on f*(n) és el cost estimat del nodo actual des del camí més curt des de l'inici al fi passant per n. Este es compon per: g(n) és el cost de la ruta de busca des del primer nodo a l'actual, i h*(n) és l'estimació heurística del cost des del nodo actual a l'objectiu. La suma f*(x) = g*(x) + h*(x), és el cost de la ruta estimada al nodo objectiu. Esta és major o igual a f(n) que és el cost del camí òptim.

Diferències en A* i IDA*

Considere IDA*, que fa una busca recursiva d'esquerra a dreta primer en profunditat des del nodo raïl, detenint la recursividad una volta que l'objectiu s'ha trobat o els nodos han alcançat un màxim valor ƒ. Si cap objectiu es troba en el primer llindar f, este s'incrementa i l'algoritme busca de nou, és dir, itera sobre el llindar.

IDA* presenta tres grans ineficiències: En primer lloc, IDA* repetirà estats quan existixen múltiples (a voltes no òptims) camins a un nodo objectiu - açò a sovint es resol mantenint una caché dels estats visitats. IDA* d'esta manera alterat es denota com a memòria- millorada IDA* (ME-IDA*), ya que utilisa algun grau d'almagasenament. Ademés, IDA* repetix totes les operacions prèvies en una busca quan es itera en un nou llindar, lo que és necessari quan s'opera sense almagasenament. Per mig de l'almagasenament dels nodos full d'una iteración anterior i el seu us com a nodos de partida de la següent, l'eficiència de IDA * s'incrementa significativament (de lo contrari, en l'última iteración sempre es tindria que visitar cada nodo en l'arbre).


Busca per Franges implementa estes millores en IDA*, fent us d'una estructura de senyes que consistix, essencialment, en dos llistes per a iterar sobre la frontera o franja de l'arbre de busca. Una llista ara almagasena la iteración actual i l'atra llista despuix la iteración que li seguix de manera immediata. D'esta forma, des del nodo raïl de l'arbre de busca, ara serà la raïl i despuix estarà buida. A continuació, l'algoritme pren una de dos accions: Si ƒ (cap) és major que el llindar actual, s'elimina el cap de la llista ara i s'afig al final de la llista despuix; és dir, es guarda el cap per a la següent iteración. De lo contrari, si ƒ (cap) és menor o igual al llindar, s'expandix el cap i posteriorment es descarta (afegint els seus nodos fills al començ de la llista ara). Al final d'una iteración s'incrementa el llindar, la llista ara passa a ser l'anterior llista despuix, i la llista despuix es buida.

Una diferència important entre la Busca per Franges i A* és que el contingut de les llistes en la primera no necessàriament té que estar ordenat - una ventaja sobre A*, que requerix el, a sovint, costós manteniment d'orde en la seua llista oberta. No obstant, a diferència de A*, la Busca per Franges tindrà que visitar els mateixos nodos en vàries ocasions pero, inclús aixina, el cost de cada visita és constant en comparació al temps logarítmic que invertix A*, en el pijor dels casos, per a ordenar la llista.

No obstant, a pesar de ser no utilisar una llista ordenada de nodos la millora en el temps promig d'eixecució no disminuïx de manera dràstica, ni representa una diminución de la complexitat de A*. Per l'atre costat, la Busca per Franges no garantisa un camí òptim en un espai euclidiano a diferència de A* que si ho garantisa.

Referències


Obtingut de «https://lenciclopedia.org/w/index.php?title=Busca_per_franges&oldid=1580479»