1

Albitres Cieza Manuel Rodrigo, Luis Bacilio Cesar Alberto

Algoritmos de búsqueda:Universidad
Informada y no
Nacional de Trujillo

Informada

 Encuentra la solución más “cercana” al estado
Resumen— inicial
En esta investigación se explorarán los diferentes algoritmos  Siempre encuentra una solución si esta existe
de búsqueda utilizados en inteligencia artificial (IA),
centrándose en las categorías de búsqueda informada y no
informada. La búsqueda es una técnica esencial en IA para
encontrar soluciones a problemas donde se necesita determinar A.3. Ejemplo de Búsqueda en Amplitud:
una secuencia de acciones desde un estado inicial hasta un estado Estado Inicial: A
objetivo. Estado Final: E

I. INTRODUCCIÓN

L a búsqueda es una herramienta fundamental en el campo

de la inteligencia artificial para resolver problemas
complejos que requieren encontrar una secuencia óptima de
acciones desde un estado inicial hasta un estado objetivo. Los
algoritmos de búsqueda se dividen principalmente en dos Fig1. Primer y segundo nivel.
categorías: informados y no informados. Los algoritmos de
búsqueda no informada, o ciega, operan sin información
adicional sobre la meta, explorando el espacio de búsqueda de
manera sistemática, pero a menudo ineficiente. En contraste,
los algoritmos de búsqueda informada utilizan heurísticas
para guiar la búsqueda de manera más eficiente hacia la
solución.

II. BÚSQUEDA NO INFORMADA Fig2. Tercer nivel.

La búsqueda no informada, conocida también como
búsqueda ciega, se refiere a una estrategia en el campo de la
Inteligencia Artificial que consiste en explorar posibles
soluciones sin tener en cuenta la ubicación exacta del
objetivo. Estos algoritmos recorren el espacio de búsqueda de
manera metódica, prescindiendo de heurísticas o estimaciones
concretas sobre el problema o la meta a alcanzar. Ejemplos
comunes son la búsqueda en amplitud y la búsqueda en
profundidad. Fig3. Hallazgo de una solución.

A. Búsqueda en Amplitud En la implementación se debe evitar la evaluación de estados

repetidos (Fig2). cada vértice generado se debe evaluar para
La búsqueda en amplitud es una estrategia de búsqueda en
determinar si corresponde a un estado solución. Cada vértice
inteligencia artificial que explora sistemáticamente todos los
generado se debe evaluar para determinar si corresponde a un
nodos vecinos de un estado inicial antes de pasar a los nodos
estado solución (Fig3).
de nivel siguiente. Este enfoque se utiliza para encontrar
soluciones en un espacio de estados donde todas las
transiciones tienen el mismo costo. Es completa y garantiza
encontrar la solución más cercana en términos de cantidad de
pasos, aunque puede requerir una cantidad significativa de
A.4. Algoritmo:
memoria.
a) Inicializar la cola y los nodos visitados
 Crear una cola vacía (FIFO).
 Crear un conjunto vacío para almacenar nodos
A.1. Características: visitados.
 Requiere gran Memoria a medida que se expanden  Insertar el nodo inicial en la cola
los nodos, especialmente en espacios de búsqueda  Marcar el nodo inicial como visitado
grandes o con muchos estados. b) Proceso de búsqueda

INTELIGENCIA ARTIFICIAL 1  Mientras la cola no esté vacía:
 2

 Extraer el nodo en la parte frontal de la cola  AÑADIR: Se marca el vecino como

(nodo actual) visitado.
 Si el nodo actual es el objetivo:  ENCOLAR: Se inserta el vecino en la cola.
 Devolver el camino desde el nodo inicial 3. Finalización
hasta el nodo objetivo
 De lo contrario, para cada vecino no visitado  DEVOLVER None: Si la cola se vacía sin haber
del nodo actual: encontrado el objetivo, se devuelve una indicación
 Marcar al vecino como visitado de que no se encontró.
 Insertar al vecino en la cola
c) Finalizar la búsqueda
B. Búsqueda en Profundidad
 Si la cola se vacía sin encontrar el objetivo:
 Devolver una indicación de que no se encontró La búsqueda en profundidad es una estrategia de búsqueda
