16

对于我的学习，我必须编写以下函数，它可以获取两国之间最短的路线。我已经编写了一个函数 isRoute 来检查两个国家之间是否存在连接，以及一个函数 yieldRoute 只返回两个国家之间的连接。现在我必须编写一个函数来返回两国之间的最短路线。

我的第一种方法是获取两国之间的所有连接，然后获取最短的一个，但在我看来，获取所有连接对编程来说有点烦人。现在我想出了实现 dijstra 算法的想法，但我实际上也觉得这有点难。你们能给我一些想法如何做到这一点吗？

我们必须使用这些类型（我们不允许更改它们，但我们可以添加新类型。）

type Country = String
type Countries = [Country]
type TravelTime = Integer -- Travel time in minutes
data Connection = Air Country Country TravelTime
    | Sea Country Country TravelTime
    | Rail Country Country TravelTime
    | Road Country Country TravelTime deriving (Eq,Ord,Show)
type Connections = [Connection]
data Itinerary = NoRoute | Route (Connections,TravelTime) deriving (Eq,Ord,Show)

我的收益路线功能，它只是广度优先搜索：（德语评论很抱歉）

-- Liefert eine Route falls es eine gibt
yieldRoute :: Connections -> Country -> Country -> Connections
yieldRoute cons start goal 
            | isRoute cons start goal == False = []
            | otherwise                        = getRoute cons start [] [start] goal

getRoute :: Connections -> Country -> Connections -> Countries -> Country -> Connections
getRoute cons c gone visited target
            | (c == target) = gone 
            | otherwise  = if ( visit cons c visited ) then ( getRoute cons (deeper cons c visited) (gone ++ get_conn cons c (deeper cons c visited)) (visited ++ [(deeper cons c visited)]) target ) else ( getRoute cons (back (drop (length gone -1) gone)) (take (length gone -1) gone) visited target )

-- Geht ein Land zurück
back :: Connections -> Country
back ((Air c1 c2 _):xs) = c1
back ((Sea c1 c2 _):xs) = c1
back ((Rail c1 c2 _):xs) = c1
back ((Road c1 c2 _):xs) = c1

-- Liefert das nächste erreichbare Country
deeper :: Connections -> Country -> Countries -> Country
deeper ((Air c1 c2 _):xs) c visited
            | (c1 == c) = if ( c2 `elem` visited ) then ( deeper xs c visited ) else c2
            | (c2 == c) = if ( c1 `elem` visited ) then ( deeper xs c visited ) else c1
            | otherwise = deeper xs c visited
deeper ((Sea c1 c2 _):xs) c visited
            | (c1 == c) = if ( c2 `elem` visited ) then ( deeper xs c visited ) else c2
            | (c2 == c) = if ( c1 `elem` visited ) then ( deeper xs c visited ) else c1
            | otherwise = deeper xs c visited
deeper ((Rail c1 c2 _):xs) c visited
            | (c1 == c) = if ( c2 `elem` visited ) then ( deeper xs c visited ) else c2
            | (c2 == c) = if ( c1 `elem` visited ) then ( deeper xs c visited ) else c1
            | otherwise = deeper xs c visited
deeper ((Road c1 c2 _):xs) c visited
            | (c1 == c) = if ( c2 `elem` visited ) then ( deeper xs c visited ) else c2
            | (c2 == c) = if ( c1 `elem` visited ) then ( deeper xs c visited ) else c1
            | otherwise = deeper xs c visited

-- Liefert eine Connection zwischen zwei Countries
get_conn :: Connections -> Country -> Country -> Connections
get_conn [] _ _ = error "Something went terribly wrong"
get_conn ((Air c1 c2 t):xs) c3 c4 
            | (c1 == c3) && (c2 == c4) = [(Air c1 c2 t)]
            | (c1 == c4) && (c2 == c3) = [(Air c1 c2 t)]
            | otherwise                = get_conn xs c3 c4
