и
>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. Для чего мы подставляем их к началу, вместо того чтобы написать