Resolución de problemas mediante

búsqueda
[7.1] ¿Cómo estudiar este tema?

[7.2] Introducción. Ejemplo «El mundo de los bloques»

[7.3] Dirección de la búsqueda

[7.4] Búsqueda exhaustiva o a ciegas

[7.5] Búsqueda heurística

[7.6] Búsqueda en juegos

[7.7] Costes

TEMA
 Técnicas de Inteligencia Artificial

Esquema

TEMA 2 – Esquema © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

Ideas clave

7.1. ¿Cómo estudiar este tema?

Para estudiar este tema deberás leer las Ideas clave que se presentan a continuación.
Puedes completar el estudio visualizando la lección magistral.

Al finalizar el estudio de este tema el alumno será capaz de:

Describir diferentes métodos de búsqueda de soluciones.

Seleccionar y aplicar métodos de búsqueda adecuados a diferentes problemas.

7.2. Introducción. Ejemplo «El mundo de los bloques»

Un agente, como podría ser un robot, se puede programar para actuar de tal manera
que alcance unos objetivos fijos pero que no pueda adaptarse a objetivos cambiantes,
no siendo, por tanto, inteligente. Por otra parte, se puede programar un robot que
decida sobre sus acciones en función de su estado, sus capacidades y sus objetivos.
¿Cómo se puede programar un robot para que tome decisiones? Una solución es que
busque, entre todos los estados posibles que representa el mundo, aquel estado que le
permita alcanzar un estado objetivo a partir del estado actual.

Existen así problemas de IA resolubles mediante búsqueda en los que se define un

espacio de estados y unos operadores que permiten la transición entre estados,
teniendo un estado inicial y un estado objetivo. En estos problemas, partiendo de un
estado inicial, se busca el camino para llegar a un estado objetivo. En cada estado se
pueden aplicar una serie de operaciones para llegar a otro estado distinto, que puede
ser el final o no.

En la resolución de problemas mediante búsqueda se ha de aplicar por tanto

una estrategia de control que permita encontrar un camino desde el estado
inicial al objetivo, lo que implica examinar posibles secuencias de acciones y los
estados que provocan, seleccionando aquella secuencia que sea la mejor según un
determinado criterio.

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

En la figura 1 se representa un problema sencillo de búsqueda mediante un gráfico. Ei

es el estado inicial y E0 es el estado objetivo. Mediante la aplicación de operadores de
estado se cambiará de estados (transición representada por flechas en la figura) y el
orden en que se apliquen esos operadores vendrá determinado por el algoritmo de
búsqueda.

Figura 1. Búsqueda de estados.

Por tanto, para resolver un problema mediante búsqueda, deben definirse los
componentes que lo forman:

Descriptores de estado: estructura simbólica capaz de representar cada estado.

Descriptores de operación: herramientas computaciones capaces de

transformar la representación del estado para poder inspeccionar sistemáticamente
el espacio de estados candidatos.

Descriptores de algoritmo de búsqueda: orden en que se aplican los

operadores a los diferentes estados para llegar al estado objetivo. El algoritmo de
búsqueda ha de ser un método efectivo de organizar las transformaciones entre
estados para así obtener el objeto deseado tan pronto como sea posible.

Este tipo de búsqueda se aplica, entre otros campos, en la búsqueda en juegos. Por
ejemplo, en el juego de ajedrez cada contrincante realiza una búsqueda entre todas las
jugadas que puede realizar en cada instante para realizar la jugada que le sea lo más
favorable posible respecto al estado en el que se encuentra. En este caso las reglas del
juego marcan las posibles operaciones de transición entre estados.

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

La investigación en robótica ha dado lugar a aplicar técnicas de búsqueda de estados para

la resolución de problemas. Programar un robot consiste en integrar varias funciones,
entre las que se incluye la percepción del entorno que le rodea a través de sensores,
formulación de planes de actuación y la realización de esos planes mediante actuadores. Un
controlador recibirá los estímulos, procesará datos, tomará decisiones y enviará los
comandos correspondientes a los actuadores que los convertirán en acciones.

A continuación se muestra un ejemplo referido específicamente a la generación de

planes de actuación que se utiliza típicamente para ilustrar la resolución de este tipo de
problemas mediante búsqueda. El problema se denomina «mundo de bloques» y en él
se plantea un robot que tiene un repertorio finito de acciones que puede ejecutar para
alcanzar un objetivo. El robot dispone de un brazo móvil capaz de cambiar de sitio a
unos cuantos bloques situados sobre una mesa. El entorno del robot estará formado por
la descripción de los distintos estados por los que atraviesa el mundo de bloques tras
las actuaciones del robot sobre él.

El planteamiento sigue el modelo propuesto para el planificador automático utilizado

en robótica STRIPS, utilizando un formalismo bastante intuitivo basado en lógica para
representar estados y operadores.

Se supone que la situación inicial es la mostrada en la figura 2:

A B

Figura 2. Estado inicial del «mundo de los bloques».

Esta situación de partida se puede describir mediante el conjunto de fórmulas lógicas:

SOBRE(C, A)  
SOBRE_LA_MESA(A)  
LIBRE(C) 
MANO_LIBRE 
SOBRE_LA_MESA(B) 
LIBRE(B) 

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

Para elaborar el plan de actuaciones, se ha de conocer el objetivo al que se desea llegar.

En este caso es que todos los bloques estén uno sobre otro tal y como se muestra en la
figura 3.

Figura 3. Estado objetivo del «mundo de los bloques».

Por tanto, el objetivo es obtener una descripción del estado del entorno del robot dado
por la conjunción de las fórmulas:

SOBRE(B,C) 
SOBRE(A,B) 

Para ello se han de aplicar operadores STRIPS que representan una acción mediante
tres componentes:

Precondiciones (P): prerrequisitos que han de ser ciertos en la descripción del

