• Author / Uploaded
• Armando Garcia

• Categories
• Teoría de la complejidad computacional
• Algoritmos
• Informática teórica
• Conceptos matemáticos
• Matemáticas discretas

Citation preview

Inteligencia Artificial (IA) ´ de problemas Resolucion Algoritmos de busqueda ´ Javier Béjar

Departament de Llenguatges i Sistemes Informàtics Enginyeria en informàtica Cuatrimestre - curso 2006/2007

\

$ BY:



C

1

er

This work is licensed under the Creative Commons

\

$ BY:



C

Attribution-NonCommercial-ShareAlike License. To view a copy of this license, visit

http://creativecommons.org/licenses/by-nc-sa/2.0/ Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

or send a letter to:

Índice general 1. Resolución de problemas

1

1.1.

¾Qué es un problema?

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2.

El espacio de estados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.3.

Algoritmos de búsqueda en el espacio de estados . . . . . . . . . . . . . . .

6

2. Búsqueda no informada

11

2.1.

Búsqueda independiente del problema . . . . . . . . . . . . . . . . . . . . .

11

2.2.

Búsqueda en anchura prioritaria . . . . . . . . . . . . . . . . . . . . . . . .

11

2.3.

Búsqueda en profundida prioritaria

. . . . . . . . . . . . . . . . . . . . . .

12

2.4.

Búsqueda en profundidad iterativa

. . . . . . . . . . . . . . . . . . . . . .

15

3. Búsqueda heurística

17

3.1.

El conocimiento importa . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

3.2.

El óptimo está en el camino

. . . . . . . . . . . . . . . . . . . . . . . . . .

17

3.3.

Tú primero y tú después . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

3.4.

∗ El algoritmo A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

3.5.

Pero, ¾encontraré el óptimo? . . . . . . . . . . . . . . . . . . . . . . . . . .

22

3.5.1.

Admisibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

3.5.2.

Consistencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

3.5.3.

Heurístico más informado

. . . . . . . . . . . . . . . . . . . . . . .

25

Mi memoria se acaba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

3.6.

∗

3.6.1.

El algoritmo IDA

. . . . . . . . . . . . . . . . . . . . . . . . . . .

25

3.6.2.

Otras alternativas . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

4. Búsqueda local 4.1.

El tamaño importa, a veces

31 . . . . . . . . . . . . . . . . . . . . . . . . . .

3

31

4

ÍNDICE GENERAL

4.2.

Tu sí, vosotros no . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

4.3.

Demasiado calor, demasiado frío . . . . . . . . . . . . . . . . . . . . . . . .

35

4.4.

Cada oveja con su pareja . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

4.4.1.

Codicación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

4.4.2.

Operadores

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

4.4.3.

Combinación de individuos . . . . . . . . . . . . . . . . . . . . . . .

40

4.4.4.

El algoritmo genético canónico . . . . . . . . . . . . . . . . . . . . .

41

4.4.5.

Cuando usarlos

42

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5. Búsqueda con adversario

43

5.1.

Tú contra mi o yo contra ti

. . . . . . . . . . . . . . . . . . . . . . . . . .

43

5.2.

Una aproximación trivial . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

5.3.

Seamos un poco más inteligentes

. . . . . . . . . . . . . . . . . . . . . . .

46

5.4.

Seamos aún más inteligentes . . . . . . . . . . . . . . . . . . . . . . . . . .

48

6. Satisfacción de restricciones

51

6.1.

De variables y valores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

6.2.

Buscando de manera diferente . . . . . . . . . . . . . . . . . . . . . . . . .

52

6.2.1.

Búsqueda con backtracking

. . . . . . . . . . . . . . . . . . . . . .

53

6.2.2.

Propagación de restricciones . . . . . . . . . . . . . . . . . . . . . .

54

6.2.3.

Combinando búsqueda y propagación . . . . . . . . . . . . . . . . .

57

Otra vuelta de tuerca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

