На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можнодвигаться только в одном направлении, указанном стрелкой. Как узнать сколько существует различных путейиз пункта А в пункт Л?

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

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

• ways = f <$>
• [('A', "BCD"), -- А
• ('B', "DJ"), -- Б
• ('C', "DHI"), -- В
• ('D', "FH"), -- Г
• ('E', "FK"), -- Д
• ('F', "HIK"), -- Е
• ('J', "EK"), -- Ж
• ('H', "I"), -- И
• ('I', "K"), -- К
• ('K', "")] -- Л
• where
• f = second (fmap (, Just 1))

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

• 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')]

В findWays передаются начальная и конечная точки маршрута, для начальной точки ищутся все возможные пути, затем для каждого из таких путей мы ищем новые пути и так далее до тех пор, пока начальная и конечные точки в вызове функции не будут совпадать.

Результат вызова для findWays 'A' 'K':

[("ABDFHIK",6),("ABDFIK",5),("ABDFK",4),("ABDHIK",5),("ABJEFHIK",7),("ABJEFIK",6),("ABJEFK",5),("ABJEK",4),("ABJK",3),("ACDFHIK",6),("ACDFIK",5),("ACDFK",4),("ACDHIK",5),("ACHIK",4),("ACIK",3),("ADFHIK",5),("ADFIK",4),("ADFK",3),("ADHIK",4)]

Это все пути, ведущие из города 'A' в город 'K' (для простоты названия городов были заменены на английские, правило замены приведено выше)

Чтобы найти количество, а не сами маршруты достаточно выполнить length $ findWays 'A' 'K': 19.

: 19 путей существует из города A в город Л.