el objetivo. en inteligencia artificial que explora las ramas de un árbol de
búsqueda de manera exhaustiva, yendo tan profundamente
A.5. Pseudocódigo del Algoritmo: como sea posible antes de retroceder y explorar otras ramas.
Este enfoque se utiliza para encontrar soluciones en un
espacio de estados y es especialmente útil cuando la solución
ALGORITMO (grafo, nodo_inicial, objetivo)
COLA ← nueva cola vacía se encuentra en una rama profunda del árbol de búsqueda.
VISITADOS ← nuevo conjunto vacío
ENCOLAR(COLA, nodo_inicial) B.1. Características
AÑADIR(VISITADOS, nodo_inicial)
 No garantiza que encontrará la solución óptima
MIENTRAS COLA no esté vacía HACER  la búsqueda en profundidad utiliza menos memoria
nodo_actual ← DESENCOLAR(COLA)
porque solo necesita almacenar la ruta desde la raíz
SI nodo_actual = objetivo ENTONCES hasta el nodo actual
DEVOLVER camino desde nodo_inicial hasta  La búsqueda en profundidad explora
nodo_actual exhaustivamente las ramas del árbol de búsqueda

PARA cada vecino EN vecinos(nodo_actual) HACER

SI vecino NO está en VISITADOS ENTONCES
AÑADIR(VISITADOS, vecino)
ENCOLAR(COLA, vecino)
FIN SI
FIN PARA
FIN MIENTRAS

DEVOLVER (None: una indicación de que no se Fig4. Árbol de búsqueda en profundidad.

encontró el objetivo)
FIN ALGORITMO B.2. Complejidad

Descripción del Pseudocódigo

1. Inicialización
 COLA: Se crea una cola vacía para manejar los
nodos a explorar.
 VISITADOS: Se crea un conjunto vacío para
rastrear los nodos visitados.
 ENCOLAR: Se inserta el nodo inicial en la cola.
 AÑADIR: Se marca el nodo inicial como visitado.
2. Bucle Principal
 MIENTRAS COLA no esté vacía: Se repite el Fig5. Complejidad búsqueda en profundidad
proceso mientras haya nodos en la cola. Complejidad en instrucciones [5], crece como una potencia
 DESENCOLAR: Se extrae el nodo al frente de la del factor de ramificación, con exponente igual a la máxima
cola. distancia entre dos nodos en el espacio de estados En
 SI nodo_actual = objetivo: Si el nodo extraído es el contraposición, la complejidad en memoria es de O(b × m).
objetivo, se devuelve el camino encontrado.
 PARA cada vecino EN vecinos(nodo_actual): Se B.3. Algoritmo
exploran todos los vecinos del nodo actual.
 SI vecino NO está en VISITADOS: Si el vecino a) Inicialización
no ha sido visitado, se realiza lo siguiente:  Crear una pila vacía.
 3

 Crear un conjunto vacío para nodos visitados.  AÑADIR: Se marca el vecino como
 Insertar el nodo inicial en la pila. visitado.
 Marcar el nodo inicial como visitado.  APILAR: Se inserta el vecino en la pila.
b) Proceso de búsqueda 3. Finalización
 Mientras la pila no esté vacía:  DEVOLVER None: Si la pila se vacía sin haber
 Extraer el nodo en la parte superior de la pila. encontrado el objetivo, se devuelve una indicación
 Si el nodo actual es el objetivo: de que no se encontró.
 Detener la búsqueda y devolver el camino
encontrado. C. Búsqueda Por Costo Uniforme
 Para cada vecino no visitado del nodo actual:
 Marcar el vecino como visitado. La búsqueda de costo uniforme es una estrategia de
 Insertar el vecino en la pila. búsqueda que explora un espacio de estados expandiendo los
c) Finalización nodos con el costo acumulado más bajo desde el nodo inicial.
 Si la pila se vacía sin encontrar el objetivo: A diferencia de la búsqueda en amplitud, donde se prioriza la
 Indicar que el objetivo no se encontró. expansión de nodos según su profundidad, la búsqueda de
costo uniforme prioriza nodos en función del costo total
B.4. Pseudocódigo del Algoritmo acumulado para alcanzarlos. Esto permite encontrar la
solución con el menor costo posible en términos de la suma
ALGORITMO (grafo, nodo_inicial, objetivo) de los costos de las acciones tomadas para llegar a la
PILA ← nueva pila vacía solución.
VISITADOS ← nuevo conjunto vacío
APILAR(PILA, nodo_inicial) C.1. Características.
AÑADIR(VISITADOS, nodo_inicial)
 Garantiza alcanzar el estado objetivo.
 brinda una solución óptima de costo de ruta para la