6.3.

7. Problemas resueltos

61

7.1.

Búsqueda heurística . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

7.2.

Búsqueda local

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

7.3.

Juegos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66

7.4.

Satisfacción de restricciones

68

. . . . . . . . . . . . . . . . . . . . . . . . . .

Capítulo 1 Resolución de problemas 1.1.

¾Qué es un problema?

Una de las principales capacidades de la inteligencia humana es su capacidad para resolver problemas. La habilidad para analizar los elementos esenciales de cada problema, abstrayéndolos, el identicar las acciones que son necesarias para resolverlos y el determinar cual es la estrategia más acertada para atacarlos, son rasgos fundamentales que debe tener cualquier entidad inteligente. Es por eso por lo que la resolución de problemas es uno de los temas básicos en inteligencia articial. Podemos denir la resolución de problemas como el proceso que partiendo de unos datos iniciales y utilizando un conjunto de procedimientos escogidos a priori, es capaz de determinar el conjunto de pasos o elementos que nos llevan a lo que denominaremos una solución. Esta solución puede ser, por ejemplo, el conjunto de acciones que nos llevan a cumplir cierta propiedad o como deben combinarse los elementos que forman los datos iniciales para cumplir ciertas restricciones. Evidentemente, existen muchos tipos diferentes de problemas, pero todos ellos tienen elementos comunes que nos permiten clasicarlos y estructurarlos. Por lo tanto, no es descabellada la idea de poder resolverlos de manera automática, si somos capaces de expresarlos de la manera adecuada. Para que podamos resolver problemas de una manera automatizada es necesario, en primer lugar, que podamos expresar las características de los problemas de una manera formal y estructurada. Eso nos obligará a encontrar un lenguaje común que nos permita denir problemas. En segundo lugar, hemos de denir algoritmos que representen estrategias que nos permitan hallar la solución de esos problemas, que trabajen a partir de ese lenguaje de representación y que nos garanticen hasta cierta medida que la solución que buscamos será hallada. Si abstraemos los elementos que describen un problema podemos identicar los siguien-

1

2

CAPÍTULO 1.

RESOLUCIÓN DE PROBLEMAS

tes elementos: 1. Un punto de partida, los elementos que denen las características del problema. 2. Un objetivo a alcanzar, qué queremos obtener con la resolución. 3. Acciones a nuestra disposición para resolver el problema, de qué herramientas disponemos para manipular los elementos del problema. 4. Restricciones sobre el objetivo, qué características debe tener la solución 5. Elementos que son relevantes en el problema denidos por el dominio concreto, qué conocimiento tenemos que nos puede ayudar a resolver el problema de una manera eciente. Escogiendo estos elementos como base de la representación de un problema podemos llegar a diferentes aproximaciones, algunas generales, otras más especícas. De entre los tipos de aproximaciones podemos citar:

Espacio de estados:

Se trata de la aproximación más general, un problema se divide en

un conjunto de pasos de resolución que enlazan los elementos iniciales con los elementos que describen la solución, donde en cada paso podemos ver como se transforma el problema.

Reducción a subproblemas:

En esta aproximación suponemos que podemos descom-

poner el problema global en problemas más pequeños de manera recursiva hasta llegar a problemas simples. Es necesario que exista la posibilidad de realizar esta descomposición.

Satisfacción de restricciones:

Esta aproximación es especíca para problemas que se

puedan plantear como un conjunto de variables a las que se han de asignar valores cumpliendo ciertas restricciones.

Juegos:

También es una aproximación especíca, en la que el problema se plantea como

la competición entre dos o mas agentes

1.2.

El espacio de estados

La aproximación más general y más sencilla es la que hemos denominado espacio de estados.

Deberemos suponer que podemos denir un problema a partir de los elementos

que intervienen en él y sus relaciones. En cada instante de la resolución de un problema estos elementos tendrán unas características y relaciones especícas.

