焼きなまし法

🔥 Vibe プロンプト

「20都市のTSPを焼きなまし法で解決。最終ツアー長を欲張り法と比較。」

import math, random

cities = [(random.randint(0,100), random.randint(0,100)) for _ in range(20)]

def dist(a, b): return math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2)
def tour_len(tour): return sum(dist(tour[i], tour[i+1]) for i in range(-1, len(tour)-1))

def simulated_annealing(cities, temp_start=1000, temp_end=0.01, cooling=0.995):
    tour = cities[:]
    random.shuffle(tour)
    best = tour[:]
    temp = temp_start
    while temp > temp_end:
        i, j = sorted(random.sample(range(len(tour)), 2))
        tour[i:j] = reversed(tour[i:j])
        delta = tour_len(tour) - tour_len(best)
        if delta < 0:
            best = tour[:]
        elif random.random() >= math.exp(-delta / temp):
            tour[i:j] = reversed(tour[i:j])
        temp *= cooling
    return best

sa_tour = simulated_annealing(cities)
greedy = cities[:]; random.shuffle(greedy)
print(f"欲張り法: {tour_len(greedy):.0f}")
print(f"焼きなまし: {tour_len(sa_tour):.0f}")

応用

• VLSI回路設計
• ジョブショップスケジューリング
• タンパク質折り畳み
• 空港ゲート割り当て

重要なポイント

• コアコンセプトをしっかり理解する
• ハンズオンコード例で実践する
• 実世界の問題に応用する
• 演習で知識を強化する

さらに学ぶ

• 公式ドキュメント
• GitHubのオープンソースプロジェクト
• コミュニティフォーラムとディスカッション
• 関連コースとチュートリアル