MIENTRAS PILA no esté vacía HACER
nodo_actual ← DESAPILAR(PILA) búsqueda si el problema se define sobre los costos
de las transiciones.
SI nodo_actual = objetivo ENTONCES  La complejidad de instrucciones y memoria de la
DEVOLVER camino desde nodo_inicial hasta búsqueda de costo uniforme es:
nodo_actual

PARA cada vecino EN vecinos(nodo_actual) HACER

SI vecino NO está en VISITADOS ENTONCES
AÑADIR(VISITADOS, vecino)
APILAR(PILA, vecino)
FIN SI
FIN PARA
FIN MIENTRAS

DEVOLVER (None: una indicación de que no se encontró el

objetivo

Descripción del Pseudocódigo

1. Inicialización Fig6. Árbol de búsqueda de costo uniforme.
 PILA: Se crea una pila vacía para manejar los
nodos a explorar.
 VISITADOS: Se crea un conjunto vacío para C.2. Algoritmo:
rastrear los nodos visitados. a) Inicialización
 APILAR: Se inserta el nodo inicial en la pila.  Crear una cola de prioridad vacía.
 AÑADIR: Se marca el nodo inicial como  Crear un conjunto vacío para nodos visitados.
visitado.  Insertar el nodo inicial en la cola de prioridad con
2. Bucle Principal un costo de 0.
 MIENTRAS PILA no esté vacía: Se repite el b) Proceso de búsqueda
proceso mientras haya nodos en la pila.  Mientras la cola de prioridad no esté vacía:
 DESAPILAR: Se extrae el nodo en la parte  Extraer el nodo con el costo acumulado más
superior de la pila. bajo de la cola de prioridad.
 SI nodo_actual = objetivo: Si el nodo extraído es  Si el nodo actual es el objetivo:
el objetivo, se devuelve el camino encontrado.  Detener la búsqueda y devolver el camino
 PARA cada vecino EN vecinos(nodo_actual): Se encontrado.
exploran todos los vecinos del nodo actual.  Si el nodo actual no ha sido visitado:
 SI vecino NO está en VISITADOS: Si el vecino  Marcar el nodo actual como visitado.
no ha sido visitado, se realiza lo siguiente:  Para cada vecino del nodo actual:
 4

 Calcular el costo total para alcanzar el  DESENCOLAR_PRIORIDAD: Se extrae el nodo

vecino. con el costo acumulado más bajo.
 Si el vecino no ha sido visitado o el  SI nodo_actual = objetivo: Si el nodo extraído es el
nuevo costo es menor que el costo objetivo, se devuelve el camino encontrado.
registrado anteriormente:  SI nodo_actual NO está en VISITADOS: Si el nodo
 Actualizar el costo del vecino. actual no ha sido visitado, se realiza lo siguiente:
 Insertar el vecino en la cola de  AÑADIR: Se marca el nodo actual como
prioridad con el nuevo costo visitado.
acumulado.  PARA cada (vecino, costo) EN
c) Finalización vecinos(nodo_actual): Se exploran todos los
 Si la cola de prioridad se vacía sin encontrar el vecinos del nodo actual.
objetivo:  costo_total: Se calcula el costo total para
 Indicar que el objetivo no se encontró. alcanzar el vecino.
 SI vecino NO está en VISITADOS O