estado a la representación de los elementos que describen el problema en un momento dado. Distinguiremos dos estados especiales, el estado inicial (punto de Denominaremos

1.2.

3

EL ESPACIO DE ESTADOS

partida) y el

estado nal (objetivo del problema). La cuestión principal que nos deberemos

plantear será qué debemos incluir en el estado. No existen unas directrices que nos resuelvan esta cuestión, pero podemos tomar como línea general que debemos incluir lo suciente para que, cuando obtengamos la solución, ésta pueda trasladarse al problema real, ya que una simplicación excesiva nos llevará a soluciones inservibles. En el otro extremo, representar elementos de estado que sean irrelevantes o superuos lo único que conseguirá es aumentar el coste computacional de la resolución. Para poder movernos entre los diferentes estados que denen el problema, necesitaremos lo que denominaremos

operadores de transformación. Un operador es una función de

transformación sobre la representación de un estado que lo convierte en otro estado. Los operadores denirán una relación de accesibilidad entre estados. Los elementos que denen un operador son:

1.

Condiciones de aplicabilidad, es decir, las condiciones que debe cumplir un estado para que podamos aplicárselo.

2.

Función de transformación,

es decir, la transformación que ha de aplicarse al

estado para conseguir otro.

Igual que con la elección de los elementos que forman parte del estado, tampoco existen unas directrices que nos permitan decidir, de manera general, que operadores serán necesarios para resolver el problema, cuantos serán necesarios, o que nivel de granularidad han de tener (como de diferente es el estado transformado respecto al original). Se puede dar el mismo consejo que con los estados, pocos operadores pueden hacer que nuestro problema sea irresoluble, o que la solución no nos sirva en el problema real, demasiados operadores pueden hacer que el coste de la resolución sea prohibitivo. Los estados y su relación de accesibilidad conforman lo que se denomina el

espacio

de estados. Éste representa todos los caminos que hay entre todos los estados posibles de

un problema. Podría asimilarse con un mapa de carreteras de un problema, la solución de nuestro problema esta dentro de ese mapa, sólo nos falta hallar el camino adecuado. El último elemento que nos queda por denir es la

solución.

La deniremos de dos

maneras, como la secuencia de pasos que llevan del estado inicial al nal (secuencia de operadores) o el estado nal del problema. Existen problemas en los que la secuencia de operadores es el objetivo de la solución, en éstos, por lo general, sabemos como es la solución, pero no sabemos como construirla, y existen tambien problemas en los que queremos saber si es posible combinar los elementos del problema cumpliendo ciertas restricciones, pero la forma de averiguarlo no es importante. Además, podremos catalogar diferentes tipos problema según el tipo de solución que busquemos, dependiendo de si nos basta con una cualquiera, queremos la mejor o buscamos todas las soluciones posibles. Evidentemente el coste computacional de cada uno de estos tipos es muy diferente.

4

CAPÍTULO 1.

En el caso de plantearnos el

RESOLUCIÓN DE PROBLEMAS

coste de una solución, deberemos introducir otros ele-

mentos en la representación del problema. Deniremos el coste de una solución como el gasto en recursos de la aplicación de los operadores a los estados, por lo que cada operador tendrá también asociado un coste. Vamos a ver dos ejemplos de como denir problemas como espacio de estados:

Ejemplo 1.1 El ocho puzzle es un problema clásico que consiste en un tablero de 9 posi-

ciones dispuesto como una matriz de 3×3 en el que hay 8 posiciones ocupadas por chas numeradas del 1 al 8 y una posición vacía. Las chas se pueden mover ocupando la posición vacía, si la tienen adyacente. El objetivo es partir de una disposición cualquiera de las chas, para obtener una disposición de éstas en un orden especíco. Tenemos una representación del problema en la siguiente gura:

1

2

3

4

5

6

7

8

