0

我有一个城镇列表和一个函数，它给出了两个城镇之间的距离。例如：

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 ...

感谢您的思考

4

1 回答 1

2

在回答您的第一个问题时，计算穿过一系列城镇的旅程总距离的一种方法如下：

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构造行程的无限重复，以确保有足够的城镇与原始的有限城镇列表“完全压缩”。

事实上，因为 zip 中的第二个列表“循环”，所以第一个列表中的最后一个城镇将与第一个城镇配对，形成一个往返。如果您宁愿在最后一个城镇结束旅程而不返回第一个城镇，那么您可以编写如下函数：

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]
于 2013-11-20T13:27:06.040 回答