STEINER DISTANCE PROBLEMのコード

最小距離を求めるコード

---

以前の投稿でシュタイナー問題 (STEINER DISTANCE PROBLEM) という最小の全長を持つ構造を求める問題を見た. 今回はその際に用いたコードをまとめておく. ただし, 以前にもまとめたように, この問題はNP問題であり, 解はあくまで近似的なものであることに留意したい.

pip install networkx matplotlib scipy


import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
from scipy.spatial import Delaunay

# 点集合を生成する（ランダムな2次元点）
np.random.seed(42)
points = np.random.rand(10, 2)  # 10個のランダムな点 (x, y)

# Delaunay三角形分割で完全グラフを構築
tri = Delaunay(points)
edges = set()
for simplex in tri.simplices:
    for i in range(3):
        for j in range(i + 1, 3):
            edges.add((simplex[i], simplex[j]))

# グラフを作成
G = nx.Graph()
for edge in edges:
    p1, p2 = points[edge[0]], points[edge[1]]
    distance = np.linalg.norm(p1 - p2)
    G.add_edge(tuple(p1), tuple(p2), weight=distance)

# 最小全域木 (MST) を計算
mst = nx.minimum_spanning_tree(G)

# グラフの可視化
pos = {tuple(p): p for p in points}
plt.figure(figsize=(8, 6))

# 元のグラフ（灰色）
nx.draw(G, pos, node_size=50, alpha=0.4, edge_color="gray", with_labels=False)

# 最小全域木（赤色）
nx.draw(mst, pos, node_size=50, edge_color="red", with_labels=False, width=2)

# 点を描画
for point in points:
    plt.scatter(*point, color="blue", s=100)

plt.title("Steiner Tree Approximation with MST")
plt.show()

参考文献

• Ul-Haque, M. M., & Kamble, G. P. (2020). Glimpse of Steiner distance problem. J. Math. Comput. Sci., 10(5), 1559-1570.