La denición de los elementos del problema para plantearlo en el espacio de estados sería la siguiente: Espacio de estados: Conguraciones de 8 chas en el tablero Estado inicial: Cualquier conguración Estado nal: Fichas en un orden especíco Operadores: Mover el hueco • Condiciones: El movimiento está dentro del tablero • Transformación: Intercambio entre el hueco y la cha en la posición del movi-

miento

Solución: Que movimientos hay que hacer para llegar al estado nal, posiblemente nos interesa la solución con el menor número de pasos En esta denición hemos escogido como operador mover el hueco, evidentemente, en el problema real lo que se mueven son las chas, pero elegir el movimiento de una cha como

1.2.

EL ESPACIO DE ESTADOS

5

operador nos habría dado 8 posibles aplicaciones con 4 direcciones posibles para cada una. Al elegir el mover hueco como operador tenemos una única aplicación con 4 direcciones posibles. Este tipo de elecciones pueden hacer que un problema sea computacionalmente más o menos costoso de resolver.

Ejemplo 1.2 El problema de las N reinas es también un problema clásico, en este caso

el problema se trata de colocar N reinas en un tablero de ajedrez de N×N de manera que no se maten entre si. En este problema no nos interesa la manera de hallar la solución, sino el estado nal. En la gura tenemos representada la solución para un problema con dimensión 4:

Espacio de estados: Conguraciones de 0 a n reinas en el tablero con sólo una por la y columna Estado inicial: Conguración sin reinas en el tablero Estado nal: Conguración en la que ninguna reina se mata entre si Operadores: Colocar una reina en una la y columna • Condiciones: La reina no es matada por ninguna otra ya colocada • Transformación: Colocar una reina más en el tablero en una la y columna

determinada

Solución: Una solución, pero no nos importan los pasos También podríamos haber hecho otras elecciones como por ejemplo que el estado inicial tuviera las N reinas colocadas, o que el operador permitiera mover las reinas a una celda adyacente. Todas estas alternativas supondrían un coste de solución más elevado.

6

CAPÍTULO 1.

RESOLUCIÓN DE PROBLEMAS

Un elemento que será importante a la hora de analizar los problemas que vamos a solucionar, y que nos permitirá tomar decisiones, es el y su

conectividad.

tamaño del espacio de búsqueda

Este tamaño inuirá sobre el tipo de solución que podemos esperar

(por ejemplo, si el tamaño es demasiado grande, encontrar la solución óptima puede ser irrealizable), el tipo de algoritmo que es más adecuado, (por ejemplo, habrá algoritmos más aptos para soluciones que están más lejos del estado inicial), y cual será el coste computacional que implicará la resolución del problema. Es esencial, a la hora de plantear un problema, estimar cual es el número de estados que contiene. Por ejemplo, en el caso del ocho puzzle tenemos tantas combinaciones como posibles ordenes podemos hacer de las 9 piezas mas el hueco, esto signica 9! estados posibles (362880 estados). Probablemente no tendremos que recorrer todos los estados posibles del problema, pero nos puede dar una idea de si el problema será mas o menos

1

difícil de resolver . Otro elemento a considerar es la conectividad entre los estados, que se puede calcular a partir del factor de ramicación de los operadores que podemos utilizar. No es lo mismo recorrer un espacio de estados en el que de un estado podemos movernos a unos pocos estados sucesores, que un espacio de estados en los que cada estado esta conectado con casi todos los estados posibles. Esta es la razón por la que elegir operadores con un factor de ramicación no muy grande es importante. Pero debemos tener en cuenta una cosa, un factor de ramicación pequeño puede hacer que el camino hasta la solución sea más largo. Como siempre, hemos de buscar el compromiso, tener mucha conectividad es malo, pero muy poca también puede ser malo. En el caso del ocho puzzle, el factor de ramicación es 4 en el peor de los casos, pero en media podemos considerar que estará alrededor de 2.

1.3.

Algoritmos de búsqueda en el espacio de estados

