Namaran

Code daily. Without assist.

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ではその順序を考える必要がなく、必要なセルが必要になったときに再帰的に評価されるだけです。