【競プロ】巡回セールスマン問題【アルゴ式】

この記事でわかること

• 巡回セールスマン問題の解き方、考え方
• 最初に作ったコード
• あまりに無駄が多いのでリファクタする
• 最終的なコード

アルゴ式：貪欲法：循環セールスマン問題

アルゴ式を初めて見て、この問題に出会いました。

問題文

• 二次元座標上に N 個の頂点 0,1,…, N−1があり、頂点 i の座標は (X i , Y i) です。
• 頂点 0 からスタートしてすべての頂点を経由して頂点 0 に戻ります。総移動距離をできるだけ短くしてください。
  ただし、ここでの距離はユークリッド距離 (日常生活で使われている距離) を指します。
• これに対し、アルルは次のアルゴリズムを考えました。
• まだ訪れていない頂点がある場合は、今いる頂点からまだ訪れていない頂点のうち最も近い頂点に移動する。 ただし、距離が等しい頂点がある場合は最も番号が小さい頂点に移動する。全ての頂点を訪れた後は、頂点 0 に戻る。
• アルルの考えたアルゴリズムを実現するプログラムを作成してください。

入力

N
X_0 Y_0
...
X_N-1 Y_N-1

※細かい説明は今回は省きます

出力

答えを出力する。

設計

• 座標クラス Point
  • x: float
  • y: float
• 巡回セールスマン問題を解くクラス SalesMan
  • n, x, y: float 入力をとりあえずもっておく
  • now: Point 現在の座標
  • unvisit: list[Point] まだ訪れていない座標のリスト（英単語としておかしい）
  • distances: list[float] 実際に移動した距離を保持しておくリスト
  • has_unvisit(): まだ訪れていない点がないか？
  • get_distance(point_a, point_b): 二点の距離を求める
  • get_min_distance(now): 現在点からまだ訪れていない点の中で最小の距離を求める
  • greed(): 貪欲法でこの問題を解いて、移動距離リストを更新する
• main関数
  • 入力を受け付けて、巡回セールスマン問題を解いて、最後移動距離の和を出力

src

import math


class Point:
    def __init__(self, x, y) -> None:
        self.x = x
        self.y = y

class SalesMan:
    def __init__(self, n, x, y) -> None:
        self.n = n
        self.points = []

        for i in range(n):
            p = Point(x[i], y[i])
            self.points.append(p)

        self.now = self.points[0]
        self.unvisit = self.points.copy()
        self.unvisit.remove(self.now)
        self.distances = []

    def has_unvisit(self) -> bool:
        return len(self.unvisit) >= 1

    def get_distance(self, point_a, point_b):
        return math.sqrt((point_a.x - point_b.x) ** 2 + (point_a.y - point_b.y) ** 2)

    def get_min_distance_and_point(self, now):
        min_distance = None
        min_point = None

        for point in self.unvisit:
            now_distance = self.get_distance(now, point)
            if min_distance == None or now_distance < min_distance:
                min_distance = now_distance
                min_point = point

        return min_distance, min_point

    def greed(self):
        # まだ訪れていない頂点があるか？
        while self.has_unvisit():
            # 最も近い点を計算
            distance, point = self.get_min_distance_and_point(self.now)
            # 記録
            self.unvisit.remove(point)
            self.distances.append(distance)
            self.now = point
        else:
            # すべて訪れたら終了
            distance = self.get_distance(self.now, self.points[0])
            self.distances.append(distance)
            return self.distances


if __name__ == '__main__':
    n = int(input())
    x = []
    y = []

    for _ in range(n):
        x_n, y_n = map(int, input().split())
        x.append(x_n)
        y.append(y_n)

    salesMan = SalesMan(n, x, y)
    salesMan.greed()
    ans = sum(salesMan.distances)
    print(ans)

無事AC...

リファクタを考える

• L#15
  • nは保持しなくてもよさそう
• unvisitはunvisitedのほうが正しそう
• get_distance()よりはcalc_distance()のほうが正しそう
• greed()は間違っていそう。greedy algorithmなのでgreedyのほうがよさそう
• 他は何か思いつかないので何かあれば指摘ください