entorno para la realización de la acción.
Borrar (B): fórmulas que se han de borrar de la descripción del entorno una vez
aplicada la acción ya que dejan de ser ciertas.
Añadir (A): fórmulas que se han de añadir a la descripción del entorno una vez
aplicada la acción.

El modelo se completa con las reglas que simulan las acciones posibles del robot y que
se supone que el robot tiene programadas tales como:

COGER(X) 
P: LIBRE(X), MANO_LIBRE 
B: LIBRE(X), MANO_LIBRE 
A: COGIENDO(X) 
 
 

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

POSAR(X) 
P: COGIENDO(X) 
B: COGIENDO(X) 
A: SOBRE_LA_MESA(X), LIBRE(X), MANO_LIBRE 
 

APILAR(X,Y) 
P: COGIENDO(X), LIBRE(Y) 
B: COGIENDO(X), LIBRE(Y) 
A: MANO_LIBRE, SOBRE(X,Y), LIBRE(X) 
 

DESAPILAR(X,Y) 
P: MANO_LIBRE, LIBRE(X), SOBRE(X,Y) 
B: MANO_LIBRE, LIBRE(X), SOBRE(X,Y) 
A: COGIENDO(X), LIBRE(Y) 

COGER(X) corresponde a la acción de coger el bloque X de la mesa con el brazo, POSAR(X)

se refiere a posar el bloque X sobre la mesa, APILAR(X,Y) es situar el bloque X sobre el
bloque Y, y DESAPILAR(X,Y) se refiere a coger el bloque X que está situado sobre el bloque
Y.

Estas acciones constan de tres partes. La primera «P»  son las precondiciones que se
han de dar para la aplicación de la acción, la segunda «B» y la tercera «A» son las
fórmulas que se han de borrar y añadir, respectivamente, a la descripción del entorno si
esa acción se ejecuta (es, por tanto, parte de la consecuencia de la acción).

La planificación de las acciones del robot se puede entonces obtener mediante la

aplicación de algún procedimiento de búsqueda entre las descripciones posibles que
resultan de ejecutar distintas acciones que transformen el entorno desde la situación de
partida hasta el estado final u objetivo. La solución es el siguiente plan de acciones:

DESAPILAR(C,A) 
POSAR(C) 
COGER(B) 
APILAR(B,C) 
COGER(A) 
APILAR(A,B) 

En los siguientes apartados se explicarán diferentes procedimientos de búsqueda que

permiten resolver este tipo de problemas de búsqueda de estados.

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

7.3. Dirección de la búsqueda

El objetivo del proceso de búsqueda se resume en encontrar un camino a través del

conjunto de estados entre el estado o estados iniciales y el o los estados finales u
objetivos. Ahora bien, esta búsqueda puede hacerse en dos direcciones:

hacia adelante (del inicio al fin)

hacia atrás (del fin al inicio).

Existen modelos de búsqueda que permiten que estos procedimientos sean simétricos.
En este caso cualquiera de estas estrategias de búsqueda tiene validez.

Búsqueda hacia adelante

Se trata de una búsqueda guiada por los datos, aplicando información disponible para
obtener nueva información. Por ejemplo:

El objetivo es conocer C.

A    [0] 
A  B  [1] 
B  C  [2] 

Conocido A y sabiendo que si se cumple A se cumple B, se busca cambiar del estado [0]
al estado [1] para conocer B. Una vez conocido B se llega al estado [2] porque si se
cumple B se cumple C y se alcanza así el objetivo de conocer C.

Búsqueda hacia atrás

Se parte del objetivo hasta llegar al estado inicial. Ejemplo:

A    [0] 
A  B  [1] 
B  C  [2] 

Sabiendo cuál es el objetivo, conocer C, hace falta encontrar B, saber si B es cierto ya

que, de acuerdo a [2], si B es cierto, C es cierto.

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

C 
 [2] 
B 
 [1] 
A 

Hay por tanto que encontrar A puesto que se sabe que si A es cierto ([0]), B es cierto
([1]) y, por tanto, C es cierto ([2]).

¿Qué método de búsqueda se debe aplicar?

Existen algunos criterios para seleccionar el mecanismo de búsqueda y se citan a

continuación tres de los mismos:

Número de estados iniciales y finales: normalmente es más conveniente ir del

conjunto con menor número de elementos al de mayor número de elementos. Por
ejemplo, en el ejemplo bien conocido del llamado «problema de la lechera»:

«Se dispone de dos medidores de líquidos; uno de 5 litros y el otro de 7.

Inicialmente ambos están vacíos y, en cualquier momento pueden ser llenados o
vaciados usando un depósito de leche con suficiente capacidad. La leche también
puede ser traspasada de uno a otro medidor hasta que el primero se vacíe o hasta
que el segundo se llene. El problema consiste en encontrar la secuencia de acciones
que se deben seguir para que en el mayor de los medidores se disponga
exactamente de 4 litros».

Se conoce el estado inicial, con ambas jarras vacías, y el conjunto de estados finales:
todos los estados posibles que contengan 4 litros en el mayor de los medidores: 6
estados. Parece, por tanto, más sencillo buscar desde el estado inicial alguno de los 6
posibles estados finales. Si se realiza la búsqueda hacia atrás no se sabría desde qué
estado final es más fácil encontrar una solución; incluso en algunos casos desde
algún estado final no es accesible el estado inicial. En este ejemplo, por tanto, se
debería iniciar una búsqueda en paralelo desde todos los nodos finales si
quisiéramos adoptar una estrategia de búsqueda hacia atrás.

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

Factor de ramificación («branching factor»): el criterio es caminar en el sentido en

que el factor de ramificación sea más pequeño, esto es, el número medio de estados
accesibles directamente desde cada nodo en la dirección de búsqueda sea menor.

Por ejemplo, en el problema de ir de la propia casa a un lugar desconocido. Dado