[Link] del Algoritmo: costo_total < costo registrado para vecino: Si el
vecino no ha sido visitado o el nuevo costo es
ALGORITMO (grafo, nodo_inicial, objetivo) menor, se realiza lo siguiente:
COLA_PRIORIDAD ← nueva cola de prioridad vacía  actualizar costo registrado para vecino: Se
VISITADOS ← nuevo conjunto vacío
actualiza el costo registrado para el vecino.
ENCOLAR_PRIORIDAD(COLA_PRIORIDAD, nodo_inicial,
0)  ENCOLAR_PRIORIDAD: Se inserta el
vecino en la cola de prioridad con el nuevo
MIENTRAS COLA_PRIORIDAD no esté vacía HACER costo acumulado.
(costo_actual, nodo_actual) ← 3. Finalización
DESENCOLAR_PRIORIDAD(COLA_PRIORIDAD)  DEVOLVER None: Si la cola de prioridad se vacía
sin haber encontrado el objetivo, se devuelve una
SI nodo_actual = objetivo ENTONCES indicación de que no se encontró.
DEVOLVER camino desde nodo_inicial hasta
nodo_actual
II. BÚSQUEDA INFORMADA.
SI nodo_actual NO está en VISITADOS ENTONCES
AÑADIR(VISITADOS, nodo_actual)
La búsqueda informada, también conocida como búsqueda
PARA cada (vecino, costo) EN vecinos(nodo_actual) heurística, es una estrategia en inteligencia artificial que
HACER utiliza información adicional sobre el problema para guiar la
costo_total ← costo_actual + costo búsqueda hacia la solución de manera más eficiente. Esta
SI vecino NO está en VISITADOS O costo_total < información adicional se expresa generalmente en forma de
costo registrado para vecino ENTONCES
una función heurística que estima el costo restante desde un
actualizar costo registrado para vecino con
costo_total estado dado hasta el objetivo. Algoritmos como A* y la
ENCOLAR_PRIORIDAD (COLA_PRIORIDAD, búsqueda Voraz son ejemplos de búsqueda informada, donde
vecino, costo_total) se prioriza la expansión de nodos que parecen estar más cerca
FIN SI del objetivo según la información proporcionada por la
FIN PARA función heurística.
FIN SI
FIN MIENTRAS
C. Búsqueda Voraz
DEVOLVER (None: una indicación de que no se encontró el La búsqueda voraz, también conocida como búsqueda
Greedy, es una estrategia de búsqueda informada en
Descripción del Pseudocodigo: inteligencia artificial que prioriza la expansión de nodos que
parecen ser más prometedores según una función heurística.
1. Inicialización: En cada paso, elige el nodo que tiene el valor heurístico más
 COLA_PRIORIDAD: Se crea una cola de prioridad bajo, sin considerar los costos acumulados hasta ese punto.
vacía para manejar los nodos a explorar con sus Este enfoque tiende a ser rápido, pero no garantiza encontrar
costos acumulados. la solución óptima en todos los casos, ya que puede quedarse
 VISITADOS: Se crea un conjunto vacío para rastrear atrapado en óptimos locales.
los nodos visitados.
 ENCOLAR_PRIORIDAD: Se inserta el nodo inicial
en la cola de prioridad con un costo de 0. A.1. Características.
2. Bucle Principal  Los nodos se seleccionan en función de una función
 MIENTRAS COLA_PRIORIDAD no esté vacía: Se heurística que estima la distancia o costo hasta el
repite el proceso mientras haya nodos en la cola de objetivo, priorizando aquellos que parecen estar más
prioridad. cerca de la solución.}
 5

 La búsqueda voraz tiende a ser rápida debido a su

enfoque en la expansión de los nodos más
prometedores en cada paso, lo que la hace adecuada
para problemas donde se requiere una solución
rápida.
 Aunque la búsqueda voraz puede encontrar
soluciones rápidamente, no garantiza encontrar la
solución óptima global en todos los casos, ya que
puede quedar atrapada en óptimos locales y no Fig10. Estado final {I, J, E, D, F, G}
considera el costo total acumulado hasta el momento
de selección.
A.3. Algoritmo:
a) Inicialización
A.2. Ejemplo de Búsqueda Voraz  Crear una cola de prioridad vacía.
Encontrar rutas de S hasta I  Crear un conjunto vacío para nodos visitados.
 Insertar el nodo inicial en la cola de prioridad con
su valor heurístico.
b) Proceso de búsqueda
 Mientras la cola de prioridad no esté vacía:
 Extraer el nodo con el menor valor heurístico de
la cola de prioridad.
 Si el nodo actual es el objetivo:
 Detener la búsqueda y devolver el camino
encontrado.
 Si el nodo actual no ha sido visitado:
 Marcar el nodo actual como visitado.
 Para cada vecino del nodo actual:
 Si el vecino no ha sido visitado:
Figura 7. Árbol Inicial {A, C, B}  Insertar el vecino en la cola de
prioridad con su valor heurístico.
c) Finalización
 Si la cola de prioridad se vacía sin encontrar el
objetivo:
 Indicar que el objetivo no se encontró.

A.2. Pseudocodigo del algoritmo:

