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

Решим эмпирически. В качестве языка использую 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.

Оцените пользу ответа
Мозг Отвечающий

Остались вопросы?

Задать вопрос