Formalizacion de un problema
problema de las ranitas
en el siguiente problema se busca llegar de un estado inicial a un estado final como se muestra a continuacion:
A) Formalizacion:
factor de ramificacion: 4
Recorrido en la mejor solucion planteada:
nodos generados:4^17
nodos expandidos:4^16
nodos hoja:(4^17-4^17)
teniendo en cuenta el problema anterior, se deduce que el algoritmo DFS encontraria la mejor solucion en 17 pasos, si y solo si los sucesores se dan de la manera en que se plantea en la imagen anterior, de tal forma que siempre escogeria el mejor camino y daria con la solucion, en caso de que los sucesores se den de otra manera, podria demorarse mas en la solucion, y por ende podria nunca encontrar la solucion al problema planteado.
en el siguiente problema se busca llegar de un estado inicial a un estado final como se muestra a continuacion:
A) Formalizacion:
Estados posibles: 7!
operadores:
- saltar izquierda si dos casillas a la izquierda esta vacia
- saltar derecha si dos casillas a la derechaesta vacia
- desplazarse izquierda si una casilla a la izquierda esta vacia
- desplazarce derecha si una casilla a la derecha esta vacia
factor de ramificacion: 4
Recorrido en la mejor solucion planteada:
nodos generados:4^17
nodos expandidos:4^16
nodos hoja:(4^17-4^17)
teniendo en cuenta el problema anterior, se deduce que el algoritmo DFS encontraria la mejor solucion en 17 pasos, si y solo si los sucesores se dan de la manera en que se plantea en la imagen anterior, de tal forma que siempre escogeria el mejor camino y daria con la solucion, en caso de que los sucesores se den de otra manera, podria demorarse mas en la solucion, y por ende podria nunca encontrar la solucion al problema planteado.
en la imagen presentada anteriormente se presenta el seudocodigo del algoritmo DFS.
Comentarios
Publicar un comentario