La resolución de un problema planteado como un espacio de estados pasa por su exploración. Debemos partir del estado inicial marcado por el problema, evaluando cada paso posible y avanzando hasta encontrar un estado nal. En el caso peor deberemos explorar todos los posibles caminos desde el estado inicial hasta poder llegar a un estado que cumpla las condiciones del estado nal. Para poder implementar un algoritmo capaz de explorar el espacio de estados en busca de una solución primero debemos denir una representación adecuada de éste. Las estructuras de datos más adecuadas para representar el espacio de estados son los grafos y los árboles. En estas estructuras cada nodo de representará un estado del problema y los ope-

1 Se

solía comentar hace unos años que problemas que tengan menos de 232 estados eran la frontera de los problemas sencillos y que se pueden resolver por fuerza bruta simplemente enumerándolos todos, con la capacidad de cálculo actual probablemente ahora ese número mínimo de estados sea bastante mayor.

1.3.

ALGORITMOS DE BÚSQUEDA EN EL ESPACIO DE ESTADOS

7

radores de cambio de estado estarán representados por los arcos. La elección de un árbol o un grafo la determinará la posibilidad de que a un estado sólo se pueda llegar a través de un camino (árbol) o que haya diferentes caminos que puedan llevar al mismo estado (grafo). Los grafos sobre los que trabajarán los algoritmos de resolución de problemas son diferentes de los algoritmos habituales sobre grafos. La característica principal es que el grafo se construirá a medida que se haga la exploración, dado que el tamaño que puede tener hace imposible que se pueda almacenar en memoría (el grafo puede ser incluso innito). Esto hace que, por ejemplo, los algoritmos habituales de caminos mínimos en grafos no sirvan en este tipo de problemas. Nosotros nos vamos a centrar en los algoritmos que encuentran una solución, pero evidentemente extenderlo a todas las soluciones es bastante sencillo. Este sería un esquema a alto nivel de un algoritmo que halla una solución de un problema en el espacio de estados:

funcion mientras

retorna

Busqueda_en_espacio_de_estados

Seleccionar el

y

Generar Escoger

fmientras retorna ffuncion

el

el

primer

estado guardar

estado

actual

no es

sucesores

siguiente

como

estado

el

el

del

estado

estado

estado

entre

los

solucion

actual

final

actual

hacer

( expansion )

pendientes

( seleccion )

solucion

En este algoritmo tenemos varias decisiones que nos permitirán obtener diferentes variantes que se comportarán de distinta manera y que tendrán propiedades especícas. La primera decisión es el

orden de expansión,

o lo que es lo mismo, el orden en el que

generamos los sucesores de un nodo. La segunda decisión es el

orden de selección, o sea,

el orden en el que decidimos explorar los nodos que aún no hemos visitado. Entrando un poco más en los detalles de funcionamiento del algoritmo, podremos dis-

nodos abiertos, que representarán a los estados generados pero aún no visitados y los nodos cerrados, que corresponderán a los estados visitados y

tinguir dos tipos de nodos, los que ya se han expandido.

Nuestro algoritmo siempre tendrá una estructura que almacenará los nodos abiertos. Las diferentes políticas de inserción de esta estructura serán las que tengan una inuencia determinante sobre el tipo de búsqueda que hará el algoritmo. Dado que estaremos explorando grafos, y que por lo tanto durante la exploración nos encontraremos con estados ya visitados, puede ser necesario tener una estructura para almacenar los nodos cerrados. Merecerá la pena si el número de nodos diferentes es pequeño respecto al número de caminos, pero puede ser prohibitivo para espacios de búsqueda muy grandes. A continuación tenemos un algoritmo algo más detallado que nos va a servir como

8

CAPÍTULO 1.

RESOLUCIÓN DE PROBLEMAS

esquema general para la mayoría de los algoritmos que iremos viendo:

Algoritmo

Busqueda

General

E s t _ a b i e r t o s . i n s e r t a r ( Estado A c t u a l=

inicial )

