2026-09-24
TspTrace.hs
module Main (main) where
import Data.Array (Array, array, listArray, (!))
import Data.Bits (bit, clearBit, testBit)
n :: Int
n = 3
dist :: Array (Int, Int) Int
dist =
listArray
((0, 0), (n - 1, n - 1))
[ 0, 4, 1
, 4, 0, 6
, 1, 6, 0
]
dp :: Array (Int, Int) Int
dp =
array
((1, 0), (2 ^ n - 1, n - 1))
[((mask, city), cost mask city) | mask <- [1 .. 2 ^ n - 1], city <- [0 .. n - 1]]
where
cost mask city
| mask == bit 0 && city == 0 = 0
| not (testBit mask city) || not (testBit mask 0) = maxBound `div` 2
| otherwise =
minimum
[ dp ! (clearBit mask city, prev) + dist ! (prev, city)
| prev <- [0 .. n - 1]
, prev /= city
, testBit mask prev
]
answer :: Int
answer = minimum [dp ! (2 ^ n - 1, city) | city <- [1 .. n - 1]]
main :: IO ()
main = print answer
このプログラムを実行すると、何が出力されるでしょうか?
Answer
出力は7です。distは3都市間の距離を並べた3x3の行列(dist ! (i, j)が都市iからjへの距離)で、dp ! (mask, city)は「訪問済み集合がmask(都市0を起点として必ず含む)、直前にいる都市がcityのときの、そこまでの最小移動コスト」を表します。ベースケースはmaskが起点の都市0だけを含みcityも0のときで、コストは0です。それ以外は、maskからcityを除いた1つ前の訪問済み集合(clearBit mask city)のもとで、直前にいた都市prevごとに「そこまでの最小コスト + dist(prev, city)」を計算し、最小のものを選びます。3都市(0, 1, 2)をすべて訪れる経路は0→1→2か0→2→1の2通りしかなく、それぞれのコストはdist(0,1) + dist(1,2) = 4 + 6 = 10とdist(0,2) + dist(2,1) = 1 + 6 = 7なので、最小は7(0→2→1の経路)です。answerはこの2通りに対応するdp ! (7, 1)とdp ! (7, 2)(mask = 7は全都市訪問済みを表すビット集合0b111)のうち小さいほうを返します。Haskellらしい点はdpの定義そのものです——dpは自分自身を参照する配列として1回のarray呼び出しで定義されていますが、遅延評価のおかげで各セルは実際にdp !で参照されたときに初めて計算されます。命令型言語なら「小さいmaskから順に埋める」という計算順序を自分で管理する必要がありますが、Haskellではその順序を考える必要がなく、必要なセルが必要になったときに再帰的に評価されるだけです。