Casos de aplicación de algoritmos de búsqueda

(1) Título: Reversi Game

El tablero del juego Reversi consta de una cuadrícula cuadrada de 4×4. Hay 1 pieza de ajedrez en cada casilla del tablero de ajedrez. Hay 8 piezas de ajedrez blancas y 8 piezas de ajedrez negras. Cada plan de colocación de estas 16 piezas de ajedrez constituye un estado de juego. Dos casillas que tienen un lado común en el tablero de ajedrez se llaman casillas adyacentes. Un cuadrado puede tener hasta 4 cuadrados adyacentes. Al jugar Reversi, cada movimiento puede intercambiar las posiciones de las piezas en dos cuadrados adyacentes. Para un estado de juego inicial y un estado de juego objetivo dados, el programa calcula la secuencia más corta de movimientos desde el estado de juego inicial hasta el estado de juego objetivo.

(2) Análisis

Podemos pensar en utilizar la búsqueda en profundidad para resolver este problema, pero ¿qué pasa si el estado anterior aparece en el siguiente paso? Puede resultar un poco difícil juzgar directamente la complejidad del tiempo. La solución óptima a este problema es utilizar la búsqueda en amplitud. Podemos hacer que el estado inicial expanda cada punto de acuerdo con el recorrido de búsqueda en amplitud, de modo que la cantidad de pasos para alcanzar el estado objetivo debe ser óptima (la cantidad de pasos aumenta monótonamente). Pero el problema es que si hay una situación duplicada, debemos juzgar el peso, pero el juicio de peso simple puede alcanzar el nivel de número de estado. De hecho, podemos considerar usar una tabla hash para juzgar el peso.

Tabla hash: La idea es realizar un acceso directo en función del valor de la clave. Es decir, el proceso de asignar un valor clave a una ubicación en la tabla para acceder al registro. En una tabla Hash, la complejidad temporal de la inserción y búsqueda general se puede lograr dentro de la complejidad temporal de O (1). Para esta pregunta, podemos usar un valor binario para representar su valor hash, hasta 2 ^ 16 de potencia, por lo que abrimos una tabla de potencia de 2 ^ 16 para registrar si ocurre este estado, de modo que la complejidad del tiempo pueda estar dentro de O (1 ) Resolver el problema del juicio pesado.

Consideración adicional: desde el estado inicial hasta el estado objetivo, inevitablemente se generarán muchos estados inútiles. Entonces, ¿qué optimizaciones pueden reducir esta complejidad temporal? Podemos considerar expandir el estado inicial y el estado objetivo juntos, de modo que si un cierto punto expandido del estado inicial es el mismo que el punto expandido del estado objetivo, entonces no es necesario expandir estos dos puntos, y el número de pasos de las dos expansiones es Esa es la respuesta.

La idea anterior es una búsqueda bidireccional de amplitud primero:

Al igual que en la Figura 2, se expanden muchos estados innecesarios.

De la pregunta anterior, podemos ver que utilizamos dos métodos de optimización, a saber, la optimización de la tabla hash y la optimización de búsqueda bidireccional. La búsqueda general en amplitud es suficiente para resolver con estas dos optimizaciones.