概要

巡回セールスマン問題(TSP)の一種で、全ての地点を訪問して元の地点に戻る最短経路のコストを求める問題です。ただしコストはユークリッド距離の二乗で定義されます。

考察

この問題はNP困難である巡回セールスマン問題として知られています。地点数\(N\)が最大16と小さいため、全探索は\(O(N!)\)となり計算量的に現実的ではありません。そこで動的計画法を用いて効率的に解きます。ビットマスクを用いて訪問済み地点の状態を表現し、部分問題の最適解を記録することで効率的に解を求めます。

アルゴリズム

ビットDP(動的計画法)を用います。状態を「訪問済み地点の集合(ビットマスク)」と「現在いる地点」の組で定義し、その状態における最小コストを記録します。

具体的には: - dp[mask][i]: 地点集合maskを訪問済みで、現在地点iにいる状態の最小コスト - 初期状態: dp[1][0] = 0 (地点0のみ訪問済み) - 遷移: 各状態から未訪問の地点jへ移動し、コストを加算して更新 - 最終的に全地点訪問後(mask = (1<<n)-1)、地点0に戻るコストを加算して最小値を求める

計算量

• 時間計算量: \(O(2^N \times N^2)\)
• 空間計算量: \(O(2^N \times N)\)

\(N=16\)の場合、状態数は\(2^{16} \times 16 = 1,048,576\)となり、十分扱える規模です。

実装のポイント

• ビット演算を用いて効率的に状態管理を行う

• 大きな数値で初期化(INF = 10**18)

• 地点0からスタートし、地点0に戻るという制約を正確に処理

• コスト計算はユークリッド距離の二乗であることに注意

• 最終的に全地点訪問後、地点0への戻りコストを個別に加算して最小値を求める

  ソースコード

def main():
    import sys
    data = sys.stdin.read().splitlines()
    n = int(data[0])
    points = []
    for i in range(1, n+1):
        x, y = map(int, data[i].split())
        points.append((x, y))
    
    INF = 10**18
    total_mask = (1 << n) - 1
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0
    
    for mask in range(1 << n):
        for i in range(n):
            if dp[mask][i] == INF:
                continue
            for j in range(n):
                if mask & (1 << j):
                    continue
                new_mask = mask | (1 << j)
                cost = (points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2
                if dp[new_mask][j] > dp[mask][i] + cost:
                    dp[new_mask][j] = dp[mask][i] + cost
    
    ans = INF
    for i in range(1, n):
        cost = (points[i][0] - points[0][0])**2 + (points[i][1] - points[0][1])**2
        ans = min(ans, dp[total_mask][i] + cost)
    
    print(ans)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。