ALGORITMO Búsqueda_Voraz(grafo, nodo_inicial, objetivo,

heurística)
COLA_PRIORIDAD ← nueva cola de prioridad vacía
Fig8. La lista S ahora contiene VISITADOS ← nuevo conjunto vacío
ENCOLAR_PRIORIDAD(COLA_PRIORIDAD, nodo_inicial,
{C, B, E, D}
heurística[nodo_inicial])

MIENTRAS COLA_PRIORIDAD no esté vacía HACER

nodo_actual ←
DESENCOLAR_PRIORIDAD(COLA_PRIORIDAD)
SI nodo_actual = objetivo ENTONCES
DEVOLVER camino desde nodo_inicial hasta
nodo_actual
SI nodo_actual NO está en VISITADOS ENTONCES
AÑADIR(VISITADOS, nodo_actual)

PARA cada vecino EN vecinos(nodo_actual) HACER

SI vecino NO está en VISITADOS ENTONCES
ENCOLAR_PRIORIDAD(COLA_PRIORIDAD,
Fig9. La lista S ahora vecino, heurística[vecino])
contiene {H, E, D, F, G} FIN SI
FIN PARA
A.3. Descripción
FIN SI del Pseudocódigo
1. FIN
Inicialización
MIENTRAS

DEVOLVER (None: una indicación de que no se encontró el

objetivo)
FIN ALGORITMO
 6

 COLA_PRIORIDAD: Se crea una cola de prioridad  “Arriba” es aplicable a un estado si existe una casilla
vacía para manejar los nodos a explorar según su arriba y no está separada por barrera; el resultado de
valor heurístico. aplicarlo es la casilla de arriba y su coste es 1
 VISITADOS: Se crea un conjunto vacío para rastrear  El resto de operadores, análogamente
los nodos visitados.  Consideraremos que los sucesores están ordenados
 ENCOLAR_PRIORIDAD: Se inserta el nodo inicial alfabéticamente
en la cola de prioridad con su valor heurístico.
2. Bucle Principal
 MIENTRAS COLA_PRIORIDAD no esté vacía: Se
repite el proceso mientras haya nodos en la cola de
prioridad.
 DESENCOLAR_PRIORIDAD: Se extrae el nodo
con el menor valor heurístico.
 SI nodo_actual = objetivo: Si el nodo extraído es el
objetivo, se devuelve el camino encontrado.
 SI nodo_actual NO está en VISITADOS: Si el nodo Fig11. Problema del laberinto
actual no ha sido visitado, se realiza lo siguiente:
 AÑADIR: Se marca el nodo actual como visitado.
 PARA cada vecino EN vecinos(nodo_actual): Se
exploran todos los vecinos del nodo actual.
 SI vecino NO está en VISITADOS: Si el vecino no
ha sido visitado, se realiza lo siguiente:
 ENCOLAR_PRIORIDAD: Se inserta el vecino en
la cola de prioridad con su valor heurístico.
3. Finalización
 DEVOLVER None: Si la cola de prioridad se vacía
sin haber encontrado el objetivo, se devuelve una
indicación de que no se encontró.

D. Búsqueda A*
Fig12. Solución del laberinto
A* es un algoritmo de búsqueda informada utilizado en
inteligencia artificial para encontrar el camino más corto o la Solución encontrada: I-W-K-M-F
solución óptima en un espacio de estados. Utiliza una función  Óptima (heurística admisible)
de evaluación f(n)=g(n)+h(n), donde g(n) es el costo
 Nodos analizados: 8
acumulado desde el estado inicial hasta el nodo n y h(n) es
una heurística que estima el costo restante desde n hasta el  Aunque en este caso se analizan más nodos (se ha
objetivo. A* expande los nodos de manera que minimiza f(n), explorado parcialmente un camino equivocado), la
lo que permite encontrar una solución óptima si la heurística solución óptima está asegurada
es admisible (no sobreestima el costo real) y consistente  Nótese que se generan dos nodos distintos con el
(satisface la desigualdad de triangularidad). mismo estado K (pero distinto camino)

B.1. Características B.3. Algoritmo

 A* es óptimo si la heurística utilizada es admisible, a) Inicialización

es decir, nunca sobreestima el costo real para llegar  Crear una cola de prioridad vacía.
al objetivo. Esto significa que siempre encontrará el  Crear un conjunto vacío para nodos visitados.
camino más corto o el costo mínimo.  Crear un diccionario para almacenar los costos desde
 Es completo, lo que significa que siempre encontrará el nodo inicial a cada nodo.
