Graphics Programming

[ALGOSPOT] TSP1 본문

Season 1/하스켈

[ALGOSPOT] TSP1

minseoklee 2015. 4. 15. 12:17

문제: https://www.algospot.com/judge/problem/read/TSP1


n-queen은 며칠 고심하며 코딩했는데 익숙해져서 그런지 tsp는 코드를 금방 짤 수 있었다. 가지치기고 뭐고 그냥 무식하게 모든 경로를 따져서 해를 구한다. 저지는 통과하는데 비슷한 c++ 코드보다 약 15배 느림..


import Control.Monad

import Data.Array

import Data.List


getInt :: IO Int

getInt = read `fmap` getLine :: IO Int


main = do

        numCases <- getInt

        forM_ [1..numCases] $ const $ do

                numCities <- getInt

                distances <- getDistance numCities

                print $ solve distances numCities


type Table = Array (Int, Int) Double

getDistance :: Int -> IO Table

getDistance numCities = do

        input <- forM [1..numCities] $ \i -> (map read) `fmap` words `fmap` getLine :: IO [Double]

        return $ listArray ((1,1),(numCities,numCities)) (foldr1 (++) input)


solve :: Table -> Int -> Double

solve table n = minimum $ map (\i -> goto i (delete i [1..n]) 0.0) [1..n] where

        goto from [] cost = cost

        goto from rest cost = minimum $ [goto to (delete to rest) (cost + (dist from to)) | to <- rest]

        dist from to = table ! (from, to)


성능 분석


1. I/O

getDistance 함수가 입력을 읽어서 2차원 배열을 반환하는 함수다. 아마 getLine이 c++에서 cin으로 string 객체 읽는 것보다 느릴 것이다.. 하스켈로 프로파일링하는 방법을 잘 몰라서 이건 정확히 따져볼 수가 없음..


2. 알고리즘

리스트에서 delete 함수를 남발하는 게 주 원인으로 보이는데 n-queen은 탐색 순서가 일방향(한 줄 아래로 또는 위로)이어서 리스트를 써도 속도 저하의 문제가 없었다. (추가/삭제가 리스트 헤드에서만 일어남)


하지만 여기서는 다음 방문할 도시의 후보가 [2, 3, 4, 5]라면 2와 [3,4,5], 3과 [2,4,5], 4와 [2,3,5], 5와 [2,3,4] 등 모든 경우를 나눠줘야 하기 때문에 상당한 부하가 생긴다. 이걸 리스트로 효율적으로 표현하는 방법이 있는지는 아직 모르겠다.


사실 문제 조건에 삼각부등식을 만족한다고 명시되어 있기 때문에 그냥 다항식 알고리즘인 다익스트라나 벨만-포드 알고리즘을 적당히 변형하면 O(nnn) 안에 끝난다. n <= 8 이기 때문에 경우의 수가 (8*8*8 = 512) vs (8! = 40320)로 대충 따져봐도 80배 빠를 것이다. 하지만 하스켈에서 배열과 메모이제이션으로 동적 프로그래밍하는 코드를 지금 실력으론 짤 수 없기 때문에.. 나중에.. ㅡㅜ

Comments