busqueda en amplitud

[walrus86]

hola como andan? tengo un problema a ver si me puede ayudar

tengo un tablero de ajedrez, pongo un caballo negro y y varios caballos blancos esparcidos aleatoriamente en el tablero. Necesito encontrar la secuencia más corta de pasos en los que el caballo negro se come todos los blancos.

Me piden hacerlo con busqueda por profundidad y por amplitud. Con busqueda por profundidad no tuve ningun problema pero con amplitud si. Ocupo alguno de los algoritmos que encuentro por ahi en la web, pero no encuentro la manera de ir registrando los movimientos que hace el caballo negro una vez que encuentra la solucion (es decir cuando no quedan mas caballos blancos en el tablero)

A alguien se le ocurre una idea??? les agradezco mucho si me ayudan con esta que me está dando un terrible dolor de cabeza jaja

salu2

[Heimish2000]

Supongo que tendrás que hacer un arbol para la decisión. Puedes hacer dos cosas:

1) Guardar en cada nodo toda la secuencia que te ha llevado a ese nodo, en cuyo caso al consultar ese nodo ya tienes la secuencia entera.

2) Guardar en cada nodo el último movimiento, el movimiento que te ha llevado a ese nodo. Luego tienes que ir recorriendo el árbol desde la base hasta ese nodo para tener la secuencia de movimientos (o desde ese nodo hasta la base)

A mi me gusta más la segunda, pero las dos son válidas.

[walrus86]

claro te entiendo, pero justamente no se cómo hacer para avanzar de nodos e ir guardando la secuencia, por que al recorrer por amplitud tengo que recorrer todos los nodos de un nivel primero antes de pasar a los del siguiente nivel, y una vez que paso al sig. nivel no tengo manera de distinguir cuál fue el nodo padre del nodo que estoy tratando ahora, me entendes?

[Heimish2000]

Guarda una referencia en el nodo a su padre y problema solucionado.

[walrus86]

mmm... dejame probar a ver si me sale