java - breadth - depth first search geeksforgeeks

Breadth-First búsqueda en Java

Question

Tengo que ejecutar una búsqueda de ancho en Java para una tarea. Tengo una cuadrícula de mosaicos de 5x5 (24 en total: 1 ficha se deja ''en blanco''). El objetivo de la búsqueda es reorganizar las fichas moviendo el "espacio en blanco" hacia arriba, hacia abajo, hacia la izquierda o hacia la derecha para reorganizar las fichas en el orden correcto.

Para hacer esta búsqueda, he creado una "cola" del Arraylist. Tengo un método que toma el estado en el índice 0 de esta lista de arrays, encuentra cada uno de los movimientos legales que pueden seguir y luego los agrega cada uno al final de la lista de arrays.

En teoría, esto continúa hasta que finalmente se encuentre el ''goalstate''. El problema es que cuando ejecuto la búsqueda, la lista de espera ''queue'' simplemente se hace cada vez más grande. Hoy lo dejé funcionando durante horas y todavía no se había encontrado la solución.

Esto sugiere que tal vez he ido por esta solución de la manera incorrecta y hay una manera mucho mejor para mí de hacer una búsqueda de amplitud en Java. Sé que mi solución funciona (eventualmente), ya que cuando uso un estado de inicio que no es muy diferente del objetivo, no lleva demasiado tiempo encontrar la ruta correcta. Sin embargo, me han dado un estado de inicio para usar, que desafortunadamente no se acerca al goalstate.

¡Cualquier sugerencia o sugerencia sería muy apreciada!

Answer 1

A primera vista, parecería que puedes terminar con estados duplicados y, por lo tanto, ciclos en tu gráfico. Puede que tenga que buscar de alguna manera para identificar si dos estados son iguales y si ya ha visitado uno anteriormente.

EDITAR: dejando a un lado las restricciones algorítmicas, tal vez haya una fórmula para mover el bloque X en la posición Y a la posición Z sin distribuir ninguna otra tesela. Dado esto, puedes calcular todas las transformaciones requeridas. Solo estoy reflexionando sobre el problema ahora.

Answer 2

Bueno, lo siguiente es que, si tuviera que hacer su lista de visitas, usaría un conjunto (probablemente un TreeSet ) que ordenaría automáticamente los estados para que la búsqueda para ver si un nuevo estado se haya visitado antes sea mucho más rápido.

Todo lo que necesitas hacer es hacer que tu clase de estado implemente la interfaz Comparable . (Espero que ya hayas esperado algo así y lo hayas convertido en clase). Si aún no lo sabe, utilizando el método compareTo de esta interfaz, defina el orden de clasificación de los objetos, que por supuesto sería utilizado por el conjunto visitado. Desde allí, puede configurar el método compareTo para que funcione como una comparación de cadenas, excepto con sus teselas.

Entonces, para dejarlo en claro, si a cada tesela se le asignara una letra, y las teselas en cada estado se enumeraran, podríamos tener esto:

State 1: ABCDEFGHIJKLMNOP
State 2: BCADEFGHIJKLMNOP

Naturalmente, el estado 1 sería lo primero en el orden. Así que simplemente extrapola ese mecanismo compareTo para trabajar con tiles en tiles (estoy seguro de que tus tiles tienen IDs o índices o algo así, ¿no?) Y tendrás una lista visitada ordenada. Luego, cuando llame a visited.Contains (estado), el programa podrá calcular muy rápidamente si se ha visitado o no un estado.

Answer 3

Creo que la idea de este ejercicio es que te des cuenta de que una búsqueda en profundidad es un mejor enfoque para este rompecabezas en particular.

Answer 4

En primer lugar, definitivamente usaría un objeto Queue real en lugar de un ArrayList. Aquí está la página de la API de Java en la interfaz de Queue: http://java.sun.com/j2se/1.5.0/docs/api/java/util/Queue.html - puede ver en esa página que hay muchos implementadores de Cola, si no sabes qué elegir, una lista LinkedList simple funcionará. ArrayList tendrá un gran éxito de rendimiento porque solo se elimina rápidamente del final, si lo elimina de cualquier otro lugar en el conjunto, tiene que cambiar TODO en uno (¡ LENTO !). Estarías poniendo en cola al final y dequerando al principio, ¡por lo tanto, LENTO !

Ahora no mencionaste explícitamente que estás eliminando elementos (eliminándolos) después de que terminaste con ellos, así que supongo que lo estás, porque esa sería una de las razones.

¿Tiene que usar específicamente la búsqueda de amplitud? Si calculé bien, ¡hay 25! (factorial) combinaciones, así que eso es 15511210043330985984000000 combinaciones, lo que teóricamente significa que si estás haciendo una búsqueda de amplitud, tu algoritmo probablemente nunca terminará. ¿La búsqueda en profundidad no está permitida? Si debe utilizar la búsqueda de amplitud, la única forma de hacerlo más rápido sería eliminar los estados que posiblemente no podrían conducir a una solución óptima. No estoy seguro de cómo lo harías.

Answer 5