get_conn ((Sea c1 c2 t):xs) c3 c4 
            | (c1 == c3) && (c2 == c4) = [(Air c1 c2 t)]
            | (c1 == c4) && (c2 == c3) = [(Air c1 c2 t)]
            | otherwise                = get_conn xs c3 c4
get_conn ((Road c1 c2 t):xs) c3 c4 
            | (c1 == c3) && (c2 == c4) = [(Air c1 c2 t)]
            | (c1 == c4) && (c2 == c3) = [(Air c1 c2 t)]
            | otherwise                = get_conn xs c3 c4
get_conn ((Rail c1 c2 t):xs) c3 c4 
            | (c1 == c3) && (c2 == c4) = [(Air c1 c2 t)]
            | (c1 == c4) && (c2 == c3) = [(Air c1 c2 t)]
            | otherwise                = get_conn xs c3 c4

-- Überprüft ob eine besuchbare Connection exestiert
visit :: Connections -> Country -> Countries -> Bool
visit [] _ _ = False
visit ((Air c1 c2 _):xs) c visited
                | (c1 == c) = if ( c2 `elem` visited) then ( visit xs c visited ) else True
                | (c2 == c) = if ( c1 `elem` visited) then ( visit xs c visited ) else True
                | otherwise = visit xs c visited
visit ((Sea c1 c2 _):xs) c visited
                | (c1 == c) = if ( c2 `elem` visited) then ( visit xs c visited ) else True
                | (c2 == c) = if ( c1 `elem` visited) then ( visit xs c visited ) else True
                | otherwise = visit xs c visited
visit ((Rail c1 c2 _):xs) c visited
                | (c1 == c) = if ( c2 `elem` visited) then ( visit xs c visited ) else True
                | (c2 == c) = if ( c1 `elem` visited) then ( visit xs c visited ) else True
                | otherwise = visit xs c visited
visit ((Road c1 c2 _):xs) c visited
                | (c1 == c) = if ( c2 `elem` visited) then ( visit xs c visited ) else True
                | (c2 == c) = if ( c1 `elem` visited) then ( visit xs c visited ) else True

我现在必须写这个：

yieldFastestRoute :: Connections -> Country -> Country -> Itinerary

Dijkstra 算法： http ://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

我的第一种方法是：（正如我所说的 getallRoutes 有问题）

yieldFastestRoute :: Connections -> Country -> Country -> Itinerary
yieldFastestRoute cons start targ
            |(isRoute start targ == False) = NoRoute
            |otherwise                    = (Route (getFastest (getAllRoutes cons start targ)) (sumTT (getFastest (getAllRoutes cons start targ))))

-- Liefert alle Routen zwischen zwei Ländern
getAllRoutes :: Connections -> Country -> Country -> [Connections]

-- Liefert aus einer Reihe von Connections die schnellste zurück
getFastest :: [Connections] -> Connections
getFastest (x:xs) = if ( (sumTT x) < sumTT (getFastest xs) || null (getFastest xs) ) then x else ( getFastest xs )

sumTT :: Connections -> TravelTime
sumTT []                  = 0
sumTT ((Air _ _ t ): xs)  = t ++ sumTT xs
sumTT ((Rail _ _ t ): xs) = t ++ sumTT xs
sumTT ((Road _ _ t ): xs) = t ++ sumTT xs
sumTT ((Sea _ _ t ): xs)  = t ++ sumTT xs

我基本上想知道在 Haskell 中实现 Dijkstra 的最佳方法是什么，或者我是否可以遵循另一种方法。

4

2 回答 2

6

您似乎已经编写了算法的大部分内容

这是 Martin Erwig 在 Haskell 的一个项目，可能有助于给你一些想法

--  SP.hs -- Dijkstra's Shortest Path Algorithm  (c) 2000 by Martin Erwig
module SP (
   spTree,spLength,sp,      -- shortest paths
   dijkstra
) where

