Safe Haskell	None
Language	GHC2021

Data.Graph.Dense.TSP

Synopsis

data TSPResult a = TSPResult {
- resultTSP :: !a
- freezedTSP :: Vector a
}
runTSP :: (Unbox w, Num w, Eq w, Ord w) => w -> DenseGraph w -> TSPResult w
reconstructTSP :: (Unbox w, Num w, Eq w) => DenseGraph w -> TSPResult w -> Vector Int

Documentation

data TSPResult a Source #

Constructors

TSPResult
Fields resultTSP :: !a freezedTSP :: Vector a

runTSP Source #

Arguments

:: (Unbox w, Num w, Eq w, Ord w)
=> w	inf `(2 * inf <= maxBound)`
-> DenseGraph w
-> TSPResult w

Traveling Salesman Problem

O(n^2 2^n)

>>> resultTSP . runTSP 0x3f3f3f3f $ fromListDG @Int [[0,1,999],[999,0,2],[4,999,0]]
7
>>> resultTSP . runTSP 0x3f3f3f3f $ fromListDG @Int [[0,1,1],[1,0,8],[1,999,0]]
10
>>> resultTSP . runTSP 0x3f3f3f3f $ fromListDG @Int [[0]]
0
>>> resultTSP . runTSP 999 $ fromListDG @Int [[0,-1,999],[999,0,1],[1,999,0]]
1
>>> resultTSP . runTSP 999 $ fromListDG @Int [[0,-1,999],[999,0,-1],[999,999,0]]
997

reconstructTSP :: (Unbox w, Num w, Eq w) => DenseGraph w -> TSPResult w -> Vector Int Source #

O(n^2)

>>> let gr = fromListDG @Int [[0,1,999],[999,0,2],[4,999,0]]
>>> reconstructTSP gr $ runTSP gr
[2,0,1,2]