1

Недавно начал изучать Haskell, и дошёл до алгоритмов на графах. Идут очень тяжело. Нашёл алгоритм Дейкстры, но не могу разобраться, что происходит в коде. А именно, не понятно, что передаётся в метод relax:

retMinNode (relax [(x,y,z) | (x,y,z) <- [(s,d,e) | (s,d,e)<-adjList, (belongsTo source visited)], not (belongsTo y visited)] visited)

А также, что происходит в методу retMinNode. Исходный код алгоритма:

inf = 100000


dijkstra  ::Int->Int->[(Int,Int,Int)]->[(Int,Int)]->[(Int,Int)]
dijkstra  s d adjList visited
    | (p,q) == (inf, inf) = visited
    | otherwise  = dijkstra p d adjList ((p,q):visited)
    where (p,q) = exploreNeighbours s visited adjList

exploreNeighbours ::Int->[(Int,Int)]->[(Int,Int,Int)]->(Int,Int)
exploreNeighbours source visited adjList = 
    retMinNode (relax [(x,y,z) | (x,y,z) <- [(s,d,e) | (s,d,e)<-adjList, 
    (belongsTo source visited)], not (belongsTo y visited)] visited)

belongsTo::Int->[(Int,Int)]->Bool
belongsTo _ [] = False
belongsTo s ((x,_):xs)
    | (x==s) = True
    | otherwise = belongsTo s xs

relax :: [(Int,Int,Int)]->[(Int,Int)]->[(Int,Int)]
relax [] visited = []
relax ((x,y,z):ns) visited = (y, (currDist x) + z):relax ns visited
    where currDist n = foldl(\acc t -> if (fst t == n) then (snd t) else 
acc) inf visited 

retMinNode ::[(Int,Int)]->(Int,Int)
retMinNode [] = (inf,inf)
retMinNode arr = foldl (\acc t -> if ((snd t) < (snd acc)) then t else acc) 
  (inf,inf) arr

1 ответ 1

2

retMinNode принимает список пар и возвращает пару с минимальным вторым элементом.

Теакрь разберемся с

exploreNeighbours ::Int->[(Int,Int)]->[(Int,Int,Int)]->(Int,Int)
exploreNeighbours source visited adjList = 
    retMinNode (relax [(x,y,z) | (x,y,z) <- [(s,d,e) | (s,d,e)<-adjList, (belongsTo source visited)], not (belongsTo y visited)] visited)

для начала перепишем разделив сложное выражение на части.

exploreNeighbours ::Int->[(Int,Int)]->[(Int,Int,Int)]->(Int,Int)
exploreNeighbours source visited adjList = 
    retMinNode c
    where
        a = [(x,y,z) | (x,y,z) <- b, not (belongsTo y visited)] 
        b = [(s,d,e) | (s,d,e) <- adjList, (belongsTo source visited)]
        c = relax a visited

Выражения вида [a | b <- c, d] называются list comprehension.

  • c исходный лист.
  • b переменная принимающая значения из исходного списка
  • d фильтр
  • a выражение результат.

Таким образом b это просто странный способ вернуть adjList если верно belongsTo source visited и пустой список в противном случае.

Теперь разберемся с a. Это список который является результатом фильтрации предыдущего.

Дальше все вроде просто.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.