EJERCICIO

3 DE JUNIO DE 2014

Ejercicio de clases:       BUSTE ZAMBRANO JOSE ORLANDO.

                              

Definiciones.

Estado.-  Es la situación en la que el agente  se puede encontrar en los posibles estados del mundo.

Espacio de estados.- son las acciones definidas por las funciones sucesoras del estado inicial hacia la cada uno de los nodos.

Árbol de búsqueda.-  un árbol de búsqueda es un grafo que define el estado inicial y aquellas funciones sucesoras que están dentro del problema en forma de nodos hacía una posible solución.

Nodo de búsqueda.-  el nodo de búsqueda es el nodo raíz donde se encuentra el estado inicial del problema.

Objetivo.- objetivo es la solución del problema que se plantea el agente, limita la meta que intenta alcanzar el agente.

Acción.- acción es cada una de las situaciones que puede realizar el agente.

Función sucesor.- es toda aquella acciones que el agente puede realizar par a alcanzar la función objetivo.

Factor de ramificación.- es el número  máximo de nodo sucesores que puede alcanzar un grafo.

Función sucesor en términos acciones legales y resultado.

FUNCION-SUCESOR (acción legal[a], sucesor [X])

Función sucesor en términos resultados y acciones legales.

FUNCION-SUCESOR (sucesor [X], acción legal[a])

v  Un espacio de estado finito siempre determina un árbol de búsqueda finito.

v  Un estado de espacio finito es un árbol siempre y cuando contengan niveles de profundidad y ramificaciones producidas por los nodos.

a)      formulación del problema:

Estado: misioneros y caníbales en un lugar del rio.

Estado inicial: ningún misionero o caníbal al otro lado del rio.

Función sucesor: pasar un caníbal al otro lado.

Test objetivo: conseguir que todos estén al otro lado sin dejar alguna vez a un grupo de misioneros en un lugar excedido en número por los caníbales.

Orilla 0	Rio, barco	Orilla 1
mmm, ccc		mmm, ccc
Nodo inicial 3c,3m,1		Nodo objetivo 0c,0m`,0

Búsqueda por profundidad;

………….

No es buena idea comprobar los estados repetidos porque se volvería  un problema muy extenso, pero garantizaría la optimización de la solución.

c) se nos hace difícil porque estamos adiestrado a pensar de una manera que  descartamos aquellas posibilidades que a primera vista no presentan la respuesta que buscamos.

 

  

Se demuestra que la búsqueda de costo uniforme y la búsqueda primero en anchura con costos constantes son más óptima cuando se utiliza con el algoritmo de BUSQUEDA-GRAFOS  porque estas no  permiten descartar   una solución óptima.

La BUSQUEDA-GRAFOS,  utilizando profundidad interactiva  genera un camino subóptimo al  comprobar si un camino recién descubierto a un nodo es mejor que el original, de esta manera revisa las profundidades y los costos del camino  descendiente de ese nodo.