Universidad de Monterrey
SC-2150
Inteligencia Artificial
2. Procedimientos para la
Solución de Problemas
2.1
Solución de Problemas
Mediante la Búsqueda
Objetivo Particular:
Comprender cómo puede un agente encontrar
una secuencia de acciones que cumpla sus
metas, cuando ninguna acción individual lo
puede lograr.
Introducción
Los agentes reflejos sencillos basan sus
acciones en un mapeo directo de estados
a acciones.
 Dichos agentes no pueden operar bien en
ambientes en los cuales este mapeo sería
demasiado grande para almacenar y
tomaría demasiado tiempo para ser
aprendido.
 Los agentes basados en metas, por otra
parte, pueden tener éxito considerando
acciones futuras y deseabilidad de sus
salidas.

Introducción
Un agente para la solución de
problemas es un tipo de agente basado
en metas que determina secuencias de
acciones que le permiten obtener estados
deseables.
 Este tipo de agente utiliza algoritmos no
informados, en el sentido que no se les
proporciona otra información sobre el
problema más que su definición.

Agentes que resuelven
problemas
 Los
agentes inteligentes deben
actuar de manera que el entorno
experimente una serie de estados
tales que permitan un máximo de la
medida de rendimiento.
 El logro de este objetivo se simplifica
cuando el agente tiene una meta y
se esfuerza por lograrla.
Agentes que resuelven
problemas
Neamt
Oradea
Iasi
Zerind
Sibiu
ARAD
Timisoara
Lugoj
Rimnicu
Vilcea
Urziceni
Pitesti
BUCHAREST
Mehadia
Dobreta
Vaslui
Fagaras
Giurgiu
Craiova
Hirsova
Eforie
Agentes que resuelven
problemas
La formulación de metas es el primer
paso para la resolución de problemas.
 Se considera que las metas son conjuntos
de estados del mundo: solo aquellos que
permiten el logro de la meta.
 Se puede considerar que las acciones son
las causantes de la transición entre uno y
otro estado del mundo.

Agentes que resuelven
problemas
La formulación de un problema es el
procesos que consiste en decidir qué
acciones y estados habrán de considerarse
y es el paso que sigue a la formulación de
metas.
 Para el problema del viaje a través de
Rumania, se considera una estado el estar
en una ciudad determinada, y como
acción, el traslado de una ciudad a otra.

Agentes que resuelven
problemas


Cuando un agente tiene ante sí diversas opciones
inmediatas cuyo valor ignora, para decidir lo que
debe hacer primero tiene que evaluar las diversas
secuencias de acciones posibles que le conducen
a estados cuyo valor se conoce, y luego decidirse
por la mejor. A este proceso se le conoce como
búsqueda.
Una vez encontrada una solución, se procede a
ejecutar las acciones que ésta recomienda. A la
anterior se le denomina fase de ejecución.
Agentes que resuelven
problemas
Función Agente-sencillo-para-la-solución-de-problemas (p) responde con una
acción
entradas: p, una percepción
estática: s, una secuencia de acciones originalmente
vacía.
estado, una descripción del estado actual del
mundo.
g, una meta, originalmente nula.
problema, la formulación de un problema
estado  Actualizar-estado (estado, p)
si s está vacío entonces
g  Formular-meta (estado)
problema  Formular-el-problema (estado, g)
s  Buscar (problema)
acción  Recomendación (s, estado)
s  Resto (s, estado)
responder con acción
Agentes que resuelven
problemas

El agente recien descrito asume que el
ambiente es:
– Estático (formular y resolver el problema se
hace sin poner atención a los cambios que
podrían ocurrir en el ambiente).
– Observable (asume que el estado inicial es
conocido).
– Discreto (se pueden enumerar “cursos
alternativos de acción”).
– Determinístico (Las soluciones a los
problemas son simples secuencias de acciones,
no se pueden manejar eventos inesperados).
Problemas bien definidos y
soluciones
Un problema es un conjunto de
información que el agente utiliza para
decidir lo que va a hacer.
 Los elementos básicos para definir un
problema son:

–
–
–
–
Estado Inicial
Operadores
Prueba de Meta
Costo de Ruta
Problemas bien definidos y
soluciones
– Los operadores son las posibles acciones que
el agente puede emprender. La formulación
mas común usa una función de sucesor.
Dado un estado particular x, SUCCESOR-FN(x)
regresa un conjunto de pares ordenados
<acción, sucesor>
 SUCCESOR-FN(En(Arad))
