python - font - Búsqueda de la amplitud funcional
subplot title python (4)
Está bastante bien tener un estado mutable oculto dentro de la función. Si no es visible, entonces no existe. Usualmente uso conjuntos de hash para esto. Pero en general, debe atenerse a esto si su perfil lo identificó. De lo contrario, solo usa la estructura de datos establecida. OCaml tiene un excelente conjunto basado en árboles AVL muy equilibrados.
La primera búsqueda de profundidad funcional es encantadora en los gráficos acíclicos dirigidos.
Sin embargo, en los gráficos con ciclos, ¿cómo evitamos la recursión infinita? En un lenguaje de procedimiento marcaría nodos cuando los golpeara, pero digamos que no puedo hacer eso.
Una lista de nodos visitados es posible, pero será lenta porque usar uno resultará en una búsqueda lineal de esa lista antes de recurrir. Obviamente, una mejor estructura de datos que una lista aquí ayudaría, pero ese no es el objetivo del juego, porque estoy programando en ML: las listas son rey, y cualquier otra cosa que tenga que escribir yo mismo.
¿Hay una manera inteligente de solucionar este problema? ¿O tendré que conformarme con una lista visitada o, Dios no lo quiera, con un estado mutable?
Tienes que hacer un seguimiento de los nodos que visitas. Las listas no son reyes en la familia ML, son solo uno de los oligarcas. Solo debe usar un conjunto (basado en árbol) para rastrear los nodos visitados. Esto agregará un factor de registro en comparación con la mutación del estado del nodo, pero es mucho más limpio que no es divertido. Si sabe más acerca de sus nodos, posiblemente pueda eliminar el factor de registro utilizando un conjunto que no esté basado en un árbol (por ejemplo, un vector de bits).
Una opción es usar gráficos inductivos , que son una forma funcional de representar y trabajar con estructuras de gráficos arbitrarias. Los proporciona la biblioteca fgl de Haskell y se describen en "Gráficos inductivos y algoritmos de gráficos funcionales" de Martin Erwig.
Para una introducción más suave (¡con ilustraciones!), Vea la publicación de mi blog Generar laberintos con gráficos inductivos .
El truco con los gráficos inductivos es que te permiten hacer un patrón de coincidencia en los gráficos . El lenguaje funcional común para trabajar con listas es descomponerlas en un elemento de cabecera y el resto de la lista, y luego replantearse sobre eso:
map f [] = []
map f (x:xs) = f x : map f xs
Los gráficos inductivos te permiten hacer lo mismo, pero para los gráficos. Puede descomponer un gráfico inductivo en un nodo, sus bordes y el resto del gráfico.
Aquí coincidimos en el nodo 1 y en todos sus bordes (resaltados en azul), separados del resto del gráfico.
Esto nos permite escribir un map para gráficos (en pseudocódigo de Haskellish que se puede realizar con sinónimos de patrón):
gmap f Empty = Empty
gmap f ((in, node, out) :& rest) = f (in, node, out) :& gmap f rest
El principal inconveniente de este enfoque, a diferencia de las listas, es que los gráficos no tienen una forma natural única de descomponerse: el mismo gráfico se puede construir de múltiples maneras. El código del mapa anterior visitaría todos los vértices, pero en un orden arbitrario (dependiente de la implementación).
Para superar esto, agregamos otra construcción: una función de match que toma un nodo específico. Si ese nodo está en nuestro gráfico, obtendremos una coincidencia exitosa como la de arriba; Si no es así, todo el partido falla.
¡Esta construcción es suficiente para escribir un DFS o un BFS, con un código elegante que parece casi idéntico para ambos!
En lugar de marcar manualmente los nodos como visitados, simplemente repasamos el resto del gráfico, excepto el nodo que estamos viendo ahora: en cada paso, estamos trabajando con una porción cada vez más pequeña del gráfico original. Si intentamos acceder a un nodo que ya hemos visto con match , no estará en el gráfico restante y esa rama fallará. Esto permite que nuestro código de procesamiento de gráficos se vea como nuestras funciones recursivas normales sobre las listas.
Aquí hay un DFS para este tipo de gráfico. Mantiene la pila de nodos para visitar como una lista (la frontera) y toma la frontera inicial para comenzar. La salida es una lista de nodos atravesados en orden. (El código exacto aquí no se puede escribir con la biblioteca directamente sin algunos sinónimos de patrones personalizados).
dfs _frontier Empty = []
dfs [] _graph = []
dfs (n:ns) (match n -> Just (ctx, rest)) = -- not visited n
dfs (neighbors'' ctx ++ ns) rest
dfs (n:ns) graph = -- visited n
dfs ns graph
Una función recursiva bastante simple. Para convertirlo en una primera búsqueda, todo lo que tenemos que hacer es reemplazar nuestra frontera de pila con una cola: en lugar de poner a los vecinos al frente de la lista, los ponemos en la parte posterior :
bfs _frontier Empty = []
bfs [] _graph = []
bfs (n:ns) (match n -> Just (ctx, rest)) = -- not visited n
bfs (ns ++ neighbors'' ctx) rest
bfs (n:ns) graph = -- visited n
bfs ns graph
Sí, eso es todo lo que necesitamos! No tenemos que hacer nada especial para realizar un seguimiento de los nodos que visitamos a medida que retrocedemos en el gráfico, al igual que no tenemos que realizar un seguimiento de las celdas de la lista que hemos visitado: cada vez que realizamos la investigación, Solo obtenemos la parte del gráfico que no hemos visto.
Vea el ejemplo de implementación de BFS , con explicación en Martin Erwig: Gráficos inductivos y algoritmos de gráficos funcionales . Además, la implementación de DFS , basada en David King, John Launchbury: estructuración de algoritmos de búsqueda en profundidad en Haskell
(Sugerencia para la policía de SO: sí, esto parece una respuesta de solo enlace, pero así es como funciona la ciencia: hay que leer los documentos, ya que volver a escribir sus resúmenes no es muy útil).