then (B,b):pathB
else (C,c):(A,a):pathA
in (newPathToA, newPathToB)
Как это работает? Для начала вычисляем оптимальное время по дороге A, основываясь на текущем лучшем маршруте; то же самое для B. Мы выполняем sum $ map snd pathA, так что если pathA – это что-то вроде [(A,100),(C,20)], timeA станет равным 120.
forwardTimeToA – это время, которое мы потратили бы, если бы ехали до следующего перекрёстка по A от предыдущего перекрёстка на A напрямую. Оно равно лучшему времени по дороге A плюс длительность по A текущей секции.
crossTimeToA – это время, которое мы потратили бы, если бы ехали до следующего перекрёстка на A по B, а затем повернули бы на A. Оно равно лучшему времени по B плюс длительность B в текущей секции плюс длительность секции C.
Таким же образом вычисляем forwardTimeToB и crossTimeToB. Теперь, когда мы знаем лучший путь до A и B, нам нужно создать новые пути до A и B с учетом этой информации. Если выгоднее ехать до A просто напрямую, мы устанавливаем newPathToA равным (A,a): pathA. Подставляем метку A и длину секции a к началу текущего оптимального пути. Мы полагаем, что лучший путь до следующего перекрёстка по A – это путь до предыдущего перекрёстка по A плюс ещё одна секция по A. Запомните, A – это просто метка, в то время как a имеет тип Int. Для чего мы подставляем их к началу, вместо того чтобы написать pathA ++ [(A,a)]? Добавление элемента к началу списка (также называемое A, двигаясь по B и поворачивая на A, то newPathToA будет старым путём до B плюс секция до перекрёстка по B и переезд на A. Далее мы делаем то же самое для newPathToB, но в зеркальном отражении.
Рано или поздно мы получим пару из newPathToA и newPathToB.
Запустим функцию на первой секции heathrowToLondon. Поскольку эта секция первая, лучшие пути по A и B будут пустыми списками.
ghci> roadStep ([], []) (head heathrowToLondon)
([(C,30),(B,10)],[(B,10)])
Помните, что пути записаны в обратном порядке, так что читайте их справа налево. Из результата видно, что лучший путь до следующего перекрёстка по A – это начать движение по B и затем переехать на A; ну а лучший путь до следующего перекрёстка по B – ехать прямо по B.
ПРИМЕЧАНИЕ. Подсказка для оптимизации: когда мы выполняем timeA = sum $ map snd pathA, мы заново вычисляем время пути на каждом шаге. Нам не пришлось бы делать этого, если бы мы реализовали функцию roadStep так, чтобы она принимала и возвращала лучшее время по A и по B вместе с соответствующими путями.
Теперь у нас есть функция, которая принимает пару путей и секцию, а также вычисляет новый оптимальный путь, так что мы легко можем выполнить левую свёртку по списку секций. Функция roadStep вызывается со значением в качестве аккумулятора ([],[]) и первой секцией, а возвращает пару оптимальных путей до этой секции. Затем она вызывается с этой парой путей и следующей секцией и т. д. Когда мы прошли по всем секциям, у нас остаётся пара оптимальных путей; кратчайший из них и будет являться решением задачи. Принимая это во внимание, мы можем реализовать функцию optimalPath.
optimalPath :: RoadSystem –> Path
optimalPath roadSystem =
let (bestAPath, bestBPath) = foldl roadStep ([],[]) roadSystem
in if sum (map snd bestAPath) <= sum (map snd bestBPath)
then reverse bestAPath
else reverse bestBPath
Мы выполняем левую свёртку по roadSystem (это список секций), указывая в качестве начального значения аккумулятора пару пустых путей. Результат свёртки – пара путей, так что нам потребуется сопоставление с образцом, чтобы добраться до самих путей. Затем мы проверяем, который из двух путей короче, и возвращаем его. Прежде чем вернуть путь, мы его обращаем, так как мы накапливали оптимальный путь, добавляя элементы в начало.
Проведём тест:
ghci> optimalPath heathrowToLondon