que un propietario conoce los alrededores de su casa, si busca un camino hacia atrás
(de lo desconocido hacia su casa) resultará más fácil que lo contrario ya que es de
suponer que encontrará cruces en los cuales sabrá por dónde volver con más
facilidad a su casa que si hiciera el recorrido inverso, pretendiendo en los cruces
tratar de llegar al lugar desconocido.

La necesidad de justificar los pasos que se siguen en el razonamiento. Si

existe esta necesidad, es importante proceder en la dirección que más se aproxime al
modo de pensar del futuro usuario del sistema. Este es el caso típico de los sistemas
expertos de diagnóstico y propuesta de soluciones que siguen un método de
razonamiento hacia atrás.

Por ejemplo, un ingeniero ante un programa de detección de fallos y diagnóstico

siempre querrá justificar los pasos seguidos en el razonamiento, razonando hacia
atrás hasta determinar las causas de los fallos. Razonando hacia atrás el sistema
podrá responder a preguntas del tipo «¿Por qué debo hacer esta comprobación?»
respondiendo «porque eso ayudaría a determinar si el problema es debido a un fallo
eléctrico o un fallo de software».

El problema que existe con este tipo de criterios tan generales es que no siempre son
aplicables. Por ejemplo, en el primer caso, no siempre se sabe cuál es el número de estados
finales. Por otra parte, el factor de ramificación es normalmente difícil de aproximar.

Por último, también debe tenerse en cuenta que existe una tercera posibilidad y es usar
los dos tipos de razonamiento, hacia adelante o hacia atrás, de forma combinada.

Otro factor que permite clasificar los algoritmos de búsqueda es la aplicación de la

información disponible sobre el problema para su resolución.

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

Así, los algoritmos de búsqueda se pueden dividir en dos grandes grupos, atendiendo al
papel que juega el conocimiento en la estrategia de control de un sistema de búsqueda:

Búsqueda exhaustiva o a ciegas: no se tiene en cuenta la posible localización del

objetivo. Estos algoritmos no utilizan ninguna información del problema e ignoran
hacia dónde se dirigen hasta que encuentran el objetivo.

Búsqueda heurística: se tiene una estimación de lo que falta para llegar al estado
objetivo. Los algoritmos utilizan información del problema para localizar el objetivo.

Los siguientes apartados se dedican a explicar estos dos grandes grupos de algoritmos
de búsqueda.

7.4. Búsqueda exhaustiva o a ciegas

Búsqueda a ciegas
Consiste en generar todos los estados posibles hasta encontrar la solución. Para
generar todos los estados se aplica una regla de forma sistemática, sin tener
en cuenta ninguna información del problema, ni del objetivo que se busca.

Existen varios tipos de algoritmos de búsqueda a ciegas que se describen en los

siguientes subapartados.

Búsqueda en amplitud

En la búsqueda de estados se va generando un grafo como puede ser una malla o un

árbol de estados como los mostrados en la figura 1 o en la figura 4. Si la búsqueda es en
amplitud, a partir de un nodo se generan todos los hijos y, para cada hijo, todos los
nietos, y así sucesivamente.

Por tanto, cada nivel del árbol de estados se desarrolla completamente antes
de desarrollar el siguiente nivel. Según los nodos de un nivel se generan, si no se
ha llegado a la solución, se va al siguiente nivel para generar los nodos siguientes. Así,
hasta encontrar el objetivo.

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

Esta estrategia asigna mayor prioridad a los nodos con menor profundidad, generando
los nodos por niveles tal y como se muestra en la figura 4 en la que los números indican
el orden en que se van generando los nodos:

Figura 4. Ejemplo de búsqueda en amplitud.

Así, se hace un recorrido uniforme del grafo que le da un carácter «lento pero seguro».
En este algoritmo siempre se expande primero el nodo menos recientemente
creado, siguiendo una estrategia FIFO (first-in , first-out).

Cuando los costes de ir de un nodo a otro son uniformes, se garantiza que se encontrará
la solución con el camino más corto, esto es, la secuencia con menor número de estados
hasta el estado objetivo. Sin embargo, si el coste no es uniforme, no se garantiza esto.

El problema es la gran cantidad de memoria necesaria y la lentitud en encontrar la

solución si esta se encuentra a gran profundidad. Aunque algorítmicamente se puede
considerar una búsqueda perfecta (siempre encuentra solución óptima), no lo es desde
el punto de vista de la IA; ya que es inflexible frente a cualquier tipo de conocimiento
que se tenga sobre el problema.

Búsqueda en profundidad

Esta estrategia da prioridad a los nodos más profundos en el grafo de

búsqueda de tal forma que estos se expanden o desarrollan, para generar posibles
soluciones, antes que otros nodos menos profundos.

Tras cada expansión o desarrollo de un nodo, de los hijos que acaban de ser generados
se selecciona uno para ser de nuevo desarrollado. Esta exploración hacia abajo se

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

desarrolla hasta que, por alguna razón, el proceso queda bloqueado. En tal caso, el
proceso continúa desde el nodo más profundo que haya sido dejado atrás sin explorar;
es decir, desde el último punto en el que se tomó una decisión dejando alguna
alternativa sin explorar.

De esta forma, se toma un camino y se sigue hasta que se encuentra la solución o un

callejón sin salida, en cuyo caso se vuelve hacia atrás.

Figura 5. Ejemplo de búsqueda en profundidad.

En este algoritmo siempre se expande el nodo más recientemente creado,

siguiendo la estrategia LIFO (Last-in, First-out).

El problema de este algoritmo es que no garantiza que se encuentre la solución por el

camino más corto. Además, podría suceder que una solución se encuentre a poca
profundidad pero no se encuentre pronto porque previamente se han explorado
caminos muy profundos. Sin embargo, tiene la ventaja de que si la tasa de generación
de hijos es muy alta, se mitiga el hecho de poder quedarse sin memoria, tal y como es
más probable que pase en la búsqueda en amplitud.

