Snowflakeで巡回セールスマン問題を解いてみる

やること

　Snowflakeで数理最適化の問題（整数計画問題）を解いてみるで解いた最適化問題の中でも難しい組合せ最適化問題をSnowflake を用いて解いてみる．少し難しい理由は，こちら明日から役立つ「オペレーションズ・リサーチ概論」を視聴いただければ幸いである．
　今回は，巡回セールスマン問題と呼ばれる問題を解いてみる．都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき，全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である．この問題は，NP困難と呼ばれる問題のクラスに属する．

サンプルコード

以下，Python on Snowflake で動作するサンプルコードである．特に何の工夫もせず，全列挙で最適解を求めているため，少しでも規模が大きくなると厳密な最適解が得られなくなる，または，計算時間が大きくなる．
Snowflake のデータベースへのアクセスは行っていないが，応用すれば，Snowflake のデータベースからデータを入力し，結果を書き込むことも可能である．

import snowflake.snowpark as snowpark
from snowflake.snowpark.functions import col
import pandas as pd
import itertools

def main(session: snowpark.Session): 

    # 距離行列 (都市間距離)
    distances = [
        [0, 10, 15, 20],
        [10, 0, 35, 25],
        [15, 35, 0, 30],
        [20, 25, 30, 0]
    ]
    city_names = ["x1", "x2", "x3", "x4"]

    # 実行
    df_result = solve_tsp_bruteforce_with_df(distances, city_names)
    print(df_result)

    dataframe = session.create_dataframe(df_result)
    
    return dataframe

def calculate_distance(path, distances):
    """パスの総距離を計算"""
    total_distance = 0
    for i in range(len(path) - 1):
        total_distance += distances[path[i]][path[i + 1]]
    # 戻ってくる距離を加える
    total_distance += distances[path[-1]][path[0]]
    return total_distance

def solve_tsp_bruteforce_with_df(distances, city_names):
    """TSPを網羅的探索で解き、結果をデータフレームで出力"""
    n = len(distances)
    cities = list(range(n))  # 都市のインデックス
    min_path = None
    min_distance = float('inf')

    # 全ての経路を探索
    for perm in itertools.permutations(cities):
        current_distance = calculate_distance(perm, distances)
        if current_distance < min_distance:
            min_distance = current_distance
            min_path = perm

    # 最短経路をデータフレームに変換
    records = []
    for i in range(len(min_path)):
        var1 = city_names[min_path[i]]
        var2 = city_names[min_path[(i + 1) % len(min_path)]]
        val = distances[min_path[i]][min_path[(i + 1) % len(min_path)]]
        records.append([var1, var2, val])

    # 合計距離の行を追加
    records.append(["opt", "opt", min_distance])

    # データフレームに変換
    df = pd.DataFrame(records, columns=["var1", "var2", "val"])
    return df