Búsqueda por costo uniforme
Esta búsqueda tiene únicamente en cuenta el costo del camino recorrido, por
lo cual la mejor solución en esta búsqueda está representada única y
exclusivamente, por el menor costo en camino a la solución.
Se desea resolver el siguiente problema aplicando búsqueda por costo
uniforme:
N
|
N
|
|
B
|
B
|
En el problema N representa a un
caballo negro y B a un caballo
blanco, estos se mueven como reglamenta el ajedrez el movimiento de estas
fichas, se desea que moviéndose solo en L,
los caballos negros pasen a la posición de los caballos blancos y viceversa.
Para este ejercicio se desea aplicar la búsqueda por costo uniforme.
Hay que tener en cuenta a g(n) y a f(n), que en su respectivo orden son
costo del camino recorrido y costo del nodo.
Sabiendo eso planteamos lo siguiente:
Para solucionar este problema, se determina que hay que hacer 16 pasos, en
los que cada ficha se mueve 4 veces para lograr la posición final. Que sería:
Estado final
B
|
B
|
|
N
|
N
|
Figura 1 (8 posibles jugadas)
Como se puede ver a partir del nodo inicial se generan 8 posibles caminos
generando un árbol con un factor de ramificación de 8 nodos. Numerándolos de
izquierda a derecha, el numero 4 es la forma correcta de iniciar para encontrar
una solución. Pero a su vez a partir de 4 podríamos hacer varios movimientos.
Es decir:
Figura 2 (Nodo 4 camino a la solución)
En esta instancia ya nos podemos imaginar la cantidad de rutas y caminos
que se pueden tomar, pero si hiciéramos todas las combinaciones no
terminaríamos nunca.., por ende solo nos guiaremos por la ruta del nodo 4 luego
el nodo 1 hasta la solución.
figura 3 (Solución a partir del
nodo 4)
El anterior es el recorrido paso a
paso que deben tomar desde el nodo después de segundo nivel nodo 4, tercer
nivel nodo 1, hasta la solución.
Ahora para entender bien en que consiste el nodo de costo uniforme, hagamos
una comparación entre la ruta directa y la ruta que anteriormente veíamos que
volvía al Estado inicial, solo nos basaremos en esas dos rutas de la
siguiente manera.
Asimilando lo que venimos explicando vamos a plantear el siguiente grafo
A = nodo inicial
Los nodos descendientes de A serán numerados de acuerdo a la primera
expansión que se ve en la figura 1,
desde el nodo 4 se plantean los nodos como están en la figura 2, también el
nodo 6 hijo de 4 en el segundo nivel
sería como volver a el nodo A por ello deduciremos el análisis a partir
de eso
Nota: En este caso vamos a
suponer que todo movimiento tiene costo de una unidad
Por ejemplo ir de A al nodo 4
vale una unidad.
La búsqueda por costo uniforme en el caso que se plantea anteriormente, con
los dos caminos de solución propuestos determinaría que la mejor solución está
en el camino uno porque el recorrido seria:
A, 4, 1, + 14 nodos.
El costo total seria por cada nodo recorrido 1 unidad, así el costo total
para este recorrido seria:
A a 4 = 1 unidad
4 a 1 = 1 unidad + 1 unidad = 2 unidades
1 a Solución = 1 unidad + 1 unidad + 14 unidades = 16 unidades.
El otro recorrido seria:
A, 4, 6, 4, 1, +14 nodos hasta la solución.
Lo anterior suponiendo que cuando vuelve al origen, encuentra el camino
propuesto en la primera solución.
El costo total seria:
A a 4 = 1 unidad
4 a 6 = 1 unidad + 1 unidad
6 a 4 = 1 unidad + 1 unidad + 1 unidad
4 a 1 = 1 unidad + 1 unidad + 1 unidad + 1 unidad
1 a solución = 14 unidades + 1 unidad + 1 unidad + 1 unidad + 1 unidad
Este recorrido costaría 18 unidades en
comparación con el anterior, por lo cual el costo uniforme determinaría que la
mejor solución es la primera y así podemos ver como el costo uniforme
selecciona la mejor solución.
No hay comentarios:
Publicar un comentario