Esta estrategia funciona bien cuando abundan las soluciones en el grafo y todas ellas son
igualmente deseables (es decir, no conduce más que de casualidad a una solución óptima).

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

También puede resultar adecuada cuando existen medios que nos pueden indicar
pronto el que se ha elegido una dirección equivocada con lo cual podremos bloquear la
búsqueda en este camino.

Los dos algoritmos (búsqueda en amplitud y en profundidad) funcionan bien en grafos

y en árboles; aunque con árboles en búsqueda en profundidad se puede entrar en un
camino infinito. Además, estos dos algoritmos son algoritmos de fuerza bruta, se va de
una rama a otra sin tener en cuenta ninguna información sobre el problema.

Búsqueda en profundidad acotada

En vez de coger un camino hasta el final, se aplica búsqueda en profundidad hasta un nivel
y, si con esa profundidad no se consigue el objetivo, se realiza búsqueda en profundidad a
partir de un nivel superior. Así, se evita centrarse sólo en una parte del árbol.

Se define una profundidad límite más allá de la cual no se buscará. Esto evita que el
proceso no pare en grafos infinitos (o en los que haya una rama infinita).

Búsqueda en profundidad iterativa

Se busca con profundidad acotada, partiendo de una cota inicial e incrementándola en

uno hasta que se llegue a la solución.

Con esta forma de búsqueda, se intenta combinar las ventajas de búsqueda en anchura
y búsqueda en profundidad. Siempre se va a encontrar el camino más corto y no se
necesita tener todos los nodos en memoria.

Los algoritmos de búsqueda a ciegas no se pueden aplicar siempre, pero en el caso de

que se puedan aplicar dan muy buenos resultados.

A continuación se expone un ejemplo para ilustrar el funcionamiento de los algoritmos

de búsqueda a ciegas. Dado el árbol que se muestra en la figura 6, se representa en las
figuras 7, 8 y 9, los órdenes en que se expanden los nodos en función del tipo de
búsqueda. Nótese que para la búsqueda en profundidad iterativa la cota inicial de
profundidad tiene un valor de 0, por lo cual se expande únicamente el nodo raíz. En el
siguiente paso, la profundidad tiene un valor de 1, con lo que se extiende el nodo raíz y
sus hijos.

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

Figura 6. Árbol de ejemplo.

2 3 4

5 6 7 8 9 10

11 12 13 14
Figura 7. Orden en que se expanden los nodos si se aplica búsqueda en anchura.

2 7 10

3 6 8 9 11 14

4 5 12 13
Figura 8. Orden en que se expanden los nodos si se aplica búsqueda en profundidad.

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

3 4 5

8 9

10

11

12 13

14

15

16 17

18

19

20

21 22

Figura 9. Orden en que se expanden los nodos si se aplica búsqueda en profundidad iterativa.

7.5. Búsqueda heurística

Métodos de búsqueda a ciegas

Son métodos exhaustivos para encontrar caminos a un estado objetivo. En principio
proporcionan una solución al problema de encontrar el camino, pero a
menudo no es viable su uso porque la búsqueda expandirá demasiados nodos
antes de encontrar un camino.

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

Para muchas tareas es posible declarar principios o reglas que ayudan a reducir la
búsqueda. Cualquier técnica usada para acelerar la búsqueda depende de la
información disponible sobre el problema representado por el grafo.

En los métodos de búsqueda heurística se aplica información del problema

para encontrar la solución. A esta información disponible se le denomina
información heurística, mientras que los procedimientos de búsqueda usados son
denominados métodos de búsqueda heurística.

Estos algoritmos tienen en cuenta que un estado generado puede no ser solución pero
podría estar más cerca de ella. En ese caso la búsqueda se seguiría desde este nodo en
adelante. Para aplicar este método de búsqueda se emplea una función denominada
heurístico, que mide la proximidad de los nodos al objetivo.

Heurístico (regla heurística o método heurístico)

Es una regla de estrategia y simplificación, que limita drásticamente la
búsqueda de soluciones en grandes espacios de problemas.

Se enumeran a continuación algunos aspectos en los que la información heurística

puede ser aplicada para expandir un árbol de manera eficiente:

Decidir qué nodo debe ser expandido o desarrollado en todas sus posibilidades en
lugar de tener un criterio puramente igualitario de la potencia de los nodos
candidatos.

Decidir qué sucesor o sucesores deben ser considerados en primer lugar en lugar de
considerar todos los posibles sucesores a la vez.

Decidir qué nodos deben ser descartados o podados del espacio de búsqueda.

El objetivo de la búsqueda heurística es, por tanto, reducir el número de nodos

examinados y la efectividad depende del heurístico seleccionado.

Sin embargo, se da el hecho de que no es fácil seleccionar el heurístico.

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

A continuación se muestra un ejemplo basado en el conocido problema del «puzle 8»

en el que se proponen dos posibles heurísticos.

La solución de este rompecabezas consiste en, a partir de una configuración inicial

dada, reordenar ocho elementos numerados móviles situados en un tablero de 3 x 3
para conseguir una configuración final dada (Ver figura 10).

1 2 3 2 8 3
8 4 1 4
7 6 5 7 6 5

Figura 10. Problema del «puzle 8».

Los heurísticos propuestos son:

h1: número de fichas mal colocadas, mientras mayor sea este valor peor.

h2: distancia Manhattan: la suma de las distancias de las fichas mal colocadas. La
distancia se mide como el número de movimientos necesarios para situar la ficha en
la posición final deseada.

La figura 11 muestra los valores de estos heurísticos para diversas configuraciones

según la ficha que se mueva desde la posición inicial mostrada en la figura 10.

h1 h2

2 8 3
1 6 4 4 5
7 5

2 3 1 2 3
1 8 4 3 3 8 4
7 6 5 7 6 5

2 8 3
1 4 3 5
7 6 5

