7/24/2019 Bsqueda Uniforme Costo

1/6

3.4.2 Bsqueda Costo-Uniforme

Cuando todos los costes de paso son iguales, bsqueda en amplitud esptima, ya que siempre expande el nodo ms superfcialno expandido.

Por una simple extensin, podemos encontrar un algoritmo que esptimo con cualquier funcin paso-costo. En lugar de expandir el nodoms supercial, la bsqueda de costo uniformeexpande el nodo ncon el costo de ruta ms bajo g(n).Esto se ace mediante elalmacenamiento de la frontera como una cola de prioridad ordenada porg. El algoritmo se muestra en la !igura ".#$.

Figura 3.14Bsqueda Costo Uniforme en un grafo. El algoritmo es idntico al algoritmo

grafo-bsqueda gen%ricaen la Figura 3.7, excepto por el uso de una cola de prioridady la adicin de una !erificacin extra en caso de que se descu"ra un camino m#s corto a un

estado fronteri$o. %a estructura de datos para rontiernecesita soportar la prue"a depertenencia eficiente, por lo que de"e com"inar las capacidades de una cola de prioridad y

una ta"la &as&.

7/24/2019 Bsqueda Uniforme Costo

2/6

Figura 3.15Una parte del espacio de estados 'umania,seleccionada para ilustrar la

"squeda de costo uniforme.

&dems de la orden de la cola por el costo de la ruta, ay otras dosdiferencias signicati'as de bsqueda en ancura. (a primera es que laprueba ob)eti'o se aplica a un nodo cuando este es seleccionado para laexpansin*como en el algoritmo grafo-bsqueda gen%rica que semuestra en la !igura ".+ en lugar de cuando este es primero generado.(a ran es que el primer nodo ob)eti'o que se generapuede ser en uncamino sub-ptimo. (a segunda diferencia es que se aade una pruebaen el caso de que un me)or camino se encontrado para un nodoactualmente en la frontera.&mbas de estas modicaciones entran en )uego en el e)emplo mostradoen la !igura ".#/, donde el problema es conseguir desde 0ibiu a1ucarest. (os sucesores de 0ibiu estn 2imnicu 3ilcea y !agaras, concostos 45 y 66, respecti'amente. El nodo de menor costo, 2imnicu3ilcea, se expande siguiente, aadiendo Pitesti con costo 45 7 6+ 8 #++.El nodo de menor costo es aora !agaras, por lo que es expandido,aadiendo 1ucarest con costo 66 7 9## 8 "#5. &ora un nodo ob)eti'ose a generado, pero la bsqueda de costo uniforme sigue adelante, laeleccin de Pitesti para la expansin y la adicin de un segundo camino a

1ucarest con un costo 4576+7#5# 8 9+4. &ora el algoritmo compruebapara 'er si este nue'o camino es me)or que el anterior: que es, por loque el 'ie)o se descarta. 1ucarest, aora con costo-g 9+4, se seleccionapara la expansin y se de'uel'e la solucin.Es fcil 'er que la bsqueda costo uniforme es ptima en general. Enprimer lugar, se obser'a que siempre que la bsqueda costo uniformeselecciona nodo n para expansin, la ruta ptima a ese nodo a sidoencontrada. *0i no fuera el caso, no tendr;a que ser otro nodo frontera n