Paizaのレベルアップ問題集『巡回セールスマン問題(近似)』の解説

 Paizaの問題の解説がさっぱりしすぎてて頭を悩ませているのでメモ程度に自分なりの解説を作ってみる。

1. 概要

今回の問題

2-近似によるTSP (paizaランク A 相当)

https://paiza.jp/works/mondai/tsp_problems/tsp_problems__tsp_approx

Python 3で解答に従い書いたコードはこんな感じ

import math
n = int(input())
cities = [list(map(int, input().split())) for _ in range(n)]
routes = []
mst = [[] for _ in range(n)] #隣接行列
tour = []
def calc_dist(a, b):
    return math.sqrt(math.pow(a[0] - b[0], 2.0) + math.pow(a[1] - b[1], 2.0))
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        
    def get_parent(self, a):
        a = self.parent[a]
        while a != self.parent[a]:
            a = self.parent[a]
        return a
    
    def unite(self, a, b):
        a = self.get_parent(a)
        b = self.get_parent(b)
        self.parent[b] = a
    
    def same(self, a, b):
        return self.get_parent(a) == self.get_parent(b)
def dfs(mst, tour, now, before):
    tour.append(now)
    if now != before:
        for nxt in mst[now]:
            if nxt in tour:
                continue
            dfs(mst, tour, nxt, now)
    
for i in range(n):
    for k in range(n):
        tmp = calc_dist(cities[i], cities[k])
        routes.append((tmp, i, k))
        
routes.sort()
uf = UnionFind(n)
for d, i, k in routes:
    if uf.same(i, k):
        continue
    mst[i].append(k)
    mst[k].append(i)
    uf.unite(i, k)
dfs(mst, tour, 0, -1)
print(*tour)

2. 解法

問題を分割して考えていくと答えまでは3ステップ

1. ユークリッド距離をもとにルートの候補を選定
2. Union Findをつかって整理
3. 深さ優先探索でルートを探索

一つ一つ見ていく

2.1 ルートの選定

とりあえず、入力座標の各点から各点までの点と距離を全部計算して、短い順にソートする。短い順にソートすると、最短ルートは、自分から自分に向かう点でユークリッド距離は0になる。

以下の処理がこれに該当する。

for i in range(n):
    for k in range(n):
        tmp = calc_dist(cities[i], cities[k])
        routes.append((tmp, i, k))
        
routes.sort()

2.2 Union Findを使って整理

このままだと、最小全域木はつくれないので、Union Findを使って同じ親を持つルートを排除していく。つまり、(0,0)→(0,0)といったものを消す。また、(0,0)→(0,1)及び(0,0)→(0,2)のうちユークリッド距離の短い方だけを残していく、(0,0) → (0,1)及び(0,1) → (0,0)の一方を消す。そうすることで、mstリストは、最小全域木の隣接リストとなる。

該当部分は以下の通り。

uf = UnionFind(n)
for d, i, k in routes:
    if uf.same(i, k):
        continue
    mst[i].append(k)
    mst[k].append(i)
    uf.unite(i, k)

親が同じならループの先頭に戻り、そうでなければ、隣接リストに情報を記録して、その後に親の情報をufインスタンスに格納していく。

そうすることで親がことなるノードだけの隣接リストが作られる。

3.3 深さ優先探索でルートをたどる。

隣接リストをたどっていく。スタートはどこでもいいが、ここでは0をスタートとしている。

そして出力して終了。

4. まとめ

この問題のポイントは、最小全域木を隣接リストに格納し、それを深さ優先探索でたどっていくとこにあると思う。

参考

公式ブログ

Pythonで「巡回セールスマン問題」を解いてみよう！8つの解法を例題で解説

https://paiza.hatenablog.com/entry/2022/10/07/130000