Figura 11. Valores de heurísticos para diversas configuraciones del puzle 8.

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

Se ve en este ejemplo sencillo cómo el heurístico que se selecciona determina la rapidez

en conseguir el objetivo. El movimiento adecuado es el segundo y, por tanto, el
heurístico 2 en este ejemplo parece más adecuado.

Este caso es muy sencillo pero, en general, no es fácil definir el heurístico adecuado.

Más aún, los heurísticos no garantizan la obtención de soluciones óptimas; de hecho,

no garantizan ningún tipo de solución: se estima si un nodo está más cerca que otro
para llegar a la solución, aunque como es una estimación podría dar lugar a una
equivocación.

En conclusión, todo lo que se puede decir de un heurístico útil es que ofrece soluciones
que son suficientemente buenas la mayoría de las veces.

Escalada simple o hill climbing

La interpretación intuitiva más sencilla y de la que toma el nombre el método de

búsqueda «escalada simple» consiste en considerar el proceso como la escalada a una
montaña: el objetivo es alcanzar la cima y el estado de búsqueda es el punto donde se
encuentra el escalador. La regla de la que se dispone es seguir escalando hasta que se
llegue a un punto a partir del cual no se pueda ascender más.

Mediante este método en el momento que se encuentra un estado más favorable que el
actual, se avanza al nuevo estado encontrado.

Para simplificar la explicación se puede considerar montañas de dos dimensiones con

lo que la escalada consiste en la búsqueda de un máximo de una función real de
variable real: f. El escalador hipotético, si se encuentra en un punto x0, si los saltos que
puede dar son de amplitud δ, podría dirigirse a x0 + δ o quedarse donde está.

Dependiendo de la altura f(x0 + δ) que se obtenga al avanzar y la altura actual del

escalador f(x0) se decidirá avanzar a la nueva posición si la situación tras el avance es
mejor que la situación sin avanzar, porque la altura se incremente. Si la altura no se
incrementa al avanzar, se da como solución la posición x0 (ver figura 12).

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

f(x)

f(x0+δ)

f(x0)

x0 x0+δ x

Figura 12. Escalada simple: Búsqueda del máximo de una función.

Este método, presenta problemas de máximos locales y/o mesetas como intuitivamente
se puede concluir observando las funciones representadas en la figura 13.

Figura 13. Máximo local (función de la izquierda) y meseta (función de la derecha).

Este método resulta interesante para maximizar o minimizar funciones y es el

algoritmo que se utiliza para, por ejemplo, sintonizar una emisora de radio. Se van
haciendo movimientos del sintonizador de frecuencias en una dirección siempre que la
calidad de la señal recibida mejore. Al llegar a un punto donde no mejora en ninguna de
las dos direcciones se detiene la búsqueda en el dial.

Escalada por máxima pendiente

En el método de escalada simple, el algoritmo en el momento que encuentra un estado

E’ más favorable que el actual E, se avanza al estado E’.

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

Sin embargo, el método de escalada por máxima pendiente consiste en «explorar los
alrededores» antes de seguir avanzando por la montaña. Cuando se está en un punto,
se da un paso en todas las direcciones y se va por el mejor camino.

Se consideran todos los posibles movimientos a partir del estado actual y se elige como
nuevo estado el mejor de ellos.

En este caso el escalador hipotético para avanzar desde un punto x0, si los saltos que
puede dar son de amplitud , podría dirigirse o bien a x0 -  o bien a x0 +

Dependiendo de la altura que tengan estas posibilidades, f(x0 - ) y f(x0 + )

respectivamente, y la del propio escalador f(x0) se decidirá saltar a la mejor opción. Si
la situación actual no es mejorable, la posición x0 se dará como solución. En el caso del
ejemplo mostrado en la figura 14, la decisión será saltar a x0 + .

f(x)

f(x0+δ)

f(x0)

f(x0-δ)

x0 x0+δ x
x0-δ

Figura 14. Escalada por máxima pendiente.

Por tanto, mediante este método se exploran todos los posibles siguientes estados y se
finaliza cuando se llega a un nodo en el que todos los siguientes estados son peores que
el actual. Cuando se salta a la mejor opción, se asume que ese siguiente estado está más
cerca del final.

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

Este algoritmo obtiene una mejor ruta que el método de escalada simple, pero es más
lento, porque hay que evaluar todos los siguientes estados posibles y el número de
operadores aplicables a un estado puede ser muy grande. Por tanto, puede suponer
altos requerimientos de computación y de memoria. Aun así, en general estos
algoritmos de escalada suelen ser muy rápidos, aunque, como principal inconveniente,
presentan problemas de máximos locales y mesetas.

Búsqueda «mejor el primero» o best-first

Este algoritmo intenta combinar las ventajas de la búsqueda en amplitud y en

profundidad.

En cada paso del algoritmo se va a seguir un camino y se va a cambiar de ruta cuando

haya una ruta más prometedora.

El funcionamiento es el siguiente: se expande el nodo padre generando nodos hijos. El

nodo padre se incluye en la lista de nodos cerrados o ya expandidos, mientras que los
nodos hijos se incluyen en la lista de nodos abiertos o no expandidos. Analizando todos los
nodos abiertos se comprueba si alguno de los nodos es el objetivo y, si ninguno lo es, se
escoge como siguiente nodo a expandir el que parezca más prometedor, de
acuerdo al valor de una función de evaluación que se esté aplicando. Típicamente esta
función se basará en un heurístico que estime la cercanía del nodo al objetivo.

Se muestra, a continuación, un ejemplo para ilustrar los diferentes pasos del algoritmo
y cómo progresan los nodos cerrados y abiertos. Las listas que se muestran en el
ejemplo están ordenadas por orden de prioridad, tomando por tanto el primer
elemento en la lista como el nodo a expandir. El número asociado a cada nodo indica el
valor de la función de evaluación. Un nodo es más prometedor, cuanto más pequeño
sea el valor de esta función. El objetivo es P. La figura 15 muestra el grafo del ejemplo y
los diferentes pasos del algoritmo son los siguientes:

