El algoritmo de Warnsdorff es un método heurístico muy simple para resolver el recorrido del caballero.
Desde este algoritmo puedes comenzar desde cualquier posición inicial del caballero en el tablero.
Regla de Warnsdorff: siempre muévete a un cuadrado adyacente no visitado con un grado mínimo.
ALGORITMO PARA IMPLEMENTAR LA REGLA WARNSDORFF:
• Se puede acceder a una posición Q desde una posición P si P puede moverse a Q mediante un solo movimiento de Caballero, y Q aún no ha sido visitado.
• La accesibilidad de una posición P es el número de posiciones accesibles desde P.
• Algoritmo:
1. establecer P para ser una posición inicial aleatoria en el tablero
2. marque el tablero en P con el número de movimiento “1”
3. para cada número de movimiento del 2 al número de casillas en el tablero:
- Cómo conectar el modelo BPMN con la estructura de datos existente
- En el algoritmo EM, ¿debería aumentar el valor de la función objetivo a través de cada M-STEP?
- ¿Qué libro sobre algoritmos es una lectura obligada para un programador?
- ¿Por qué el hashing geométrico es más eficiente que usar una matriz indexada de las coordenadas de los puntos característicos?
- ¿Cuál es la razón por la que el conjunto de todos los enteros contiene 0?
—1. deje que S sea el conjunto de posiciones accesibles desde la posición de entrada
—2. establecer P para ser la posición en S con accesibilidad mínima
—3. marque el tablero en P con el número de movimiento actual
—4. devuelva el tablero marcado: cada casilla se marcará con el número de movimiento en el que se visita.
Si está interesado en ver el programa C para generar Knight’s Tour en un tablero de ajedrez 8 × 8 utilizando Warnsdorff Heuristics, consulte mi repositorio de Github:
bhaduriu / misc_progs_in_C-and-Cplusplus
🙂
