Ответьте пожалуйста!Между населенными пунктами А В С Д построены дороги,протяженность которых (в километрах)приведена в таблице.

Приложения:

Ответы

Ответ дал: MaxLevs

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

Опишем дороги следующим образом:

ways :: [(Char, [(Char, Maybe Int)])]
ways = f $ fltr . f <$>
[[Nothing, Just 2, Nothing, Nothing, Just 1],
[Just 2, Nothing, Just 5, Nothing, Just 4],
[Nothing, Just 5, Nothing, Just 3, Just 3],
[Nothing, Nothing, Just 3, Nothing, Just 4],
[Just 1, Just 4, Just 3, Just 4, Nothing]]
where
f = zip "ABCDE"
fltr = filter $ isJust . snd

Опишем функции fromA для получения всех возможных путей из заданной начальной точки, функцию findWays для поиска путей из пункта A в пункт B, а также функцию findMin для выбора минимального из путей:

fromA :: Char -> [(Char, Maybe Int)]
fromA a = join [x | (c, x) <- ways, c == a]
findWays :: Char -> Char -> [(String, Int)]
findWays a b = findWays' a b ("", 0)
findWays' :: Char -> Char -> (String, Int) -> [(String, Int)]
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