java - recorrido - ejemplos de busqueda costo uniforme

La búsqueda en profundidad primero y la comprensión de la búsqueda en primer lugar

Question

Estoy haciendo Tetris como un proyecto paralelo divertido (no para la tarea) y me gustaría implementar la inteligencia artificial para que la computadora pueda jugar sola. La forma en que he escuchado hacerlo es usar BFS para buscar lugares disponibles, luego crear una puntuación agregada de la ubicación de colocación más sensible ...

Pero tengo problemas para entender los algoritmos BFS y DFS. La forma en que aprendo mejor es dibujarlo ... ¿mis dibujos son correctos?

¡Gracias!

Answer 1

El resultado final de tus recorridos es correcto, estás bastante cerca. Sin embargo, estás un poco alejado de los detalles.

En la primera búsqueda en profundidad, aparecerá un nodo, lo marcará como visitado y apilará a sus hijos no visitados. En ese orden. El orden puede parecer irrelevante para un árbol, pero si tuviera una gráfica con ciclos, podría caer en un bucle infinito, pero esta es otra discusión.

Dada la línea de base del algoritmo, después de empujar el nodo raíz en la pila, comenzará su primera iteración, inmediatamente haciendo estallar A. No permanecerá en la pila hasta el final del algoritmo. Tomará A, apilará D, C y B al mismo tiempo (o B, C y D, puede hacerlo de izquierda a derecha o de izquierda a derecha, es su elección) y marque A como visitado. En este momento, tu pila tiene D en la parte inferior, C en el medio y B en la parte superior.

El siguiente nodo emergente es B. Insertarás F y E en la pila (mantendré el orden igual que el tuyo), marcando B como visitado. La pila tiene, de arriba a abajo, EFC D. A continuación, se abre E, no se agregan nuevos nodos y E se marca como visitado. El bucle continuará, haciendo lo mismo con F, C y D. El orden final es ABEFC D.

Intentaré reescribir el algoritmo de manera similar al tuyo:

Push root into stack
Loop until stack is empty
    Pop node N on top of stack
    Mark N as visited
    For each children M of N
        If M has not been visited (M.visited() == false)
            Push M on top of stack

No entraré en detalles para la primera búsqueda, el algoritmo es exactamente el mismo. La diferencia está en la estructura de datos y en cómo se comporta. Una cola es FIFO (First In First Out) y, debido a eso, visitará todos los nodos en el mismo nivel antes de comenzar a visitar los nodos en los niveles inferiores.

Answer 2

En primer lugar, creo que sus recorridos parecen estar bien (de un resumen rápido). Te voy a dar algunos enlaces útiles a continuación.

He encontrado algunos videos decentes sobre youtube sobre esto antes, pero aquí hay uno (no es el mejor que he visto) que lo cubre en http://www.youtube.com/watch?v=eXaaYoTKBlE . Si lo haces por diversión, crea dos versiones, una con DFS y otra con BFS, y haz una prueba comparativa para observar la diferencia. También descargue el buscador de gráficos y cualquier otra herramienta que le resulte útil en http://www.aispace.org/downloads.shtml si desea rastrear algunas para una mejor comprensión. Y por último, pero no menos importante, una pregunta de en DFS y BFS http://www..com/questions/687731/