–Z
{<Ir_a(Sibiu),En(Sibiu)>,
<Ir_a(Timisoara),En(Timisoara)>,
<Ir_a(Zerind),En(Zerind)>}
– Lo anterior define el espacio de estados, que
es el conjunto de todos los estados que
pueden alcanzarse a partir del estado inicial,
mediante una secuencia de operadores.
Problemas bien definidos y
soluciones
– Una ruta en el espacio de estados es
una secuencia de acciones que permite
pasar de un estado a otro.
Problemas bien definidos y
soluciones
La prueba de meta es la que el agente
aplica a la descripción de un solo estado
para decidir si se trata de un estado meta.
A veces se compara el estado actual con
un conjunto de estados meta, y otras, se
busca una propiedad.
 El costo de ruta es una función mediante
la que se asigna un costo a una ruta
determinada. El costo total es la suma de
todos los costos de cada una de las
acciones individuales a lo largo de una
ruta. Se denota como g.

Problemas bien definidos y
soluciones
 El
costo de paso de tomar la acción
a para ir del estado x al estado y se
denota por c(x,a,y).
 Los costos de paso para el problema
de Rumania son las distancias de
ruta. Se asumirá que los costos de
paso son no negativos.
Problemas bien definidos y
soluciones


El estado inicial, los operadores, la prueba de
meta y el costo de ruta son entradas para los
algoritmos de búsqueda. Su salida se denomina
solución, una ruta que va del estado final a
algún estado que cumpla la prueba de meta. Una
solución óptima tiene el menor costo de ruta de
todas las soluciones
Para problemas de estado múltiple, existe un
conjunto de estados iniciales, desde los cuales se
puede llegar a otro conjunto de estados. Se tiene
un espacio de conjuntos de estados.
Formulación de problemas
 El
verdadero arte de la solución de
problemas consiste en saber qué
decidir qué es lo que servirá para
describir estados y operadores y qué
no.
 El proceso de eliminación de detalles
de una representación se denomina
abstracción.
Problemas de Ejemplo

El enfoque de solución de problemas se ha
aplicado a una amplia gama de ambientes
de trabajo. Estos se pueden clasificar en:
– Problemas de “juguete”
 Empleados
para ejemplificar o ejercitar métodos para
la solución de problemas. Su naturaleza permite
describirlos de manera concisa y exacta.
– Problemas del mundo real
 Tienden
a ser más difíciles, su solución es importante
para alguien. Tienden a no tener una sola
caracterización que goce de consenso
Problemas de Ejemplo
Problemas de “Juguete”

Problema del mundo de la aspiradora:
–
–
–
–
–
En este mundo hay dos posibles ubicaciones.
En ellas puede o no haber mugre.
El agente se encuentra en una de las dos
El mundo puede asumir ocho posibles estados
Son tres las acciones posibles: A la izquierda,
A la derecha y Aspirar.
– Se puede suponer que la eficiencia del
aspirado es 100%
– La meta es eliminar toda la mugre.
Problemas de Ejemplo
Problemas de “Juguete”
Problema
del mundo de la aspiradora:
Problemas de Ejemplo
Problemas de “Juguete”

Problema del mundo de la aspiradora:
– Estados: El agente está en una de dos ubicaciones, cada
una de las cuales puede o no contener mugre. Por lo
tanto, puede haber 2 x 22 = 8 estados posibles del
mundo.
– Estado inicial: Cualquier estado puede ser designado
como estado inicial.
– Función de sucesor: Esto genera los estados legales que
resultan de intentar las tres acciones (izquierda, derecha
y aspirar).
– Prueba de Meta: Esto revisa si las dos ubicaciones están
limpias.
– Costo de ruta: Cada paso cuesta 1, así el costo de ruta
es el número de pasos en la ruta.
Problemas de Ejemplo
Problemas de “Juguete”
1
2
3
4
5
6
7
8
Problemas de Ejemplo
Problemas de “Juguete”
 El
juego de las ocho fichas
Problemas de Ejemplo
Problemas de “Juguete”