Est_abiertos . primero ( )

mientras no

e s _ f i n a l ?( Actual )

y no

Est_abiertos . vacia ?()

hacer

Est_abiertos . borrar_primero ( ) Est_cerrados . i n s e r t a r ( Actual ) H i j o s=

generar_sucesores ( Actual )

H i j o s=

tratar_repetidos ( Hijos ,

Est_cerrados ,

Est_abiertos )

Est_abiertos . i n s e r t a r ( Hijos ) A c t u a l=

fmientras fAlgoritmo

Est_abiertos . primero ( )

Variando la estructura de abiertos variamos el comportamiento del algoritmo (orden de visita de los nodos). La función

generar_sucesores

seguirá el orden de generación

de sucesores denido en el problema. El tratamiento de repetidos dependerá de cómo se visiten los nodos, en función de la estrategia de visitas puede ser innecesario. Para poder clasicar y analizar los algoritmos que vamos a tratar, escogeremos unas propiedades que nos permitirán caracterizarlos. Estas propiedades serán:

Completitud:

Si un algoritmo es completo tenemos la garantía de que hallará la

solución, si no lo es, es posible que algoritmo no acabe o que sea incapaz de encontrarla.

Complejidad temporal:

Nos indicará el coste temporal de la búsqueda en fun-

ción del tamaño del problema, generalmente a partir del factor de ramicación y la profundidad a la que se encuentra la solución.

Complejidad espacial: Espacio requerido para almacenar los nodos pendientes de explorar. También se puede tener en cuenta el espacio para almacenar los nodos ya explorados si es necesario para el algoritmo

Optimalidad:

Si es capaz de encontrar la mejor solución según algún criterio de

preferencia o coste. Atendiendo a estos criterios podemos clasicar los algoritmos principales que estudiaremos en:

Algoritmos de búsqueda no informada: Estos algoritmos no tienen en cuenta el coste de la solución durante la búsqueda. Su funcionamiento es sistemático, siguen un orden de visitas de nodos jo, establecido por la estructura del espacio de búsqueda. Los principales ejemplos de estos algoritmos son el de anchura prioritaria, el de profundidad prioritaria y el de profundidad iterativa.

1.3.

ALGORITMOS DE BÚSQUEDA EN EL ESPACIO DE ESTADOS

9

Algoritmos de búsqueda heurística y búsqueda local: Estos algoritmos utilizan una estimación del coste o de la calidad de la solución para guiar la búsqueda, de manera que se basan en algún criterio heurístico dependiente del problema. Estos algoritmos no son sistemáticos, de manera que el orden de exploración no lo determina la estructura del espacio de búsqueda sino el criterio heurístico. Algunos de ellos tampoco son exhaustivos y basan su menor complejidad computacional en ignorar parte del espacio de búsqueda. Existen bastantes algoritmos de este tipo con funcionamientos muy diferentes, no siempre garantizan el encontrar la solución óptima, ni tan siquiera el hallar una ∗ ∗ solución. Los principales ejemplos de estos algoritmos son A , IDA , Branch & Bound, Hill-climbing.

10

CAPÍTULO 1.

RESOLUCIÓN DE PROBLEMAS

Capítulo 2 Búsqueda no informada 2.1.

Búsqueda independiente del problema

Los algoritmos de búsqueda no informada (también conocidos como algoritmos de búsqueda ciega), no dependen de información propia del problema a la hora de resolverlo. Esto quiere decir que son algoritmos generales y por lo tanto se pueden aplicar en cualquier circunstancia. Estos algoritmos se basan en la estructura del espacio de estados y determinan estrategias sistemáticas para su exploración. Es decir, siguen una estrategia ja a la hora de visitar los nodos que representan los estados del problema. Se trata también de algoritmos exhaustivos, de manera que pueden acabar recorriendo todos los nodos del problema para hallar la solución. Existen básicamente dos políticas de recorrido de un espacio de búsqueda, en anchura y en profundidad. Todos los algoritmos que se explicarán a continuación se basan en una de las dos. Al ser algoritmos exhaustivos y sistemáticos su coste puede ser prohibitivo para la mayoría de los problemas reales, por lo tanto sólo será aplicables en problemas pequeños. Su ventaja es que no nos hace falta obtener ningún conocimiento adicional sobre el problema, por lo que siempre son aplicables.

