Namaran

Code daily. Without assist.

2026-09-24

TspVisited.hs

module Main (main) where

import Data.Array (Array, array, listArray, (!))
import Data.Bits (bit, 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 ! (mask, 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

3都市を巡る最短ハミルトン路のコストを、訪問済み集合をビットマスクにしたDP配列dpで求めるつもりのプログラムです。入力はコードに埋め込まれた3都市分の距離行列(n = 3)。いまの出力は保証されません(このコードを実行すると、dpが自分自身を無限に参照し続けるため、GHCが<<loop>>を検出して異常終了します)。本来の出力は7です。何が問題で、どう直せばよいでしょうか?

Answer

dpの状態遷移では、いま訪れた都市cityを訪問済み集合から除いた、1つ前の状態dp ! (何か, prev)を参照しなければなりません。ところがこのコードはclearBit mask cityを書き忘れ、cityを訪れる前と同じmaskのままdp ! (mask, prev)を呼んでいます。訪問済み集合が一切縮まないので、あるセルを計算しようとすると同じmaskを持つ別のセルを必要とし、そのセルの計算がまた別のセルを必要とし……という具合に、基本ケース(mask == bit 0 && city == 0)へ決して辿り着けない参照の輪ができてしまいます。Data.Arrayの配列は、自分自身を参照する定義を遅延評価で成立させます(だからこそ計算順序を自分で書かずに済むのですが)が、その循環が本当に自分自身の値を必要としてしまうと、GHCの実行時システムは評価中のセルがまた自分自身を要求していることを検出し、<<loop>>という例外で止まります。直し方は、訪れた都市を集合から取り除いてから1つ前の状態を参照することです:

          minimum
            [ dp ! (clearBit mask city, prev) + dist ! (prev, city)
            | prev <- [0 .. n - 1]
            , prev /= city
            , testBit mask prev
            ]