순열 목록 (하스켈)의 거리를 정리하십시오.

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]) 

을하지만 나는 하스켈하는 ... 생각을위한 음식

감사를 번역 방법을 모르는

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]