NetworkXで経路探索をやってみる。（グラフ作成〜A*アルゴリズム）

はじめに

グラフ理論を学ぶ機会が、増えてきました。
ある出発地点から、目的地点までの経路を考える時にも、グラフ理論が活用できます。
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*アルゴリズムを使用してみました。
効率良く、経路探索するために、ヒューリスティック関数の設計がポイントです。
今後は、様々なシチュエーションを想定し、ヒューリスティック関数を設計してみます。