import qualified Heap as H
import Graph
import RootPath
expand :: Real b => b -> LPath b -> Context a b -> [H.Heap (LPath b)]
expand d p (_,_,_,s) = map (\(l,v)->H.unit ((v,l+d):p)) s
dijkstra :: Real b => H.Heap (LPath b) -> Graph a b -> LRTree b
dijkstra h g | H.isEmpty h || isEmpty g = []
dijkstra h g =
    case match v g of
         (Just c,g')  -> p:dijkstra (H.mergeAll (h':expand d p c)) g'
         (Nothing,g') -> dijkstra h' g'  
    where (p@((v,d):_),h') = H.splitMin h

spTree :: Real b => Node -> Graph a b -> LRTree b
spTree v = dijkstra (H.unit [(v,0)])
spLength :: Real b => Node -> Node -> Graph a b -> b
spLength s t = getDistance t . spTree s
sp :: Real b => Node -> Node -> Graph a b -> Path
sp s t = map fst . getLPath t . spTree s

其余模块在这里

于 2012-12-23T19:30:48.550 回答
3

编辑：以下实际上不是 Dijkstra。该算法称为 SPFA。

要实现该算法，您应该考虑所需的最少信息量，使用它来构建通用解决方案，然后将该解决方案应用于您的特定案例。

对于 Dijkstra，它关心的是：

  • 识别节点
  • 比较路径成本
  • 确定从节点到哪里。

我们可以这样编码

import qualified Data.Set as Set

dijkstra
    :: (Ord cost , Ord node)
    => ((cost , node) -> [(cost , node)]) -- ^ Where we can go from a node and the cost of that
    -> node                               -- ^ Where we want to get to
    -> (cost , node)                      -- ^ The start position
    -> Maybe (cost , node)                -- ^ Maybe the answer. Maybe it doesn't exist
dijkstra next target start = search mempty (Set.singleton start)
    where
        search visited toBeVisited = case Set.minView toBeVisited of
            Nothing -> Nothing
            Just ((cost , vertex) , withoutVertex)
                | vertex == target            -> Just (cost , vertex)
                | vertex `Set.member` visited -> search visited withoutVertex
                | otherwise                   -> search visitedWithNode withNext
                where
                    visitedWithNode = Set.insert vertex visited
                    withNext = foldr Set.insert withoutVertex $ next (cost , vertex)

现在您可以自由地表示您想要的图表，并将您的成本视为您想要的任何东西。

这是一个使用 Map 来表示小字符图的示例。

import Data.Maybe (fromMaybe)
import qualified Data.Map.Strict as Map

graph =
    Map.fromList
        [ ('a' , [(1 , 'b') , (5 , 'c')])
        , ('b' , [(2 , 'c')])
        , ('c' , [(1 , 'a') , (5 , 'b')])
        ]

-- Output:
-- Just (3,'c')
main = print $ dijkstra step 'c' (0 , 'a')
    where
        step :: (Int , Char) -> [(Int , Char)]
        step (cost , node) =
            [ (cost + edgeCost , child)
            | (edgeCost , child) <- fromMaybe [] $ Map.lookup node graph
            ]

如果您不仅想知道从 A 到 B 的成本，还想知道完整的路径，您可以将此信息与您的成本一起存储。

data Path a = Path {cost :: Int , trajectory :: [a]}
    deriving (Show)

instance Eq (Path a) where
    a == b = cost a == cost b

instance Ord (Path a) where
    compare a b = compare (cost a) (cost b)


-- Output:
--     Just (Path {cost = 3, trajectory = "cba"},'c')
tryItOutWithPath = dijkstra step 'c' (Path 0 ['a'] , 'a')
    where
        step :: (Path Char , Char) -> [(Path Char , Char)]
        step (Path cost traj , node) =
            [ (Path (cost + edgeCost) (child : traj) , child)
            | (edgeCost , child) <- fromMaybe [] $ Map.lookup node graph
            ]
于 2020-10-12T17:15:49.393 回答