una solución si existe una, asumiendo que el espacio  Crear un diccionario para almacenar los padres de
de búsqueda es finito y la heurística es consistente. cada nodo para reconstruir el camino.
 Insertar el nodo inicial en la cola de prioridad con un
B.2. Ejemplo de Búsqueda A* costo de 0.
 Establecer el costo del nodo inicial en el diccionario
Estados: A, B, C, D, E, G, I, W, K, M, N, P, Q, R, T y F • de costos como 0.
Estado inicial: I b) Proceso de búsqueda
Estado final: F  Mientras la cola de prioridad no esté vacía:
Operadores: arriba, abajo, izquierda, derecha  Extraer el nodo con el menor costo estimado
Aplicabilidad y resultado de la aplicación (costo actual + heurística) de la cola de prioridad.
 7

 Si el nodo actual es el objetivo: B.4. Descripción del Pseudocódigo

 Detener la búsqueda y devolver el camino 1. Inicialización
reconstruido.  COLA_PRIORIDAD: Se crea una cola de prioridad
 Si el nodo actual no ha sido visitado: vacía para manejar los nodos a explorar según su
 Marcar el nodo actual como visitado. costo estimado (costo actual + heurística).
 Para cada vecino del nodo actual:  VISITADOS: Se crea un conjunto vacío para rastrear
 Calcular el costo total para alcanzar el vecino. los nodos visitados.
 Si el vecino no ha sido visitado o el nuevo  COSTOS: Se crea un diccionario para almacenar los
costo es menor que el costo registrado costos acumulados desde el nodo inicial hasta cada
anteriormente: nodo, inicializado con valores infinitos por defecto.
 Actualizar el costo del vecino.  PADRES: Se crea un diccionario para almacenar el
 Establecer el nodo actual como padre del nodo padre de cada nodo.
vecino.  ENCOLAR_PRIORIDAD: Se inserta el nodo inicial
 Insertar el vecino en la cola de prioridad en la cola de prioridad con un costo de 0.
con el costo estimado (costo total +  ESTABLECER_COSTO: Se establece el costo del
heurística). nodo inicial como 0 en el diccionario de costos.
c) Finalización 2. Bucle Principal
 Si la cola de prioridad se vacía sin encontrar el  MIENTRAS COLA_PRIORIDAD no esté vacía: Se
objetivo: repite el proceso mientras haya nodos en la cola de
 Indicar que el objetivo no se encontró. prioridad.
 DESENCOLAR_PRIORIDAD: Se extrae el nodo
B.3. Pseudocodigo: con el menor costo estimado.
 SI nodo_actual = objetivo: Si el nodo extraído es el
ALGORITMO A*(grafo, nodo_inicial, objetivo, objetivo, se devuelve el camino reconstruido desde el
heurística) nodo inicial hasta el objetivo.
COLA_PRIORIDAD ← nueva cola de prioridad vacía  SI nodo_actual NO está en VISITADOS: Si el nodo
VISITADOS ← nuevo conjunto vacío actual no ha sido visitado, se realiza lo siguiente:
COSTOS ← nuevo diccionario con valor infinito por  AÑADIR: Se marca el nodo actual como visitado.
defecto  PARA cada (vecino, costo) EN
PADRES ← nuevo diccionario vacío vecinos(nodo_actual): Se exploran todos los
ENCOLAR_PRIORIDAD(COLA_PRIORIDAD,
vecinos del nodo actual.
nodo_inicial, 0)
ESTABLECER_COSTO(COSTOS, nodo_inicial, 0)
 costo_total: Se calcula el costo total para alcanzar
el vecino.
MIENTRAS COLA_PRIORIDAD no esté vacía HACER  SI vecino NO está en VISITADOS O costo_total
(costo_actual, nodo_actual) ← < COSTOS[vecino]: Si el vecino no ha sido
DESENCOLAR_PRIORIDAD(COLA_PRIORIDAD) visitado o el nuevo costo es menor, se realiza lo
siguiente:
SI nodo_actual = objetivo ENTONCES  ESTABLECER_COSTO: Se actualiza el costo
DEVOLVER reconstruir_camino(PADRES, acumulado del vecino en el diccionario de
nodo_inicial, objetivo) costos.
 ESTABLECER_PADRE: Se establece el nodo