He hecho la ''búsqueda brutal'' - el problema es que con una cuadrícula de 5x5 hay tantas combinaciones que solo lleva una eternidad. Lo dejé funcionando mientras iba a trabajar ... 8 horas después, todavía estaba funcionando, el tamaño de la lista de arrays de cola era de hasta 100k estados diferentes y mi PC sonaba como si se sobrecalentara y explotara lol

Sé que mi código funciona (eventualmente, como dije), así que me gustaría presentarlo. Solo me preocupa el tiempo que lleva encontrar una solución y me pregunto si hay un mejor enfoque que podría tomar, que no sea el uso de una lista de arrays para crear una cola.

Answer 6

La búsqueda en primer lugar sin verificación duplicada definitivamente le dará resultados como los que está viendo. De hecho, es bastante trivial probar que el algoritmo tal como lo ha implementado nunca terminará. No dude en esperarlo ... :-)

Lo que necesita es una estructura de datos auxiliares (preferiblemente un Set ) para almacenar posiciones previamente examinadas. Por lo tanto, parte de tu código se verá así:

public Queue<Position> queue = new LinkedList<Position>();
public Set<Position> done = new HashSet<Position>();

public Position[] findPath(Position start, Position goal) {
    if (done.contains(start)) return null;

    done.add(start);
    // add subsequent states to `queue`
    ...
}

Como se menciona en otras respuestas, la búsqueda de profundidad primero es una solución mucho mejor en este caso. Asumiendo que la posición de la goal es alcanzable, debería generar tiempos de búsqueda exponencialmente superiores para todas las posiciones excepto las más artificiales.

Answer 7

La forma en que lo estoy haciendo en este momento es la siguiente:

• 2 listas de Array; Cola y visitado
• El estado de inicio se agrega automáticamente a la lista de arrays visitada
• Se obtienen todos los movimientos legales posibles desde el inicio y cada uno se compara con los almacenados en el arraylist visitado.
• Esos movimientos legales que no crean un estado "visitado" se agregan a la cola.
• Se toma el estado mantenido en el índice 0 de la lista de arrays, y el proceso se repite.

Veo en las respuestas anteriores que probablemente debería cambiar las listas de arreglos en una colección diferente. Pero estoy comprobando que los estados no estén duplicados.

Answer 8

No dijiste si lo verificaste o no, pero parece que no estás recortando ciclos.

Primero, suponga que en lugar de representar movimientos como mover el cuadrado en blanco en alguna dirección, en su lugar proporcionó el número de mosaico que se movió. (Se garantiza que será único.) Ahora suponga que un movimiento legal es "3" - moviendo el mosaico # 3 al espacio vacío. El resultado es un nuevo diseño de tablero. Un movimiento legal desde allí es mover nuevamente el mosaico 3, y ahora estás de vuelta donde comenzaste.

Los acertijos deslizantes pueden tener ciclos más largos fácilmente. Si hay una cuadrícula 2x2 con 1-2-3-vacío en ella, entonces una secuencia válida de movimientos es 1-2-3-1-2-3-1-2-3-1-2-3 - que te envía De regreso al principio.

Si su búsqueda no verifica y poda tableros duplicados, la búsqueda de amplitud seguirá finalizando (siempre que no haya errores, y no haya un error de paridad (?) Que haga que su placa sea insoluble) - existe una solución correcta que es N movimientos de longitud, y se tomará un tiempo finito para procesar cada secuencia de movimientos K, de modo que eventualmente llegue a N, y a su solución. Sin embargo, el tiempo para cada longitud de movimiento aumenta exponencialmente (hasta 4 movimientos de cada tablero). Probablemente estás golpeando la memoria.

Desafortunadamente, el enfoque de la fuerza bruta para verificar el estado de la placa duplicada es almacenar cada placa a medida que la alcanza, lo que también consumirá la memoria rápidamente, aunque tal vez no tan rápido como su método actual. De hecho, podría ser satisfactorio para un simple tablero de 5x5.

Answer 9

Si bien es probable que no esté dentro del alcance de su tarea, hay un algoritmo para resolver este tipo de rompecabezas. Básicamente, hay dos movimientos que funcionan para cada línea, excepto los dos últimos, y dos movimientos que funcionan para las dos últimas líneas. El uso de este enfoque le brinda una solución mucho más rápida.

Desafortunadamente, como se trata de una tarea, sin duda se espera que hagas una búsqueda de fuerza bruta.

Answer 10

Tal vez una búsqueda de profundidad primero dirigida a un objetivo. Comience por resolver 9 fichas de borde, reduciendo el rompecabezas a una cuadrícula de 4x4. A continuación, resuelve las 7 fichas de borde de eso, reduciendo a una cuadrícula de 3x3 que debería ser una elección fácil para tu algoritmo original.

Answer 11

Tengo que escribir el código para ambos. Así que estoy a punto de pasar a la primera búsqueda de profundidad. Antes de hacerlo, solo quería asegurarme de que no me reirían de mi curso por producir un código que duró una eternidad y un día en encontrar una solución !!!!!!!