【競技プログラミング:リハビリ】巡回セールスマン問題(総当たり)

既存投稿一覧ページへのリンク

一覧ページ

巡回セールスマン問題(総当たり)

sample_code.py

import itertools
import math

def calculate_distance(point1, point2):
    """2点間のユークリッド距離を計算"""
    return math.sqrt((point1[0]-point2[0])**2 + (point1[1]-point2[1])**2)

def total_path_distance(path):
    """経路の総距離を計算（開始地点への戻りを含む）"""
    total = 0.0
    for i in range(len(path)):
        total += calculate_distance(path[i-1], path[i])  # 最後の要素で自動的に開始地点に戻る
    return total

def tsp_bruteforce(cities):
    """ブルートフォースで最適経路を探索"""
    min_distance = float('inf')
    best_path = []
    
    # 全ての順列を生成（開始地点固定で効率化）
    for permutation in itertools.permutations(cities[1:]):
        current_path = [cities[0]] + list(permutation)
        current_distance = total_path_distance(current_path)
        
        if current_distance < min_distance:
            min_distance = current_distance
            best_path = current_path
            
    return best_path, min_distance

if __name__ == "__main__":
    # テキストファイルを読み込む
    with open('./input_data/01.txt', 'r') as file:
        # 各行をタプルに変換してリストに格納
        cities = [tuple(map(int, line.split())) for line in file]

    optimal_path, min_distance = tsp_bruteforce(cities)
    
    print("都市情報")
    print(*cities)
    print("最適経路:")
    print(" → ".join([str(point) for point in optimal_path]))
    print(f"総移動距離: {min_distance:.2f}")

./input_data/01.txt

2 1
9 2
10 9
6 10
10 1

イメージ

例01

都市情報
(2, 1) (9, 2) (10, 9) (6, 10) (10, 1)
最適経路:
(2, 1) → (9, 2) → (10, 1) → (10, 9) → (6, 10)
総移動距離: 30.46

例02

都市情報
(8, 8) (8, 10) (3, 4) (7, 7) (1, 9) (5, 6) (3, 9)
最適経路:
(8, 8) → (8, 10) → (3, 9) → (1, 9) → (3, 4) → (5, 6) → (7, 7)
総移動距離: 20.96