SI nodo_actual NO está en VISITADOS ENTONCES
actual como padre del vecino en el diccionario
AÑADIR(VISITADOS, nodo_actual)
de padres.
PARA cada (vecino, costo) EN  ENCOLAR_PRIORIDAD: Se inserta el
vecinos(nodo_actual) HACER vecino en la cola de prioridad con el costo
costo_total ← costo_actual + costo estimado (costo total + heurística).
SI vecino NO está en VISITADOS O costo_total 3. Finalización
< COSTOS[vecino] ENTONCES  DEVOLVER None: Si la cola de prioridad se vacía
ESTABLECER_COSTO(COSTOS, vecino, sin haber encontrado el objetivo, se devuelve una
costo_total) indicación de que no se encontró.
ESTABLECER_PADRE(PADRES, vecino,
nodo_actual)
costo_estimado ← costo_total + E. Búsqueda BRPM
heurística[vecino]
La búsqueda BRPM (Branch and Bound, "Ramas y
ENCOLAR_PRIORIDAD(COLA_PRIORIDAD, vecino,
costo_estimado)
Acotación") es una técnica de optimización que busca
FIN SI soluciones óptimas en problemas combinatorios, dividiendo el
FIN PARA problema en subproblemas más pequeños y utilizando límites
FIN SI (cotas) para descartar aquellos que no pueden mejorar la
FIN MIENTRAS mejor solución encontrada hasta el momento.

DEVOLVER (None: es una indicación de que no se

encontró el objetivo)
 8

C.1 Características
 El problema principal se descompone en
subproblemas más manejables, formando una
estructura de árbol de posibles soluciones donde cada
nodo representa un subproblema con restricciones SI nodo_actual = objetivo ENTONCES
adicionales. MEJOR_COSTO ← costo_actual
 Se calcula una cota para cada subproblema que DEVOLVER reconstruir_camino(desde
representa el mejor valor posible que se puede nodo_inicial hasta nodo_actual)
obtener dentro de ese subproblema. Si la cota no
puede mejorar la mejor solución encontrada hasta el SI nodo_actual NO está en VISITADOS ENTONCES
momento, el subproblema se descarta. AÑADIR(VISITADOS, nodo_actual)
 El proceso de acotación permite eliminar
PARA cada (vecino, costo) EN
subproblemas no prometedores sin necesidad de
vecinos(nodo_actual) HACER
explorarlos exhaustivamente, reduciendo así el
costo_total ← costo_actual + costo
espacio de búsqueda y mejorando la eficiencia del SI vecino NO está en VISITADOS O costo_total
algoritmo. < COSTOS[vecino] ENTONCES
COSTOS[vecino] ← costo_total
costo_estimado_vecino ← costo_total +
C.2. Algoritmo heurística[vecino]
ENCOLAR_PRIORIDAD(COLA_PRIORIDAD,
a) Inicialización vecino, costo_estimado_vecino)
 Crear una cola de prioridad vacía. FIN SI
FIN PARA
 Crear un conjunto vacío para nodos visitados.
FIN SI
 Insertar el nodo inicial en la cola de prioridad con un FIN MIENTRAS
costo de 0 y su valor heurístico.
b) Proceso de búsqueda DEVOLVER (None: es una indicación de que no se
 Mientras la cola de prioridad no esté vacía: encontró el objetivo
 Extraer el nodo con el menor costo estimado FIN ALGORITMO
(costo actual + heurística) de la cola de prioridad.
 Si el nodo actual es el objetivo:
 Detener la búsqueda y devolver el camino C.4. Descripción del Pseudocódigo
encontrado.
 Si el nodo actual no ha sido visitado: 1. Inicialización
 Marcar el nodo actual como visitado.  COLA_PRIORIDAD: Se crea una cola de prioridad
 Para cada vecino del nodo actual: vacía para manejar los nodos a explorar según su
 Calcular el costo total para alcanzar el vecino. costo estimado (costo actual + heurística).
 Si el vecino no ha sido visitado o el nuevo  VISITADOS: Se crea un conjunto vacío para rastrear
costo es menor que el costo registrado los nodos visitados.
anteriormente:  MEJOR_COSTO: Se inicializa con un valor infinito
 Actualizar el costo del vecino. para rastrear el mejor costo encontrado.
 Insertar el vecino en la cola de  ENCOLAR_PRIORIDAD: Se inserta el nodo inicial
prioridad con el costo estimado (costo en la cola de prioridad con un costo de 0 más su
total + heurística). valor heurístico.
c) Poda  COSTOS: Se inicializa un diccionario para
 Si un nodo en la cola tiene un costo mayor que el almacenar los costos acumulados desde el nodo
