Question

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых ( в километрах ) приведена в таблице.
Определите длину кратчайшего пути между пунктами A и F. Передвигаться можно только по дорогам, указанным в таблице.

Answer 1

Решим эмпирически. В качестве языка использую Haskell.

Таблица описывается функцией ways.

• type Way = ([Char], Int)
• ways :: [(Char, [(Char, Maybe Int)])]
• ways =  f $ fltr . f <$>
•                [[Nothing, Just 3, Just 4, Nothing, Nothing, Just 18],
•                [Just 3, Nothing, Just 3, Nothing, Nothing, Nothing],
•                [Just 4, Just 3, Nothing, Just 4, Nothing, Nothing],
•                [Nothing, Nothing, Just 4, Nothing, Just 2, Just 6],
•                [Nothing, Nothing, Nothing, Just 2, Nothing, Just 1],
•                [Just 18, Nothing, Nothing, Just 6, Just 1, Nothing]]
•  where
•    f = zip "ABCDEF"
•    fltr = filter $ isJust . snd
• fromA :: Char -> [(Char, Maybe Int)]
• fromA a = join [x | (c, x) <- ways, c == a]
• findWays :: Char -> Char -> [Way]
• findWays a b = findWays' a b ("", 0)
• findWays' :: Char -> Char -> Way -> [Way]
• findWays' a b (w, c)
•  | a == b = [(w ++ [a], c)]
•  | otherwise = [(w', c'') | (a', Just c') <- fromA a, a' `notElem` w, (w', c'') <- findWays' a' b (w ++ [a], c + c')]
• findMin :: Ord a => [(a, b)] -> (a, b)
• findMin xs  | length xs == 1 = head xs
•            | fst x < fst y = findMin $ x : drop 2 xs
•            | otherwise  = findMin $ y : drop 2 xs
•            where
•              x = head xs
•              y = xs !! 1
• main :: Char -> Char -> (String, Int)
• main a b = findMin $ findWays a b

Вызов main 'A' 'F' выдаст длину кратчайшего пути.

Ответ: Кратчайший путь A-C-D-E-F. Его длина – 11.