Çalışmalarım için iki ülke arasında en kısa rotayı alan aşağıdaki fonksiyonu yazmam gerekiyor. Zaten zaten iki ülke arasında bir bağlantı olup olmadığını kontrol eden bir işlev ve iki ülke arasında bir bağlantı döndüren bir işlev verimiRoute olan bir işlev yazmıştım. Şimdi iki ülke arasındaki en kısa rotayı döndüren bir işlevi kodlamam gerekiyor.Haskell'de Dijkstra Algoritması Nasıl Uygulanır
İlk yaklaşımım, iki ülke arasındaki tüm bağlantıları almak ve en kısa olanı elde etmekti, ancak tüm bağlantıları almak benim görüşüme göre programlamak için can sıkıcıydı. Şimdi bir dijstra algoritması uygulama fikrini buluyorum, ama aslında bunu da çok zor buluyorum. Bana bunun nasıl yapılacağı konusunda biraz fikir verebilir misiniz? Biz bu tür kullanmak zorunda
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)
olan My verim rota fonksiyonu sadece ilk arama breadth (biz onları değiştirmek için izin ancak yeni türleri eklemek için izin verilen ofc değildir.): (Sry
yieldFastestRoute :: Connections -> Country -> Country -> Itinerary
Dijkst:
-- 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
Bu bir) Alman yorumlar için şimdi yazmak zorunda ra Algoritma: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Benim ilk yaklaşım şuydu: Ben temelde iyi yolu Haskell Dijkstra uygulamak neyin bilmek istiyorum
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
durumunda veya (I getallRoutes ile ilgili sorunlar vardı söylediği gibi) Takip edebileceğim başka bir yaklaşım var.
1. Dijkstra algoritması nedir? 2. Bunu uygulamadaki girişimlerinizi gösterin. 3. Uygulamanızın hangi parçasını zor bulduğunuzu netleştirin. – dave4420
Haskell içinde dijstra uygulamak için aşırı zor bir yol yoksa ya da sorunu çözmek için bazı daha kolay onaylar varsa istiyorum: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm –
Bence bu soru Uygun grafik veri yapılarının nasıl oluşturulacağını sormaya odaklanırsanız daha iyi yanıtlanabilir olun. Bundan sonra, Dijkstra'yı uygulamak zor olmamalı. Ayrıca bir ton kodunuz var ve bu yutmak biraz zor, özellikle Alman yorumlarla birlikte – hugomg