Biblioteka do pracy z (potencjalnie nieskończonych) wykresów zdefiniowanych przez sąsiada liście funkcjonuje

Question

Oto wzór Używałem wiele razy w wielu różnych językach programowania:

1. napotkasz problem, który może być łatwo zredukowana do niektórych algorytm wykresu.
2. Zdefiniuj funkcję przylegania: outEdges :: MyNode -> [MyNode].
3. Kodowanie pewnej ogólnej postaci wspomnianego algorytmu wykresu, który przyjmuje tę funkcję jako pierwszy argument.

Jako przykład tę (celowo nieefektywny) sposób obliczania edycji odległość pomiędzy dwoma słowami. Będziemy policzyć najmniejszą liczbę wstawień i usunięć koniecznych do przekształcenia jednego słowa na drugie poprzez pierwsze wyszukiwanie wszerz.

import Data.List 
import Data.Maybe 

alphabet :: String 
alphabet = ['a'..'z'] 

wordNeighbors :: String -> [String] 
wordNeighbors word = deletions ++ insertions where 
    insertions = [pre++[c]++suf | (pre,suf) <- splits, c <- alphabet] 
    deletions = [pre++suf  | (pre,_:suf) <- take (length word) splits] 

    splits = zip (inits word) (tails word) 

shortestDistance :: (Eq a,Hashable a)=> (a -> [a]) -> a -> a -> Maybe Int 
shortestDistance edgeFunc source target = 
    -- 8 lines of code where I do a breadth-first traversal, 
    -- using a HashSet to track previously visited nodes; 
    -- yawn... 

editDistance :: String -> String -> Int 
editDistance a b = fromJust $ shortestDistance wordNeighbors a b 

main = print $ editDistance "cat" "can" -- prints 2 

Problem polega na tym, Dostaję strasznie zmęczony kroku 3. (patrz wyżej shortestDistance ...)

czuję jak pisałem tych samych algorytmów setki razy. Bardzo bym chciał, gdybym mógł po prostu w jakiś sposób wykorzystać FGL lub Data.Graph i zrobić z tym, ale o ile mogę powiedzieć, że oba ostatecznie wymagają budowy jakiejś struktury danych, która jest ścisła w stosunku do zestaw wszystkich węzłów. Jest to problem, ponieważ w wielu problemach, wykres jest nieskończony (jak w powyższym przykładzie).

Pytam konkretnie o Haskella, ponieważ Haskell tak mocno koncentruje się na kombinatorach, że jakoś oczekiwałem, że wiele z tych algorytmów już gdzieś istnieje.

---

Uzupełnienie: Oto inne przykłady funkcji I często pisać oprócz najkrótszej ścieżki:

-- Useful for organizing the computation of a recursively-defined 
-- property of the nodes in an acyclic graph, such as nimbers. 
dfsPostOrder :: (v -> [v]) -> v -> [v] 
dfsPostOrder adjFunc root = ... 

-- Find all nodes connected in some manner to the root node. 
-- In case I know the components are finite size, but am not sure 
-- of a nice way to express their contents. 
-- (Note: The API below is only good for undirected graphs) 
getComponent :: (v -> [v]) -> v -> Set v 
getComponent adjFunc root = ... 

-- Lazily organize the graph into groups by their minimum distance 
-- to any of the nodes in @roots@. 
-- One could use this to help incrementalize parts of e.g. a Game 
-- of Life or Kinetic Monte Carlo simulation by locating regions 
-- invalidated by changes in the state. 
groupsByProximity :: (v -> [v]) -> Set v -> [Set v] 
groupsByProximity adjFunc roots = ... 

---

TL; DR: Czy istnieje jakiś ogólny sposób pisania algorytmów pracować na potencjalnie nieskończonych, potencjalnie cyklicznych, skierowanych wykresach --- takich jak te zdefiniowane przez funkcję przylegania (Node -> [Node] lub Node -> [(Node, Weight)])?

Answer 1

Myślę, że większość algorytmów wyszukiwania "od pierwszego do końca" jest naprawdę w pewnym rodzaju "best-first" algorithm. Oznacza to, że granica wyszukiwania znajduje się w kolejce priorytetowej , która określa kolejność, w jakiej odwiedzane są węzły.

znalazłem dwa pakiety, które realizują ogólnie najlepiej Pierwsze algorytmy:

• astar
• monad-dijkstra

Oba moduły mają interfejsy bardzo ogólnych - tj podać sąsiada funkcji funkcja odległości międzywęzła i (w przypadku gwiazdy A) funkcja heurystyczna .

Przy odpowiednim doborze funkcji heurystycznych i dystansowych można przeszukać swoje wyszukiwanie na jeden z tych algorytmów. Na przykład: this patent opisuje sposób użycia gwiazdki A- w celu rozwiązania problemu odległości edycji.