Реализация функции поиска оптимального пути

Какой может быть декларация типа для функции, вычисляющей кратчайший путь для дорожной системы? Она должна принимать дорожную систему как параметр и возвращать путь. Мы будем пред- ставлять путь в виде списка. Давайте определим тип 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)]

Мы собираемся пройти по списку секций слева направо и со- хранять оптимальные пути по А и В по мере обхода списка. Будем накапливать лучшие пути по мере обхода списка – слева направо... На что это похоже? Тук-тук-тук! Правильно, левая свёртка!

При решении задачи вручную был один шаг, который мы пов- торяли раз за разом. Мы проверяли оптимальные пути по А и В на текущий момент и текущую секцию, чтобы найти новый оп- тимальный путь по А и В. Например, вначале оптимальные пути по А и В равны, соответственно, [] и []. Мы проверяем секцию 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)

Как это работает? Для начала вычисляем оптимальное время по дороге А, основываясь на текущем лучшем маршруте; то же са- мое для В. Мы выполняем sum $ map snd pathA, так что если pathA – это что-то вроде [(A,100),(C,20)], timeA станет равным 120.

forwardTimeToA – это время, которое мы потратили бы, если бы ехали до следующего перекрёстка по А от предыдущего перекрёс- тка на А напрямую. Оно равно лучшему времени по дороге А плюс длительность по А текущей секции.

crossTimeToA – это время, которое мы потратили бы, если бы ехали до следующего перекрёстка на А по В, а затем повернули бы на A. Оно равно лучшему времени по В плюс длительность В в теку- щей секции плюс длительность секции C.

Таким же образом вычисляем forwardTimeToB и crossTimeToB.

Теперь, когда мы знаем лучший путь до А и В, нам нужно создать новые пути до А и В с учетом этой информации. Если выгоднее ехать до А просто напрямую, мы устанавливаем newPathToA равным (A,a): pathA. Подставляем метку А и длину секции а к началу текущего оп-

 

тимального пути. Мы полагаем, что лучший путь до следующего перекрёстка по А – это путь до предыдущего перекрёстка по А плюс ещё одна секция по А. За- помните, А – это просто метка, в то время как а имеет тип Int. Для чего мы подставляем их к началу, вместо того чтобы на- писать pathA ++ [(A,a)]? Добав- ление элемента к началу списка (также называемое конструиро- ванием списка) работает значи-

тельно быстрее, чем добавление к концу. Это означает, что полу- чающийся путь будет накапливаться в обратном порядке, по мере выполнения свёртки с нашей функцией, но нам легче будет обра- тить список впоследствии, чем переделать формирование списка. Если выгоднее ехать до следующего перекрёстка по А, двигаясь по В и поворачивая на А, то newPathToA будет старым путём до B плюс секция до перекрёстка по В и переезд на А. Далее мы делаем то же самое для newPathToB, но в зеркальном отражении.

Рано или поздно мы получим пару из newPathToA и newPathToB. Запустим функцию на первой секции heathrowToLondon. Посколь-

ку эта секция первая, лучшие пути по А и В будут пустыми списками.

ghci> roadStep ([], []) (head heathrowToLondon) ([(C,30),(B,10)],[(B,10)])

Помните, что пути записаны в обратном порядке, так что чи- тайте их справа налево. Из результата видно, что лучший путь до следующего перекрёстка по А – это начать движение по В и затем переехать на А; ну а лучший путь до следующего перекрёстка по В – ехать прямо по В.

ПРИМЕЧАНИЕ. Подсказка для оптимизации: когда мы выполняем timeA = sum $ map snd pathA, мы заново вычисляем время пути на каж- дом шаге. Нам не пришлось бы делать этого, если бы мы реали- зовали функцию roadStep так, чтобы она принимала и возвращала лучшее время по А и по В вместе с соответствующими путями.

Теперь у нас есть функция, которая принимает пару путей и сек- цию, а также вычисляет новый оптимальный путь, так что мы легко

 

можем выполнить левую свёртку по списку секций. Функция 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), который означает, что мы переехали на другую до- рогу, как только попали в Лондон; но поскольку этот переезд ниче- го не стоит, результат остаётся верным.