¿Usando el algoritmo de búsqueda A * para resolver el rompecabezas de caja tridimensional 3x3?

Question

Estoy trabajando en un problema de rompecabezas tridimensional de 3x3 en mi tarea. Voy a codificar con C.

Hay 26 cajas y en un primer momento, el primer lugar se encuentra vacío. Al deslizar las cajas, debo arreglarlas en el orden correcto. Los números rojos muestran el orden correcto y el lugar 27 debe estar vacío al fin. No quiero que me des código; Busqué en foros y parece que debo usar el A* search algorithm, pero ¿cómo?

¿Puede darme consejos sobre cómo puedo usar el algoritmo A * sobre este problema? ¿Qué tipo de estructura de datos debo usar?

Answer 1

Ya sabes cómo funcionan los gráficos y cómo A * encuentra los caminos más cortos en ellos, ¿verdad?

La idea básica es que cada configuración del rompecabezas se puede considerar un vértice en un gráfico y los bordes representan los movimientos (conectando las configuraciones antes y después del movimiento).

Encontrar un conjunto de movimientos que conducen desde una configuración original a la deseada puede verse como un problema de búsqueda de ruta.

Answer 2

definir su problema como un estados-gráfico:
G=(V,E) donde V=S={(x_1,x_2,...,x_54) | all possible states the 3d board can be in} [cada número representa a un único 'cuadrado' en el tablero 3d].
y definir E={(v1,v2)| it is possible to move from state v1 to state v2 with a single step} una definición alternativa [idénticos] para E es mediante el uso de la función successors(v):
Para cada v en V: successors(v)={all possible boards you can get, with 1 step from v}

Usted también necesitará un admissible heuristic function, uno bastante bueno para este problema puede ser: h(state)=Sigma(manhattan_distance(x_i)) where i in range [1,54]) básicamente, es la suma de manhattan distances para cada número de su objetivo.

Ahora, una vez que tenemos estos datos, podemos comenzar a ejecutar A * en el gráfico definido G, con la heurística definida. Y dado que nuestra función heurística es admisible [¡convencerse por qué!], Se garantiza que la solución A * descubierta será óptima, debido a admissibility and optimality of A*.
Encontrar la ruta real: A * terminará cuando desarrolle el estado objetivo. [x_i=i en los términos que utilizamos anteriormente]. Encontrará su camino al retroceder desde el destino al origen, utilizando el campo parent en cada nodo.