二重木アルゴリズム(Double Tree Algorithm)をPythonで実装する

この記事で得られるもの

• Double Treeアルゴリズムの手順
• Pythonでの実装例

環境

• Google Colaboratory

二重木アルゴリズムの概要

二重木アルゴリズム(Double Tree Algorithm)は巡回セールスマン問題（TSP）の近似解を求めるためのアルゴリズムである。
巡回セールスマン問題はNP困難であり、多項式時間で最適解を求めることは困難であるので、最適解に近い近似解を求めるアルゴリズムが用いられる。

Double Tree アルゴリズムの手順

1. 最小全域木を作成する
2. 最小全域木を二重化する
3. 得られた経路からオイラー閉路を作成する
4. オイラー閉路を用いてハミルトン閉路を作る

ただし、最小全域木の作成にはKruskalのアルゴリズムを用いた。

実装例

import itertools
import networkx as nx

def get_double_tree_tour(n, T):
    checked = [False] * n  # 各ノードが訪問されたかどうかを追跡するためのリスト
    tour = []  # ツアーを保存するリスト
    g = nx.MultiGraph()  # グラフの作成
    g.add_edges_from(T + T)  # 最小全域木を2倍にしてグラフに追加する
    # オイラーサーキット（各エッジを一度だけ通る閉路）を見つける
    for u, v in nx.eulerian_circuit(g):
        if not checked[u]:  # まだ訪問していないノードに出会った場合
            tour.append(u)  # ツアーにノードを追加
            checked[u] = True  # ノードを訪問済みとしてマーク
    tour.append(tour[0])  # ツアーの開始点に戻る
    return tour

# ツアーを取得するためのメイン関数
def get_tour(P, distances, start):
    G = get_complete_graph(P, distances)  # 完全グラフを作成
    # 最小全域木を見つける
    T = [(u, v) for u, v, w in nx.minimum_spanning_edges(G, algorithm='kruskal')]
    tour = shift_tour_start(get_double_tree_tour(len(P), T), start)
    return tour

# ツアーの開始点をシフトする関数
def shift_tour_start(tour, start_node):
    if start_node not in tour:
        raise ValueError("Start node not in tour")
    start_index = tour.index(start_node)  # 開始ノードのインデックスを見つける
    return tour[start_index:] + tour[1:start_index+1]  # ツアーの開始点をシフト

# 完全グラフを生成する関数
def get_complete_graph(P, distances):
    g = nx.Graph()
    edges = []
    for i, j in itertools.combinations(range(len(P)), 2):  # 全てのノードの組み合わせに対して
        edges.append((i, j, distances[i][j]))  # エッジと距離を追加
    g.add_weighted_edges_from(edges)  # グラフに加重エッジを追加
    return g

使用例

def get_tour_cost(tour, distances):
    return sum(distances[tour[i]][tour[i + 1]] for i in range(len(tour) - 1))

if __name__ == '__main__':
    # 2x3のグリッドの座標を定義
    coordinates = np.array([
        [1, 1], [2, 1], [3, 1],
        [1, 2], [2, 2], [3, 2]
    ])

    # 2x3グリッドのダミーの距離行列を定義
    distances = [
        [0, 1, 2, 1, 2, 3],
        [1, 0, 1, 2, 1, 2],
        [2, 1, 0, 3, 2, 1],
        [1, 2, 3, 0, 1, 2],
        [2, 1, 2, 1, 0, 1],
        [3, 2, 1, 2, 1, 0]
    ]

    # ツアーを計算する
    start_index = 0
    d_tour = get_tour(coordinates, distances, start_index)

    # ツアーとそのコストを出力する
    print("Route:", " -> ".join(map(str, d_tour)))
    print("Cost:", get_tour_cost(d_tour, distances))

結果

Route: 0 -> 3 -> 1 -> 4 -> 2 -> 5 -> 0
Cost: 10