El juego de las ocho fichas
– Estados: Ubicación de cada una de las ocho placas en los
nueve cuadrados. Conviene incluir la ubicación del espacio
vacío.
– Estado inicial: Cualquier estado puede ser designado como
estado inicial. Note que cualquier meta dada puede ser
alcanzada desde exactamente la mitad de los estados iniciales
posibles.
– Función de sucesor: Esta genera los estados legales que
resultan de intentar las cuatro acciones (el espacio vacío
puede moverse a la izquierda, derecha, arriba y abajo).
– Prueba de meta: Verifica que el estado actual coincida con
un estado predefinido previamente como estado final.
– Costo de ruta: Cada paso cuesta 1, así que el costo de la ruta
corresponde a la longitud de la ruta.
Problemas de Ejemplo
Problemas de “Juguete”

El juego de las ocho fichas
– Abstracciones: Se ignoran las ubicaciones intermedias
cuando la ficha se está deslizando, si se tiene que
sacudir el tablero cuando las piezas se atoran, o si se
extraen las piezas con un cuchillo y se colocan de nuevo
en orden.
– El juego de las ocho fichas pertenece a la familia de
rompecabezas de piezas deslizantes, los cuales son
a menudo usados como problemas de prueba para
nuevos algoritmos de IA.
– Esta clase general es del tipo NP-completo.
– El juego de las ocho fichas tiene 9!/2 = 181,440 estados
alcanzables y es fácilmente solucionado.
Problemas de Ejemplo
Problemas de “Juguete”
 EL
problema de las ocho reinas
Problemas de Ejemplo
Problemas de “Juguete”

El problema de las ocho reinas
– Estados: cualquier disposición que tenga de 0
a 8 reinas en el tablero.
– Estado inicial: ninguna reina en el tablero.
– Función de sucesor: añadir una reina a un
cuadro vacío.
– Prueba de meta: 8 reinas en el tablero,
ninguna con posibilidad de atacar.
– Costo de ruta: cero
Problemas de Ejemplo
Problemas de “Juguete”


El problema de las ocho reinas (otras
formulaciones)
Formulación 2
– Estados: Disposiciones de 0 a 8 reinas, sin que se
pueda atacar ninguna de ellas
– Función de Sucesor: Poner una reina en la columna
vacía del extremo izquierdo de manera que ninguna otra
reina la pueda atacar.

Formulación 3
– Estados: Disposiciones de 8 reinas, una en cada
columna.
– Función de sucesor: Cambiar las reinas que puedan
ser atacadas a otro cuadro de la misma columna.
Problemas de Ejemplo
Problemas de “Juguete”
 Criptoaritmética
FORTY
+ TEN
+ TEN
--------SIXTY
2976
+ 850
+ 850
--------31486
Problemas de Ejemplo
Problemas de “Juguete”

Criptoaritmética
– Estados: Un problema de criptoaritmética en el que
algunas letras están reemplazadas con dígitos.
– Estado inicial: Ninguna letra ha sido reemplazada por
algún dígito.
– Función de sucesor: Reemplazar todas las veces que
aparezca una letra con un dígito que no haya aparecido
en el problema.
– Prueba de meta: Si en el problema sólo hay dígitos y
representan una suma correcta
– Costo de la ruta: Cero. Todas las soluciones son
igualmente válidas.
Problemas de Ejemplo
Problemas de “Juguete”

Misioneros y Caníbales
– 3 misioneros y tres caníbales salen a pasear a
la selva, y necesitan cruzar el río. Hay un bote,
pero este sólo puede llevar a una o dos
personas. Encuentre la manera de cruzar a
todos, evitando que el número de caníbales
sea superior al número de misioneros.
– ¿Cuáles son los Estados, Estado inicial, Función
de Sucesor, Prueba de Meta, Costo de Ruta?
Problemas de Ejemplo
Problemas de “Juguete”

El problema de la jarra de agua
– Supón que tienes 2 tarros, uno de 4 galones, y
otro de 3. Y no tienen ninguna marca de
medición en éstos. Hay una bomba que puede
ser usada para llenar los tarros con agua.
¿Cómo se puede llenar con exactamente 2
galones de agua, el tarro de 4 galones?
– ¿Cuáles son los Estados, Estado inicial, Función
de Sucesor, Prueba de Meta, Costo de Ruta?
Problemas de Ejemplo
Problemas Reales

