Estados Simple

7/30/2019 Estados Simple

1/20

Tcnicas de Bsqueda

MSc. Edgar Taya Acosta


2/20

Tcnicas de Bsqueda Bsqueda en espacio de estados Estrategias de bsqueda simple (Profundidad y

Amplitud)

Tcnicas de Bsqueda


3/20

Bsqueda en espacio deestados

En la gran mayora de problemas, si abstraemos sus elementospodemos identificar:

Un punto de partida.Un objetivo a alcanzar.

Elementos que son relevantes en el problema definidos porel tipo de dominio.Acciones a nuestra disposicin para resolver el problema.Restricciones sobre el objetivo.Ej.:


4/20

Acciones, Restricciones y elementos relevantes

Elemento obj.

Puede serObj1, Obj2, mesa

SitioPuede ser

Sitio1, Sitio2



5/20

En cada instante de la resolucin de un problema esoselementos tendrn unas caractersticas y relacionesespecficas.

Denominaremos Estado a la representacin de los

elementos que describen el problema en un momento.

Distinguiremos dos estado especiales el Estado Inicial(punto de partida) y el Estado Final (objetivo del problema).

Ej. Estado (no Inicial, no Final):

Sobre (Obj1,Obj2)Sobre (Obj2,mesa)En (mesa, sitio1)En (Robot, sitio1)ManoVaciaGrande (mesa)

Despejado (Obj1)



6/20

Los estados y su relacin de accesibilidad conforman lo que sedenomina espacio de estados.

Representa todos los caminos que hay entre todos los estados

posibles de un problema.

Podra asimilarse con un mapa de carreteras de un problema.

La solucin de nuestro problema esta dentro de ese mapa

Si en el ejemplo anterior realizramos todas las posiblescombinaciones de estados podramos llegar desde cualquierestado inicial a cualquier estado final.



7/20


Ej.: problema de los tres bloques

A B C

((A)(B)(C))

A

B C

A

CB A

B

C A

B

C A B

C

A B

C

((AB)(C)) ((B)(AC)) ((BA)(C)) ((A)(BC)) ((CA)(B)) ((A)(CB))

Restriccin: para realizarcualquier movimiento losdos elementos implicadosdeben estar despejados


8/20

A

((A)(B)(C))

A

B C

A

CB

AB

C ABC

A B

C

A B

C

((AB)(C))

((B)(AC))

((BA)(C)) ((A)(BC))

((CA)(B))

((A)(CB))

B C

A

B

C

((CBA))

A

B

C((ABC))

B

A

C

((CAB))

B

A

C

((BAC))A

C

B

((ACB))

B

C

A

((BCA))

Bsqueda en espacio de estados(Grafo de estados explicito)


9/20

Bsqueda en espacio de estados(Busqueda en estados explcitos)

0

1

0

1

2 2

0

1

2 2

3

3

3

33

0

1

2 2

3

3

3

33

4

4

44


10/20

Muchos de los problemas de inters practico tienen unosespacios de bsqueda tan grandes que no pueden serrepresentados mediante un grafo explicito. Es por esta raznque se crearon nuevos algoritmos de bsqueda quepermitieran generar de forma implcita el grafo de estados yposteriormente aplicar mtodos eficientes de bsquedasobre dichos grafos de gran tamao. Dichos algoritmos seclasifican en 2 grupos:

Algoritmos de bsqueda ciega

Algoritmos de bsqueda heurstica

Bsqueda en espacio de estados(Bsqueda en estados implcitos)


11/20

Algoritmos de bsqueda ciega

No tienen en cuenta el coste de la solucin en la bsqueda.

Su funcionamiento es sistemtico, siguen un orden devisitas y generacin de nodos establecido por la estructuradel espacio de bsqueda.

Este tipo de algoritmos funcionan aplicando todos losoperadores disponibles a los nodos.

Existe dos algoritmos muy conocidos en este grupo:Primero en amplitud.Primero en Profundidad.


12/20

Algoritmos de bsqueda ciegaPrimero en amplitud

En este algoritmo se va construyendo un grafo de estadosexplcitos mediante la aplicacin de los operadoresdisponibles al nodo inicial, luego aplica los operadoresdisponibles a los nodos sucesores directos del nodo inicial, yas sucesivamente.


13/20

Los nodos se visitan y generan por niveles.Un nodo es visitado cuando todos los nodos de los niveles

superiores y sus hermanos precedentes han sido visitados.

Caractersticas:Completitud: El algoritmo siempre encuentra una solucin.Complejidad temporal y espacial : Exponencial respecto alfactor de ramificacin y la profundidad de la solucin.

Optimalidad: La solucin que se encuentra es ptima ennmero de niveles desde la raz.



14/20

s

a d

a eb d

c e b fbe

d f b f d e a c g

g c g f

g

1 2

3 4 5 6

7 8 9 10 11 12

13 14 15 16 17 18 19 20 21


Nodo Inicio

Nodo Objetivo


15/20

Algoritmos de bsqueda ciegaPrimero en Profundidad

En este algoritmo se genera solo un sucesor del nodo encada paso; es decir, cada vez que obtenemos un nuevosucesor, se le aplica a este un operador y se obtiene unnuevo sucesor, y asi sucesivamente.


16/20

Los nodos se visitan y generan buscando los nodos a mayor

profundidad y retrocediendo cuando no se encuentran nodossucesores.Para garantizar que el algoritmo acaba debe imponerse unlmite en la profundidad de exploracin.

Caractersticas

Completitud: El algoritmo encuentra una solucin si seimpone un lmite de profundidad y existe una solucindentro de ese lmite.Complejidad temporal y espacial : Exponencial respectoal factor de ramificacin y la profundidad del lmite deexploracin.Optimalidad: No se garantiza que la solucin sea ptima



17/20

s

a d

a eb d

c e b fbe

d f b f d e a c g

g c g f

g

1

2

3 4

56

7

Nodo Inicio

Nodo Objetivo



18/20

Algoritmos de bsqueda ciegaEjercicio

Aplicando el mtodo de bsqueda ciega Primero en amplitudrealice el siguiente ejercicio.

Se tienen dos jarrones, uno de 4 y otro de 3 litros.

Ninguno tiene marcas de medidas sobre l.

cmo podemos obtener exactamente 2 litros en el jarrn de3?

Tambin se tiene una toma de agua que puede usarse para

llenar los jarrones (solo se pueden utilizar para llenar losjarrones hasta el tope).

Podemos vaciar agua de un tanque a otro (Hasta que quedelleno o vaci un tanque)


19/20

Algoritmos de bsqueda ciegaEjercicio


20/20

Bibliografa

Nils J. Nilsson. INTELIGENCIA ARTIFICIAL: Una Nueva Sntesis,

Ed McGraw-Hill 2001.

Documents

Estados Simple