はじめに
グラフ理論を学ぶ機会が、増えてきました。
ある出発地点から、目的地点までの経路を考える時にも、グラフ理論が活用できます。
Pythonでは、NetworkXという、グラフ計算ライブラリがあります。
本記事は、NetworkXを使用して、グラフの作成〜経路探索してみました。
今回やりたいことは、３つ。
- 格子状にノードを配置した、グラフを作成する（下図、左）
- グラフから、ランダムにノードを削除する（下図、中央）
- A*アルゴリズムを使用して、経路探索する（下図、右）
コードを書いていく
Step0. 準備
Python 3.8.6、NetworkX 2.6.2を使います。
まず、importしていく。
import matplotlib.pyplot as plt
import networkx as nx
import random
Step1. グラフの作成
今回、_N×M_の格子状にノードを配置した、グラフを作成します。
格子状の配置は、色々試すのに見やすくて好みです。
def make_graph(n, m):# n*mの格子状のグラフ作成
G = nx.Graph()
# n*m個、ノードを追加する
for i in range(n):
for j in range(m):
G.add_node((i,j))
# 縦横(x、y軸)方向にエッジを追加する
for i in range(n):
for j in range(m-1):
if (i,j) in G and (i,j+1) in G:
G.add_edge((i,j), (i,j+1))
for j in range(m):
for i in range(n-1):
if (i,j) in G and (i+1,j) in G:
G.add_edge((i,j), (i+1,j))
# たすき掛け方向にもエッジを追加する
for j in range(m-1):
for i in range(n-1):
if (i,j) in G and (i+1,j+1) in G:
G.add_edge((i,j), (i+1,j+1))
for i in range(n):
for j in range(m):
if (i,j+1) in G and (i+1,j) in G:
G.add_edge((i,j+1), (i+1,j))
# スタート地点、ゴール地点のノードを追加する
G.add_edge((0, -1), (0, 0))# スタート
G.add_edge((n-1, m-1), (n-1, m))# ゴール
# ノードの位置を設定
pos_0={n:(n[1], n[0]) for n in G.nodes()}
# グラフを描画、保存
nx.draw_networkx_nodes(G, pos_0, node_size=30, node_color="0.4")
nx.draw_networkx_edges(G, pos_0, label=1, edge_color="black", width=1)
plt.tick_params(left=True, bottom=True, labelleft=True, labelbottom=True)#軸メモリ描画
plt.savefig('graph_1.png')
plt.figure()
return G
Step2. グラフからランダムにノード削除
Step1で作成したグラフから、ランダムにノードを削除してみます
Step1で、ランダムにノードを作成すれば良かった
def set_nodes_to_delete(num, n, m):# 削除するノードをランダムに選定し、リストに保存
del_n=[]
for i in range(num):# 削除するノードをnum個挙げる
a = random.randint(0, n-1)# 乱数(整数値)の範囲は、0 <= a <= (n-1)
b = random.randint(0, m-1)
del_n.append(tuple([a,b]))# タプルでリストに保存
print(del_n)
return del_n
def delete_nodes(Gp, xy_list):# リストに記載されているノードを削除した、グラフを返す
for k in list(Gp.nodes()):
if(k in xy_list)==1:# リスト内のノードが、グラフに含まれているかチェック
print('Boooom!')# なんとなくつけた、削除の効果音
Gp.remove_node(k)# ノード削除
# ノード削除後グラフを描画、保存
pos_0={n:(n[1], n[0]) for n in Gp.nodes()}
nx.draw_networkx_nodes(Gp, pos_0, node_size=30, node_color="0.4")
nx.draw_networkx_edges(Gp, pos_0, label=1, edge_color="black", width=1)
plt.tick_params(left=True, bottom=True, labelleft=True, labelbottom=True)#軸メモリを描画する
plt.savefig('graph_2.png')
plt.figure()
return Gp
Step3. A*アルゴリズム使用
経路探索に、A*アルゴリズムを使用します。A*アルゴリズムの概要説明は省略します。
（参考）Wikipedia A*
def distance(a, b):# ヒューリスティック関数に、ユークリッド距離を利用する
(x1, y1) = a
(x2, y2) = b
return ((x1-x2)**2 + (y1-y2)**2)**0.5
def astar(Gp, n, m):# 入力したグラフから、A*アルゴリズムで経路探索
path = nx.astar_path(Gp, source=(0, -1), target=(n-1, m), heuristic=distance, weight='weight')# (0,-1)から(n-1,m)までの経路を探索
print(path)# 導出した経路を確認する
# 結果を描画、保存
pos_1 = {l: (l[1], l[0]) for l in Gp.nodes()}
node_color=['blue'if(i in path)==1 else '0.4'for i in Gp.nodes()]# 導出した経路を青色で着色する
nx.draw_networkx_nodes(Gp, pos_1, node_size=30, alpha=1, node_color=node_color)
nx.draw_networkx_edges(Gp, pos_1, edge_color="black", width=1)
plt.tick_params(left=True, bottom=True, labelleft=True, labelbottom=True)#軸メモリを描画する
plt.savefig('graph_3.png')
plt.show()
plt.figure()
Step4. 実行
print('Please enter the number of nodes in the y-axis direction.')
n = int(input())# y方向(上下方向)
print('Please enter the number of nodes in the x-axis direction.')
m = int(input())# x方向（左右方向）
print('Please enter the number of nodes to be deleted.')
num = int(input())
G1 = make_graph(n, m)# n*mの格子状にノードを配置したグラフ(G1)を作成
del_n = set_nodes_to_delete(num, n, m)# 削除するノードを任意の数、ランダムに選ぶ
G2 = delete_nodes(G1, del_n)# G1から、ノードを削除したグラフ(G2)を作成
astar(G2, n, m)# G2にA*アルゴリズムを使用する
おわりに
今回、NetworkXを利用して、グラフを作成し、A*アルゴリズムを使用してみました。
効率良く、経路探索するために、ヒューリスティック関数の設計がポイントです。
今後は、様々なシチュエーションを想定し、ヒューリスティック関数を設計してみます。