Determinación de una ruta
– Consiste en definir una ruta en función de la
especificación de ubicaciones y las transiciones
mediante los vínculos que relacionan una y
otra ubicación.
– Los algoritmos que resuelven estos problemas
se usan en ruteo de redes de cómputo,
sistemas automatizados de asesores de viajes,
sistemas para planificación de viajes aéreos,
bonificaciones a viajeros frecuentes, etc.
Problemas de Ejemplo
Problemas Reales

Determinación de una ruta
– Problema de determinar una ruta aérea





Estados: Cada uno es representado por un aeropuerto y la
hora actual.
Estado inicial: Es especificado por el problema.
Función de sucesor: Regresa los estados resultantes de
tomar cualquier vuelo programado, que sale después de la
hora actual, más el tiempo de vuelo entre aeropuertos,
desde el aeropuerto actual a otro.
Prueba de meta: Verifica si estamos en el destino a una
hora pre-especificada.
Costo de ruta: Depende del costo monetario, el tiempo de
espera, el tiempo de vuelo, procedimientos de migración,
calidad de asiento, hora del día, tipo de avión,
bonificaciones por viajes frecuentes, etc.
Problemas de Ejemplo
Problemas Reales

Problema del agente viajero
– “Visitar todas las ciudades importantes de Rumania por
lo menos una vez, comenzando y terminando en
Bucarest”
– Este problema es un “Touring Problem”: requiere más
información sobre el espacio de estados. Además de la
ubicación del agente, un registro de las ciudades
visitadas.
– La prueba de meta consistiría en verificar si el agente
está en Bucarest y se han visitado todas las ciudades
UNA SOLA VEZ.
– El objetivo es determinar cuál es el recorrido más corto,
es un problema de complejidad NP.
– Los algoritmos que lo resuelven también se aplican para
tareas tales como planeación de movimientos de
taladros automáticos para circuitos impresos.
Problemas de Ejemplo
Problemas Reales

Distribución de componentes en circuitos
VLSI
– Es una de las tareas más complejas de diseño
en la ingeniería actual.
– El objetivo es colocar los miles de compuertas
del circuito integrado de tal manera que no se
encimen y ocupando un mínimo de área y de
longitud de conexiones, con el fin de obtener
un máximo de velocidad.
Problemas de Ejemplo
Problemas Reales
 Navegación
de robots
– Es una generalización del problema de
la determinación de ruta: en vez de
hacerlo en un espacio discreto, ahora es
continuo.
– Las acciones y estados posibles son (en
principio) infinitos.
– Este problema puede ser bi o
tridimensional.
Problemas de Ejemplo
Problemas Reales
 Secuencia
de ensamble
– En este problema, la dificultad radica en
determinar la secuencia adecuada para
el ensamble de las partes de un objeto
determinado.
– Si se elige un orden equivocado,
algunas partes ya no se podrán agregar.
Problemas de Ejemplo
Problemas Reales
 Secuencia
de ensamble
– En este problema, la dificultad radica en
determinar la secuencia adecuada para
el ensamble de las partes de un objeto
determinado.
– Si se elige un orden equivocado,
algunas partes ya no se podrán agregar.
Problemas de Ejemplo
Problemas Reales

Búsqueda en Internet
– En años recientes se ha incrementado la
demanda por robots de software que busquen
en Internet por respuestas a preguntas,
información relacionada, o para opciones de
compra.
– Ésta es una buena aplicación para técnicas de
búsqueda, porque es fácil conceptualizar la
Internet como un grafo con nodos (páginas)
conectadas por enlaces.
Búsqueda de Soluciones
 Después
de definir un problema e
identificar una solución, se prosigue
con la búsqueda de la solución.
 La búsqueda se hace en el espacio
de estados, y la idea es mantener y
ampliar un conjunto de secuencias
de solución parciales.
Generación de secuencias de
acciones
 Primero,
conviene evaluar el estado
inicial para determinar si es un
estado meta.
 Al aplicar los operadores a un estado
determinado, se genera un conjunto
de estados.
 Al proceso anterior se le llama
expansión del estado.
Generación de secuencias de
acciones
 Si
hay varios estados que se pueden
expandir, la elección del que se
expanderá primero se hace con una
estrategia de búsqueda.
 Conviene concebir el proceso de
búsqueda como la construcción de
un árbol de búsqueda sobrepuesto
al espacio de estados.
Generación de secuencias de
acciones
 La
raíz del árbol de búsqueda es el
nodo de búsqueda y corresponde
al estado inicial
 Los nodos hoja del árbol de
