Реализация функции поиска оптимального пути
Какой может быть декларация типа для функции, вычисляющей кратчайший путь для дорожной системы? Она должна принимать дорожную систему как параметр и возвращать путь. Мы будем представлять путь в виде списка. Давайте определим тип Label, который может принимать три фиксированных значения: A, B или C. Также создадим синоним типа – Path.
data Label = A | B | C deriving (Show)
type Path = [(Label, Int)]
Наша функция, назовём её optimalPath, будет иметь такую декларацию типа:
optimalPath :: RoadSystem –> Path
Если вызвать её с дорожной системой heathrowToLondon, она должна вернуть следующий путь:
[(B,10),(C,30),(A,5),(C,20),(B,2),(B,8)]
Мы собираемся пройти по списку секций слева направо и сохранять оптимальные пути по A и B по мере обхода списка. Будем накапливать лучшие пути по мере обхода списка – слева направо… На что это похоже? Тук-тук-тук! Правильно, левая свёртка!
При решении задачи вручную был один шаг, который мы повторяли раз за разом. Мы проверяли оптимальные пути по A и B на текущий момент и текущую секцию, чтобы найти новый оптимальный путь по A и B. Например, вначале оптимальные пути по A и B равны, соответственно, [] и []. Мы проверяем секцию Section 50 10 30 и решаем, что новый оптимальный путь до A1 – это [(B,10),(C,30)]; оптимальный путь до B1 – это [(B,10)]. Если посмотреть на этот шаг как на функцию, она принимает пару путей и секцию и возвращает новую пару путей. Тип функции такой: (Path, Path) –> Section –> (Path, Path). Давайте её реализуем – похоже, она нам пригодится.
Подсказка: функция будет нам полезна, потому что её можно использовать в качестве бинарной функции в левой свёртке; тип любой такой функции должен быть a –> b –> a.
roadStep :: (Path, Path) –> Section –> (Path, Path)
roadStep (pathA, pathB) (Section a b c) =
let timeA = sum $ map snd pathA
timeB = sum $ map snd pathB
forwardTimeToA = timeA + a
crossTimeToA = timeB + b + c
forwardTimeToB = timeB + b
crossTimeToB = timeA + a + c
newPathToA = if forwardTimeToA <= crossTimeToA
then (A,a):pathA
else (C,c):(B,b):pathB
newPathToB = if forwardTimeToB <= crossTimeToB
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
[(B,10),(C,30),(A,5),(C,20),(B,2),(B,8),(C,0)]
Это практически тот результат, который мы ожидали получить. Чудесно. Он слегка отличается от ожидаемого, так как в конце пути есть шаг (C,0), который означает, что мы переехали на другую дорогу, как только попали в Лондон; но поскольку этот переезд ничего не стоит, результат остаётся верным.