Суммируйте расстояния списка перестановок (Haskell)

Question

У меня есть список городов и функция, которая выдает расстояние между ними. Например:

dist!(Bielefeld,Muenchen) = 598

Теперь я хочу создать функцию, в которой я могу рассчитать полную длину случайного тура между всеми городами. Например:

tourlength [a permutation of the 12 Towns] = whole way you have to travel (as Int)

Я надеюсь, вы понимаете, о чем я. Я не уверен, как интегрировать dist! функция в новый.

Моя вторая проблема заключается в том, что я хочу вычислить, какой город имеет наименьшее расстояние до второго. Чтобы решить это, я хотел использовать greedy функция ниже:

greedy a []     = [a]
greedy a X      = a : greedy (z X - [z])
              z = argmin x : dist a x 
tspgreedy X     = greedy (s x - [s])

Но я не знаю, как перевести это на haskell...

Спасибо за пищу для размышлений

Answer 1

В ответ на ваш первый вопрос один из способов подсчета общего расстояния путешествия, проходящего через ряд городов, выглядит следующим образом:

import Data.Complex (Complex, magnitude)

type Town = Complex Double

dist :: Town -> Town -> Int
dist x y = round $ magnitude (x-y)

journeyDistance :: [Town] -> Int
journeyDistance itinerary = sum . zipWith dist itinerary . drop 1 . cycle $ itinerary

(Не отвлекайтесь на использование комплексных чисел; вы можете определять свои города и расстояния между ними, как вам угодно, например, с помощью поиска в таблице.) Идея этого кода заключается в том, чтобы сжать список, представляющий маршрут, с помощью сам - но компенсируется одним городом (отсюда drop 1) - вычисление расстояний по мере того как мы застегиваем. Таким образом, мы соединяем каждый город с его преемником в маршруте, но операция объединения - это не обычная конструкция кортежа, а наша собственная функция расстояния (отсюда zipWith dist). cycle создает бесконечное повторение маршрута, чтобы обеспечить достаточное количество городов, чтобы "полностью сжать" первоначальный конечный список городов.

Фактически, поскольку второй список в почтовом индексе "вращается вокруг", последний город в первом списке будет в паре с первым городом, образуя двустороннюю поездку. Если вы предпочли бы закончить свое путешествие в последний город, не возвращаясь к первому, то вы можете написать такую ​​функцию:

journeyDistance itinerary = sum . init . zipWith dist itinerary . drop 1 . cycle $ itinerary

Быстрый способ решить вашу вторую проблему может быть таким:

import Data.List (minimumBy, tails)
import Data.Ord (comparing)

closestTowns :: [Town] -> (Town, Town)
closestTowns towns = minimumBy (comparing $ uncurry dist) [(x, y) | (x:xs) <- tails towns, y <- xs]