Đối với các nghiên cứu của tôi, tôi phải viết hàm sau đây là tuyến đường ngắn nhất giữa hai quốc gia. Tôi đã viết một hàm làRoute kiểm tra nếu có kết nối giữa hai quốc gia và hàm yieldRoute chỉ trả về kết nối giữa hai quốc gia. Bây giờ tôi phải mã một hàm trả về tuyến đường ngắn nhất giữa hai quốc gia.Cách thực hiện Thuật toán Dijkstra trong Haskell
Cách tiếp cận đầu tiên của tôi là nhận tất cả các kết nối giữa hai quốc gia và sau đó nhận được kết nối ngắn nhất, nhưng nhận được mọi kết nối đều gây phiền toái cho lập trình theo ý kiến của tôi. Bây giờ tôi đưa ra ý tưởng để thực hiện một thuật toán dijstra, nhưng tôi thực sự tìm thấy điều này kinda khó quá. Các bạn có thể cho tôi một số ý tưởng làm thế nào để làm điều này?
Chúng ta phải sử dụng các loại
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)
My chức năng tuyến đường năng suất mà chỉ đơn giản là theo chiều rộng tìm kiếm đầu tiên (chúng tôi không được phép thay đổi chúng nhưng OFC chúng ta được phép thêm các loại mới.): (Sry cho ý kiến Đức)
-- 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
Cái này tôi phải viết bây giờ:
yieldFastestRoute :: Connections -> Country -> Country -> Itinerary
Dijkst ra thuật toán: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
tiếp cận đầu tiên của tôi là thế này: (như tôi đã nói tôi có vấn đề với 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
tôi về cơ bản muốn biết whats cách tốt nhất để thực hiện Dijkstra trong Haskell, hoặc nếu có một cách tiếp cận khác mà tôi có thể làm theo.
1. Thuật toán Dijkstra là gì? 2. Cho chúng tôi thấy nỗ lực của bạn khi triển khai nó. 3. Làm rõ phần nào của việc thực hiện nó mà bạn đang gặp khó khăn. – dave4420
Tôi muốn nếu có một cách cực kỳ khó khăn để thực hiện dijstra trong haskell hoặc nếu có một số đơn giản hơn để giải quyết vấn đề: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm –
Tôi nghĩ câu hỏi này sẽ phải trả lời tốt hơn nếu bạn tập trung vào việc hỏi cách tạo cấu trúc dữ liệu đồ thị thích hợp. sau đó, việc triển khai Dijkstra không khó. Ngoài ra bạn có một tấn mã và đó là một chút khó nuốt, đặc biệt với các ý kiến Đức – hugomg