1. ABTOS = [A5] 
CDOS = [  ] 
2. Evaluación A5 
ABTOS = [B4, C4, D6] 
CDOS = [A5] 
3. Evaluación B4 

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

ABTOS = [C4, E5, F5, D6] 
CDOS = [B4, A5] 
4. Evaluación C4 
ABTOS = [H3, G4, E5, F5, D6] 
CDOS = [C4, B4, A5] 
5. Evaluación H3 
ABTOS = [O2, P3, G4, E5, F5, D6] 
CDOS = [H3, C4, B4, A5] 
6. Evaluación O2 
ABTOS = [P3, G4, E5, F5, D6] 
CDOS = [O2, H3, C4, B4, A5] 
7. Evaluación P3 

Figura 15. Grafo del ejemplo de búsqueda «primero el mejor».

El problema que presenta este algoritmo es que hay que mantener todos los nodos
abiertos (o no expandidos) en la memoria de trabajo. Además, el heurístico puede
fallar, como es el caso de la evaluación del nodo O en el ejemplo anterior que no se
acerca precisamente al objetivo, aunque el algoritmo es lo suficientemente bueno como
para recuperarse del fallo. Por otra parte, este algoritmo tiene la ventaja de valer tanto
para árboles como para grafos.

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

Algoritmo A*

El algoritmo A* se puede considerar una particularización del algoritmo de búsqueda

«mejor el primero» en que la función de evaluación f(n) se define como sigue:

Para cada nodo n,

f(n) = h(n) + g(n)

siendo:

h(n): heurístico, coste estimado del camino más corto del nodo actual al nodo
objetivo (h(n)=0 si n es un nodo objetivo).
n  nO

g(n): coste real del camino conocido más corto desde el nodo origen al nodo n a
evaluar.
ni  n

Por tanto la función de evaluación f(n) es el coste del camino más corto
desde el nodo inicial al nodo objetivo condicionado a pasar por el nodo n.
Cabe comentar que la definición de h(n) es una tarea complicada y determinará el
rendimiento adecuado de la aplicación de este algoritmo.

El algoritmo seleccionará como nodo a expandir el que tenga un menor valor de f(n).
Este algoritmo tiene en cuenta por tanto la medida de la profundidad, utilizando una
estimación del coste del camino total.

Si se define h(n) = 0, se está realizando una búsqueda en anchura, que siempre da lugar
al camino más corto, pero cuyo coste computacional es muy elevado.

Este algoritmo impone una restricción para alcanzar el objetivo por el camino de menor
coste: la función h nunca ha de sobreestimar el coste para alcanzar el objetivo. Una función
h de este tipo es una heurística admisible.

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

A continuación se utiliza de nuevo el problema del «puzle 8» para ilustrar lo que no se

considera una heurística admisible. En la figura 16, la configuración F es la final
deseada, la configuración I es la inicial y la configuración A representa un posible
movimiento de una ficha desde la configuración I.

2 3 1 2 3
1 8 4 8 4
7 6 5 7 6 5
I F
2 3
1 8 4
7 6 5
A

Figura 16. Ejemplo de problema del «puzle 8».

Para analizar si la configuración A está más cerca del objetivo F, se consideran los
heurísticos siguientes:

h1(n) = número de fichas mal colocadas

h2(n) = distancia Manhattan
h3(n) = h2(n) + 3·S(n)

S(n) es la cuenta de secuencia obtenida recorriendo sucesivamente las casillas no

centrales y anotando dos puntos en la cuenta por cada ficha no seguida por su ficha
sucesora y 0 puntos para las otras; si hay una ficha en el centro se anota 1. Por ejemplo,
este cálculo, para la posición inicial sería:

h3(posición inicial) = 3 + 3 (2 + 2 + 1) = 18

En la tabla 1 se muestran los valores de estos heurísticos para las configuraciones I y A:

Inicio I A
h1 3 4
h2 3 4
h3 18 19

Tabla 1. Valores de los heurísticos propuestos.

Los dos primeros heurísticos son admisibles, mientras que h3(n) no es admisible, dado que
es mayor al número de movimientos que hay que realizar para llegar a la solución F.

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

7.6. Búsqueda en juegos

Búsqueda en juegos
Consiste en determinar el conjunto de jugadas que permiten ganar al oponente.

Las búsquedas más sencillas son las relativas a problemas de búsqueda de estrategias
ganadoras en juegos de dos jugadores con movimientos alternados y en los que no
interviene el azar. Concretamente, son juegos de los llamados de información
completa y suma nula:

La información completa se refiere al hecho de que cada jugador conoce las

jugadas que se hicieron y todas las que se pueden hacer en cada momento y por cada
jugador.

La suma nula se refiere a juegos en los que las situaciones finales son o de victoria
para uno de los jugadores (y, por tanto, derrota para el otro) o empate; se excluyen,
por tanto, juegos en los que puedan perder o ganar a la vez los dos jugadores.

Juegos típicos de este tipo son el ajedrez, las damas, el tres-en-raya, etc.

Las partidas posibles que se pueden realizar en estos juegos se pueden describir
mediante árboles o grafos en los cuales las hojas corresponden a situaciones de victoria
para alguno de los jugadores, de derrota o tablas. Los nodos intermedios representan
situaciones donde debe mover uno u otro jugador.

Se pueden diferenciar dos tipos de juegos:

Juegos donde es posible desarrollar todo el espacio de estados.

Juegos donde no es posible desarrollar todo el espacio de estado, porque es muy
grande. En este caso se aplican heurísticos para estimar si una jugada es buena o no.

Como ejemplo de la búsqueda en juegos se explica el algoritmo sencillo Minimax.

Se consideran dos jugadores: MIN y MAX y el objetivo es que gane MAX. MAX
intentará maximizar su ventaja y minimizar la de MIN.

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

Cada nivel del árbol va a estar formado por nodos MAX o MIN, según a quien le toque
jugar. Se supone que MIN tiene la misma información e inteligencia que MAX. Además
MIN intentará hacer lo peor para MAX. El algoritmo Minimax elegirá el mejor movimiento
para MAX suponiendo que el contrincante elegirá lo peor para MAX. Una vez determinado
el grafo de todas las posibles jugadas, el proceso a seguir es el siguiente:

1. Asignar a los nodos finales un valor:

1  victoria MAX
0  victoria MIN

2. Propagar las etiquetas o valores de esta función hacia arriba. Si se tiene un nodo
MAX se toma el máximo de los hijos y, si se tiene un nodo MIN, se toma el mínimo
de los hijos.

3. El camino de victoria se obtiene uniendo el trazado que va por los 1's (ver figura 17).

1
MAX

0 1 MIN

0 1
1 MAX

0 0 1 1 MIN
Figura 17. Ejemplo de árbol resultado de ejecutar el algoritmo Minimax.

El procedimiento MINIMAX toma las decisiones óptimas en cada jugada y, si es

posible, ganará la partida o, si no, la empatará.

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

7.7. Costes

Los procedimientos de búsqueda inteligente en problemas de una cierta

magnitud, como suelen ser los problemas de inteligencia artificial, deben disponer de
estrategias de control adecuadas. Es decir, que se debe guiar la búsqueda
basándose en conocimientos específicos del tema a tratar, tal y como se hace en la
búsqueda heurística. El problema está en saber cómo se maneja y representa el
conocimiento para que este sea útil.

En la búsqueda exhaustiva (con información nula) es necesario expandir todos los

nodos, lo que conlleva un elevado coste debido a la expansión del árbol. Por otra parte,
a medida que se tiene más información (mejor es el heurístico), se expanden solo los
nodos necesarios con lo que disminuye el coste debido a la expansión del árbol. Sin
embargo, el coste debido a la estrategia de control aumenta a medida que se emplea un
heurístico mejor; ya que calcular el heurístico conlleva mucho gasto computacional.

Por lo tanto, el problema del coste se puede resumir en la suma de los costes:
Debidos a la estrategia de control.
Debidos a la expansión de los nodos del árbol.

Estas consideraciones sobre los costos de la estrategia de control y de la expansión del

árbol en un proceso de búsqueda pueden resumirse a través del gráfico de la figura 18.

Coste total de la búsqueda

Coste del proceso
de búsqueda
Debido a la estrategia de control

Debido a la expansión del árbol (reglas)

Información empleada en la búsqueda

Figura 18. Coste del proceso de búsqueda en función de la información.

Analizando el gráfico anterior, el problema está en encontrar el punto de corte de las

gráficas correspondientes al consumo causado por la estrategia de control y al coste
debido a la expansión del árbol, ya que marca el mínimo del costo total utilizado en el
proceso de resolución del problema.

TEMA 7 – Ideas clave © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

Lo + recomendado

Lecciones magistrales

Búsqueda en juegos: algoritmo Minimax

Esta lección magistral consiste en ilustrar el funcionamiento del algoritmo de búsqueda

en juegos Minimax aplicándolo al juego de Grundy.

Accede a la lección magistral a través del aula virtual

No dejes de ver…

Métodos de búsquedas, a ciegas y heurísticas

Presentación que explica los métodos de

búsquedas a ciegas y heurísticas, con un ejemplo
muy ilustrativo relativo a un problema de salir de
un laberinto.

Accede al vídeo desde el aula virtual o a través de la siguiente dirección web:

https://www.youtube.com/watch?v=g6l685-LMbU

TEMA 7 – Lo + recomendado © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

+ Información

A fondo

Making games

Página web de un ex estudiante de doctorado de la Universidad de Stanford. Contiene

información, recursos y enlaces muy interesantes relacionados con la inteligencia
artificial y la creación de juegos. Específicamente se recomienda visitar la sección
dedicada a temas de programación de juegos, que incluye recursos relacionados con el
tipo de cuestiones que el autor necesitó conocer mientras trabajó en crear juegos. El
autor hace especial hincapié en el algoritmo A*, con enlaces muy interesantes, códigos y
demos.

Accede a la página principal desde el aula virtual o a través de la siguiente dirección web:
http://www-cs-students.stanford.edu/~amitp/

Accede a la sección de programación de juegos desde el aula virtual o a través de la

siguiente dirección web:
http://www-cs-students.stanford.edu/~amitp/gameprog.html

Applets de Java para visualizar el funcionamiento de estrategias de

búsqueda a ciegas

Página web interactiva en la que puedes observar el orden en que un determinado

algoritmo de búsqueda a ciegas recorre los nodos de un árbol. Específicamente se
puede observar el funcionamiento de los algoritmos explicados en este tema. Además,
la autora de los applets que permiten esta visualización, Naomi Novik, proporciona
acceso al código fuente de los applets y documentación asociada.

Accede a la página principal desde el aula virtual o a través de la siguiente dirección web:
http://cse.unl.edu/~choueiry/S03-476-876/searchapplet/

TEMA 7 – + Información © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

Bibliografía

Fikes, R.E. & Nilsson, N.J. (1971). Strips: A new approach to the application of theorem
proving to problem solving. Artificial Intelligence, 2(3–4), 189-208.

Poole, D. L. & Mackworth, A. K. (2010). Artificial intelligence: foundations of

computational agents. New York: Cambridge University Press.

TEMA 7 – + Información © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

Actividades

Resolución del problema del puzzle-8 mediante búsqueda

heurística

Descripción de la actividad

El puzzle-8 es un juego de un único jugador que consiste en un tablero de 9 posiciones