búsqueda o no tienen sucesores o no
se han expandido, o al expandirlos
generaron un conjunto vacío
Generación de secuencias de
acciones
 Estado
inicial
Arad
Generación de secuencias de
acciones
 Después
de expandir Arad
Arad
Sibiu
Timisoara
Zerind
Generación de secuencias de
acciones
 Después
de expandir Sibiu
Arad
Sibiu
Arad
Fagaras
Timisoara
Oradea
Zerind
Rimnicu Vilcea
Algoritmo General de Búsqueda
Función búsqueda-general (problema, estrategia) produce una
solución, o falla
inicializa el árbol de búsqueda empleando el estado inicial del
problema
ciclo hacer
si no hay candidatos para la expansión, responder con
falla
escoger un nodo hoja para hacer la expansión, de conformidad con la estrategia
si el nodo contiene un estado meta, responder con la
solución respectiva
o bien expanda el nodo y añada los nodos resultantes al
árbol de búsqueda
fin
Estructuras de datos para los
árboles de búsqueda

Un nodo es una estructura de datos con
cinco componentes:
– El estado en el espacio de estados al que
corresponda el nodo
– El nodo del árbol de búsqueda que generó este
nodo (nodo padre)
– El operador que se aplicó al generar el nodo
– Cuántos nodos de la ruta hay desde la raíz
hasta dicho nodo (profundidad)
– El costo de la ruta desde el estado inicial al
nodo
Estructuras de datos para los
árboles de búsqueda
El margen o frontera es el grupo de
nodos que están en espera de ser
expandidos.
 Este grupo de nodos se puede implantar
como una lista de espera, con
operaciones como:

–
–
–
–
Hacer-lista-espera (elementos)
¿Está vacía? (lista de espera)
Quitar-primero (lista de espera)
Poner-en-lista (elementos, lista de espera)
Algoritmo General de Búsqueda
Función búsqueda-general (problema, Función-lista-deespera)
produce una solución, o falla
nodos  Hacer-lista-de-espera (Hacer-nodo(Estadoinicial[problema]))
ciclo hacer
si nodos está vacío, contestar con falla
nodo  Quitar-primero (nodos)
si Prueba-Meta[problema] se aplica a Estado(nodo) y
se
tiene éxito, contestar con nodo
nodos  Función-lista-de-espera(nodos,
Expandir(nodo, Operadores[problema]))
fin
Estrategias de búsqueda

Las estrategias se evalúan de acuerdo a
su
– Completez
 ¿La
estrategia garantiza encontrar una
solución, si ésta existe?
– Complejidad temporal
 ¿Cuánto
tiempo se necesitará para encontrar
una solución?
– Complejidad espacial
 ¿Cuánta
memoria se necesita para efectuar la
búsqueda?
– Optimalidad
 ¿Con
esta estrategia se encontrará una solución
de la más alta calidad, si hay varias soluciones?
Estrategias de búsqueda no
informada
 No
existe información sobre la
cantidad de estados intermedios o
el costo de ruta para pasar del
estado actual a la meta.
 Sólo se sabe distinguir si estamos
en el estado meta o no
 A esta búsqueda se le conoce
también como búsqueda ciega
Estrategias de búsqueda no
informada
 Búsqueda
 Búsqueda
 Búsqueda
 Búsqueda
 Búsqueda
preferente por amplitud
de costo uniforme
preferente por profundidad
limitada por profundidad
por profundización
iterativa
 Búsqueda bidireccional
Búsqueda preferente por amplitud
 En
este caso, primero se expande el
nodo raíz y luego todos los nodos
generados por éste, luego sus
sucesores y así sucesivamente.
 Todos los nodos que están a
profundidad d se expanden antes
que los nodos con profundidad d+1.
Búsqueda preferente por amplitud
Función Búsqueda-preferente-por-amplitud(problema)
responde
con solución o falla
responde con Búsqueda-general (problema, Lista-deesperaal-final)
Búsqueda preferente por amplitud
Si hay solución, es seguro que se
encontrará mediante la búsqueda
preferente por amplitud.
 Si son varias soluciones, siempre
encontrará primero el estado de meta más
próximo (menos profundidad, más a la
izquierda).
 La búsqueda preferente por amplitud es
completa y óptima siempre y cuando el
costo de ruta sea una función que no
disminuya al aumentar la profundidad del
nodo.

Búsqueda preferente por amplitud
 Si
b es el factor de ramificación de
los estados, y la solución está a una
profundidad d, entonces la cantidad
máxima de nodos expandidos antes
de encontrar la solución es
1+ b+ b2 + b3 + ... + bd + (bd+1 – b)

La complejidad de este algoritmo es
O(bd+1).
Búsqueda preferente por amplitud

Si b=10, se analizan 10,000 nodos por segundo y cada
nodo requiere 1000 bytes de almacenamiento:
Profundidad
Nodos
Tiempo
Memoria
2
1100
.11 segundos
1 Megabyte
4
111,100
11 segundos
106
Megabytes
6
107
19 minutos
10 Gigabytes
8
109
31 horas
1 Terabyte
10
1011
129 días
101 Terabyte
12
1013
35 años
10 Petabytes
14
1015
3523 años
1 Exabyte
Búsqueda de costo uniforme
Con la búsqueda anterior no siempre se
encuentra la solución de costo de ruta
mínimo.
 La búsqueda de costo uniforme
expande siempre el nodo de menor costo
en el margen, medido por el costo de ruta
g(n) en vez del nodo de menor
profundidad.
 Si se cumplen ciertas condiciones, es
seguro que la primera solución encontrada
será la más barata.

Búsqueda de costo uniforme
A
S
1
5
S
B
15
10
5
0
Frontera
G
5
C
NOTA: NO SE GENERARÁN NUEVAMENTE
LOS ESTADOS ANALIZADOS PREVIAMENTE
S es el único nodo en la frontera
(nodos pendientes por expandir).
Debido a que no es la meta, se
procede a su expansión...
Búsqueda de costo uniforme
A
S
1
5
S
B
15
10
5
G
5
C
0
A
B
1
C
5
15
Frontera
Hay 3 nodos en la frontera (A, B y C), y se elige el de
menor costo de ruta (A). Como no es una meta, se procede
a su expansión...
Búsqueda de costo uniforme
A
S
1
5
S
B
15
0
10
5
G
5
A
B
C
5
C
G
15
Frontera
11
Hay 3 nodos en la frontera (G, B y C), de los cuales B es el
que tiene el menor costo de ruta, por lo que se procede a
expandirlo. Note que aunque ya hay una solución en la fronTera (G), el algoritmo la ignora porque la rama S-B tiene posibilidades de encontrar una solución mejor que S-A-G.
Búsqueda de costo uniforme
A
S
1
5
S
B
15
0
10
5
G
5
A
B
C
15
C
G
11
G
Frontera
10
Hay 3 nodos en la frontera (G, G y C), de los cuales el segundo G
es el que tiene el menor costo de ruta, por lo que se procede a
expandirlo. En ese momento se detecta que es una solución (sólo
genera nodos ya analizados) y la búsqueda termina. Note que hay
dos nodos (las dos G’s en la frontera) que representan a un mismo
estado, y que el algoritmo ni siquiera intenta expandir C, que no
tiene posibilidades de llevar a una mejor solución (S-C ya tiene un
costo de 15).
Búsqueda de costo uniforme
 Este
método puede encontrar la
solución más barata siempre y
cuando se satisfaga un requisito
sencillo: el costo de ruta nunca debe
ir disminuyendo conforme
avanzamos por la ruta, es decir,
g(Sucesor(n))  g(n) para todos los
nodos n.
Búsqueda preferente por
profundidad



En esta búsqueda siempre se expande uno de los
nodos que se encuentre en lo más profundo del
árbol.
Sólo si la búsqueda conduce a un callejón sin
salida (un nodo que no es meta y que no tiene
expansión), se revierte la búsqueda y se
expanden los nodos de niveles menos profundos.
Lo anterior se logra mediante el algoritmo de
Búsqueda-General, con una función de lista de
espera que ponga los estados recién generados al
principio de la lista.
Búsqueda preferente por
profundidad
Función Búsqueda-preferente-por-profundidad(problema)
responde con solución o falla
responde con Búsqueda-general (problema, Lista-deesperaal-principio)
Búsqueda preferente por
profundidad
NOTA: Se supone
que el factor de
ramificación es 2
y que los nodos
de nivel 3 no
tienen sucesores.
Búsqueda preferente por
profundidad
 Sólo
es necesario guardar la ruta que
va del nodo raíz al nodo hoja, junto
con los nodos restantes no
expandidos, por cada nodo de la
ruta.
 Si un espacio de estados tiene factor
de ramificación b y profundidad
máxima m, se requieren almacenar
bm nodos.
 La complejidad temporal es de
O(bm).
Búsqueda preferente por
profundidad
Si la cantidad de soluciones en un
problema es grande, se recomienda esta
búsqueda (BPPP) sobre la búsqueda
preferente por amplitud (BPPA).
 La desventaja de esta búsqueda es que se
puede quedar estancada al avanzar por
una ruta equivocada, ya que muchos
árboles de búsqueda pueden ser muy
profundos o infinitos. Por lo tanto, la BPPP
no es ni la mas completa ni la más
óptima.

Búsqueda limitada por
profundidad




Con esta búsqueda se eliminan las dificultades de la
búsqueda preferente por profundidad, al imponer un límite
a la profundidad máxima de una ruta.
El establecer este límite es difícil, ya que no conocemos
mucho sobre el espacio de estados.
La búsqueda limitada puede no ser completa ni óptima: un
límite de profundidad muy pequeño puede que no contenga
la solución, y uno muy grande puede que contenga
soluciones no óptimas que son encontradas primero.
La complejidad espacio-temporal de la búsqueda limitada
por profundidad es similar a la de la búsqueda preferente
por profundidad: requiere un tiempo de O(bl) y un espacio
O(bl), donde l es el límite de profundidad.
Búsqueda por profundización
iterativa



Elimina la dificultad de elegir un límite adecuado
de profundidad en la búsqueda limitada por
profundidad.
Lo anterior lo hace probando todos los límites de
profundidad posibles, primero la profundidad 0,
luego la 1, luego la 2, etc.
En la profundización iterativa se combinan las
ventajas de las búsquedas preferente por
profundidad y preferente por amplitud. Es óptima
y completa, como la búsqueda preferente por
amplitud, pero la memoria que necesita es la de
la búsqueda preferente por profundidad.
Búsqueda por profundización
iterativa
Función Búsqueda-por-profundización-iterativa(problema)
responde con una secuencia de solución.
entradas: problema, un problema.
para profundidad  0 a  hacer
si Búsqueda-limitada-por-profundidad(problema,
profundidad) tiene éxito, entregue el
resultado obtenido
fin-para
responda con falla
Búsqueda por profundización
iterativa
Límite = 0
Límite = 1
Límite = 2
Límite = 3
...
Búsqueda por profundización
iterativa
La búsqueda por profundización iterativa
puede parecer un desperdicio, por repetir
expansiones de estados, pero en la
mayoría de los problemas esta expansión
múltiple es realmente pequeña.
 La complejidad temporal sigue siendo
O(bd) y la complejidad espacial es O(bd).
 La profundización iterativa es el método
idóneo para aquellos casos donde el
espacio de búsqueda es grande y se
ignora la profundidad de la solución.

Búsqueda bidireccional
Es básicamente una búsqueda simultánea
que avanza a partir del estado inicial y
que retrocede a partir de la meta y que se
detiene cuando ambas búsquedas se
encuentran en algún punto intermedio.
 Si en un problema el factor de
ramificación b es el mismo en ambas
direcciones, la búsqueda bidireccional
puede ser muy útil. Si la solución está a
profundidad d, entonces la solución estará
a O(2bd/2) = O(bd/2) pasos

Búsqueda bidireccional

Cuestiones a resolver:
– La búsqueda hacia atrás implica la sucesiva generación de
predecesores a partir del nodo meta.
– Si todos los operadores son reversibles, los conjuntos de
predecesor y sucesor son idénticos, pero en algunos
problemas, el cálculo de los predecesores puede resultar muy
difícil.
– Si hay varios estados meta listados en forma explícita, se
puede aplicar una función de predecesor al conjunto de
estados como en el caso de la búsqueda de estado múltiple.
Pero si sólo hay una descripción de los estados meta, es
realmente difícil (¿qué estados son predecesores del jaque
mate en ajedrez?)
– Se requiere una manera eficiente de verificar cada uno de los
nodos nuevos para ver si ya están en el otro árbol.
– Se tiene que definir un tipo de búsqueda para cada mitad.
Amplitud – amplitud, amplitud – profundidad, etc. La
complejidad espacial es igual a la temporal para esta
búsqueda.
Descargar

Inteligencia Artificial