2.2.

Búsqueda en anchura prioritaria

La búsqueda en anchura prioritaria intenta explorar el espacio de búsqueda haciendo un recorrido por niveles, de manera que un nodo se visita solamente cuando todos sus predecesores y sus hermanos anteriores en orden de generación ya se han visitado. Para obtener este algoritmo solo hemos de instanciar la estructura que guarda los nodos abiertos a una cola. Esta estructura nos consigue que el algoritmo general visite los nodos

11

12

CAPÍTULO 2.

BÚSQUEDA NO INFORMADA

en el orden que hemos establecido. Si nos jamos en las propiedades que hemos escogido para clasicar los algoritmos:

Completitud: El algoritmo siempre encuentra una solución. Complejidad temporal: El coste es exponencial respecto al factor de ramicación y p la profundidad de la solución O(r ). Complejidad espacial: El coste es exponencial respecto al factor de ramicación y la p profundidad de la solución O(r ). Optimalidad: La solución obtenida es óptima respecto al número de pasos desde la raíz.

Respecto al tratamiento de nodos repetidos, si nos jamos en la gura que aparece a continuación:








 














            





 
           





  













      
      





  
 
 
 
 
  









 






 

   


   


 
  

  




 

 


    
      


   
  









 






    
  




     



  




     



 



      

 



      

 





 
 
  
 
 

 
  














   

















 

      










 
     


     





  










      
       






 







 













 



El nodo de color negro sería el nodo generado actual, los nodos en cuadrícula son nodos cerrados y los nodos rayados son nodos abiertos. Si el nodo generado actual está repetido en niveles superiores (más cerca de la raíz), su coste será peor ya que su camino desde la raíz es más largo, si está al mismo nivel, su coste será el mismo. Esto quiere decir que su coste será peor o igual que algún nodo anterior visitado o no, de manera que lo podremos descartar, ya que o lo hemos expandido ya o lo haremos próximamente. El coste espacial de guardar los nodos cerrados para el tratamiento de repetidos es

O(rp ).

2.3.

Búsqueda en profundida prioritaria

La búsqueda en profundidad prioritaria intenta seguir un camino hasta la mayor profundidad posible, retrocediendo cuando acaba el camino y retomando la última posibilidad de elección disponible.

2.3.

13

BÚSQUEDA EN PROFUNDIDA PRIORITARIA

Para obtener este algoritmo solo hemos de instanciar la estructura que guarda los nodos abiertos a una pila. Esta estructura nos consigue que el algoritmo general visite los nodos en el orden que hemos establecido. El principal problema de este algoritmo es que no acaba si existe la posibilidad de que hayan caminos innitos. Una variante de este algoritmo que evita este problema es el algoritmo de

profundidad limitada,

éste impone un límite máximo de profundidad

que impone la longitud máxima de los caminos recorridos. Esta limitación garantiza que el algoritmo acaba, pero no garantiza la solución ya que esta puede estar a mayor profundidad que el límite impuesto. El algoritmo de profundidad limitada es el siguiente:

Algoritmo

Busqueda

en

profundidad

E s t _ a b i e r t o s . i n s e r t a r ( Estado A c t u a l=

Est_abiertos . primero ( )

mientras no

limitada

( limite :

entero )

inicial )

e s _ f i n a l ?( Actual )

y no

Est_abiertos . vacia ?()

hacer

Est_abiertos . borrar_primero ( ) Est_cerrados . i n s e r t a r ( Actual )

si

p r o f u n d i d a d ( A c t u a l )