(3x3), y ocho fichas numeradas del 1 al 8, situadas en el tablero, quedando una posición
del tablero vacía. El objetivo del juego es alcanzar una determinada disposición de las
fichas a partir de una disposición inicial realizando sólo los movimientos permitidos,
que son mover una ficha adyacente a la posición vacía de forma horizontal o vertical,
ocupando la posición vacía y quedando en su lugar vacía la casilla ocupada
anteriormente por la ficha movida.

En esta actividad has de utilizar la estrategia de búsqueda heurística A* con el fin de

resolver el problema del puzzle-8 teniendo en cuenta el siguiente estado inicial del
puzzle:

2 8 3
1 6 4
7 5

El estado objetivo es el siguiente:

1 2 3
8 4
7 6 5

Utiliza como heurística el número de fichas mal colocadas respecto al estado objetivo.
El coste de cada movimiento es 1. Se pretende encontrar la secuencia de movimientos
de las fichas que permiten alcanzar el estado objetivo con el menor coste, esto es, el
menor número de movimientos de fichas.

TEMA 7 – Actividades © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

Pautas de elaboración

Debes desarrollar el árbol de búsqueda desde el estado inicial al estado objetivo,

anotando en cada iteración del algoritmo el contenido de la lista abierta y cerrada de
nodos (estados) con su valor de función de evaluación.

En la actividad debes entregar un informe que contenga dicho árbol de búsqueda

desarrollado, y los diferentes pasos de ejecución del algoritmo indicando en cada paso
la lista abierta y lista cerrada de nodos, los valores utilizados para evaluar los nodos,
dejando claro el orden en que han sido expandidos los nodos.

Extensión máxima: 3 páginas (Georgia 11 e interlineado 1,5).

TEMA 7 – Actividades © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

Test

1. Indica cuáles de las siguientes afirmaciones son correctas respecto a los problemas
de búsqueda de estados:
A. La resolución de un problema mediante búsqueda conlleva definir únicamente
dos descriptores: los de operación y los de estado.
B. Los descriptores de operación indican el orden en que se aplican los
operadores a los diferentes estados para llegar al estado objetivo.
C. La búsqueda de estados se aplica en juegos y en robótica.
D. La resolución de un problema de búsqueda se puede describir como la
búsqueda de un camino a través de un conjunto de estados que permite alcanzar
un estado objetivo desde un estado inicial.

2. Cuando se conoce un estado inicial y múltiples estados objetivos, ¿qué búsqueda es

más conveniente aplicar en principio?
A. Búsqueda hacia adelante.
B. Búsqueda hacia atrás.

3. Si he de justificar el motivo por el que se da un razonamiento se suele utilizar:

A. Búsqueda hacia adelante.
B. Búsqueda hacia atrás.

4. Indica cuáles de las siguientes afirmaciones son correctas respecto a los algoritmos
de búsqueda a ciegas:
A. La búsqueda en amplitud sigue una estrategia LIFO para expandir los nodos.
B. La búsqueda en profundidad garantiza que se encuentre la solución por el
camino más corto.
C. La búsqueda en profundidad no tiene en cuenta ninguna información sobre el
problema.
D. La búsqueda en profundidad iterativa intenta combinar las ventajas de la
búsqueda en amplitud y la búsqueda en profundidad.

TEMA 7 – Test © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

5. Indica cuáles de las siguientes afirmaciones son correctas respecto a los algoritmos
de búsqueda heurística:
A. Utilizan información heurística que es información sobre el problema para
encontrar la solución.
B. El heurístico es una función que permite garantizar encontrar la solución
óptima.
C. Facilitan la aceleración de la búsqueda.
D. El heurístico puede utilizarse para, una vez expandido el nodo, decidir qué
nodo hijo ha de ser considerado en primer lugar.

6. Indica la afirmación correcta relacionada con la búsqueda heurística:

A. La escalada por máxima pendiente presenta problemas de máximos locales
pero no de mesetas.
B. La escalada simple considera todos los posibles movimientos a partir del
estado actual, escogiendo el mejor de ellos.
C. El algoritmo de búsqueda «primero el mejor» puede presentar problemas de
memoria.
D. El heurístico en un algoritmo A* ha de ser admisible, esto es, no debe
sobreestimar el coste desde el nodo origen al nodo actual.

7. Si no se dispone de información útil de un problema de búsqueda, ¿qué método de

los siguientes se podría en principio aplicar para resolverlo?
A. Búsqueda en profundidad.
B. Búsqueda «mejor el primero».
C. Escalada por máxima pendiente.
D. Ninguno de los anteriores.

8. Si se dispone de información útil de un problema de búsqueda, ¿qué método de los

siguientes se podría, en principio, aplicar para resolverlo?
A. Búsqueda en profundidad iterativa.
B. Búsqueda en profundidad acotada.
C. Búsqueda «mejor el primero».
D. Ninguno de los anteriores.

9. Indica cuáles de las siguientes afirmaciones relativas al algoritmo Minimax de

búsqueda en juegos son ciertas:

TEMA 7 – Test © Universidad Internacional de La Rioja (UNIR)

 Técnicas de Inteligencia Artificial

A. Minimax es un algoritmo utilizado en la búsqueda en juegos.

B. El algoritmo Minimax desarrolla todo el espacio de estados.
C. Minimax se aplica a juegos de información completa, pero suma no nula.
D. Minimax toma las decisiones óptimas en cada jugada de tal forma que si es
posible Min ganará la partida.

10. Si se desea minimizar el coste del proceso de búsqueda se ha de:

A. Minimizar el coste debido a la expansión del árbol.
B. Minimizar el coste debido a la estrategia de control.
C. Minimizar la suma de los costes debidos a la expansión del árbol y a la
estrategia de control.
D. Minimizar los costes debidos a la expansión del árbol y utilizar el mejor
heurístico posible.

TEMA 7 – Test © Universidad Internacional de La Rioja (UNIR)