menor costo encontrado hasta ahora: inicial hasta cada nodo.
 Ignorar ese nodo (podar). 2. Bucle Principal
d) Finalización  MIENTRAS COLA_PRIORIDAD no esté vacía: Se
 Si la cola de prioridad se vacía sin encontrar el repite el proceso mientras haya nodos en la cola de
objetivo: prioridad.
 Indicar que el objetivo no se encontró.  DESENCOLAR_PRIORIDAD: Se extrae el nodo
con el menor costo estimado.
C.3. Pseudocodigo  SI nodo_actual = objetivo: Si el nodo extraído es el
objetivo, se actualiza el mejor costo y se devuelve el
camino encontrado.
ALGORITMO BRPM(grafo, nodo_inicial, objetivo, heurística)
COLA_PRIORIDAD ← nueva cola de prioridad vacía  SI nodo_actual NO está en VISITADOS: Si el nodo
VISITADOS ← nuevo conjunto vacío actual no ha sido visitado, se realiza lo siguiente:
MEJOR_COSTO ← infinito  AÑADIR: Se marca el nodo actual como visitado.
ENCOLAR_PRIORIDAD(COLA_PRIORIDAD,
nodo_inicial, 0 + heurística[nodo_inicial])
COSTOS[nodo_inicial] ← 0

MIENTRAS COLA_PRIORIDAD no esté vacía HACER

(costo_estimado, nodo_actual) ←
DESENCOLAR_PRIORIDAD(COLA_PRIORIDAD)
costo_actual ← costo_estimado -
heurística[nodo_actual]
 9

 PARA cada (vecino, costo) EN Los algoritmos de búsqueda informada son generalmente
vecinos(nodo_actual): Se exploran todos los más eficientes que los no informados porque utilizan
vecinos del nodo actual. información heurística para guiar la búsqueda. Sin
 costo_total: Se calcula el costo total para alcanzar embargo, los algoritmos no informados son útiles cuando
el vecino. no se dispone de una heurística fiable.
 SI vecino NO está en VISITADOS O costo_total
< COSTOS[vecino]: Si el vecino no ha sido  Requerimientos de Información:
visitado o el nuevo costo es menor, se realiza lo Los algoritmos informados requieren una heurística bien
siguiente: diseñada y adecuada para ser efectivos. Sin una buena
 COSTOS[vecino]: Se actualiza el costo heurística, pueden perder su ventaja en eficiencia sobre
acumulado del vecino en el diccionario de los métodos no informados.
costos.
 ENCOLAR_PRIORIDAD: Se inserta el  Balance entre Recursos y Precisión:
vecino en la cola de prioridad con el costo La elección del algoritmo depende del balance entre la
estimado (costo total + heurística). precisión de la heurística y el coste computacional. Es
3. Poda esencial considerar las limitaciones de memoria y tiempo
 SI costo_actual > mejor_costo: Si un nodo en la cola de procesamiento, especialmente en aplicaciones
tiene un costo mayor que el mejor costo encontrado prácticas donde estos recursos pueden ser limitados.
hasta ahora, se ignora ese nodo.
4. Finalización
 DEVOLVER None: Si la cola de prioridad se vacía
sin haber encontrado el objetivo, se devuelve una
indicación de que no se encontró. REFERENCIAS

[1] Russell, S. y Norvig, P. Inteligencia artificial: Un enfoque moderno

(segunda edición) (Prentice Hall, 2004).

[2] Russell, S. y Norvig, P. Artificial Intelligence (A Modern Approach)

III. COMPARACIÓN DE TIPOS DE BÚSQUEDA (Prentice–Hall, 2010). Third Edition.

[3] J. L. Ruiz Reina, “Búsqueda informada mediante técnicas heurísticas”,

F. Cuadro Comparativo Sevilla, España.

[4] Hugo Franco, “Búsqueda No Informada”, 2002.

El cuadro compara tipos de búsqueda (informada y no
informada) en IA, destacando estrategia, memoria, [5] E. I. Benítez Guerrero, “Resolución de problemas mediante búsquedas”,
optimalidad, completitud y uso de heurística. 2010.

Tabla1. Cuadro comparativo

IV. CONCLUSIONES

 Eficiencia y Aplicabilidad: