参考：http://www.geocities.jp/m_Hiroi/light/pyalgo05.html
グラフをプログラムする場合、よく使われる方法に「隣接行列」と「隣接リスト」があります。隣接行列は 2 次元配列で頂点の連結を表す方法です。頂点が N 個ある場合、隣接行列は N 行 N 列の行列で表すことができます。
グラフの例
グラフをプログラムで書く
隣接行列
縦横がそれぞれa-gまでのノードを表す。エッジがある場合は1にする。g[0][1]は、a-b間のエッジがあることを示す。
g = np.array([
[0, 1, 1, 0, 0, 0, 0],
[1, 0, 1, 1, 0, 0, 0],
[1, 1, 0, 0, 1, 0, 0],
[0, 1, 0, 0, 1, 1, 0],
[0, 0, 1, 1, 0, 0, 1],
[0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0]
])
隣接行列の欠点は、辺の数が少ない場合でも N 行 N 列の行列が必要になることです。つまり、ほとんどの要素が 0 になってしまい、メモリを浪費してしまうのです。この欠点を補う方法に隣接リストがあります。これはつながっている頂点を格納する方法です。
隣接リスト
つながってる頂点を配列にいれる。
g = np.array([
[1, 2], # A
[0, 2, 3], # B
[0, 1, 4], # C
[1, 4, 5], # D
[2, 3, 6], # E
[3], # F
[4] # G
])
探索
深さ優先探索
def search(goal, path): n = path[-1] if n == goal: print(path) else: for x in g[n]: if x not in path: path.append(x) search(goal, path) path.pop()
使い方
search(6, [0])
結果
[0, 1, 2, 4, 6] [0, 1, 3, 4, 6] [0, 2, 1, 3, 4, 6] [0, 2, 4, 6]
再帰をうまく使うと芸術的だな。分かりづらいけど。goalは到達したい場所。pathはスタート地点と通過したい場所を配列で入れる。 ＡからＧに行きたい場合は、search(6, [0])という風にやります。最初にpathの最後の要素を取り出しそれがゴール地点だったら、pathつまりスタート地点からゴール地点までの順番を表示しております。ゴール地点でなければ、現在位置からいける地点を順に取り出し、pathに加えます。その際に、戻らないように今まで通った場所は、次にいける地点から除外します。そして、またsearch(goal, path)を実行します。再帰的に繰り返すことで、Goalに到達可能であれば、いずれGoalが次にいける地点に現れます。これによって、goalへの道順を発見できたことになります。最後のsearchの実行で、pathがprintされます。これで最後のsearchは終了します。もしゴールに到達できなければ、最終的にはg[n]が空になるか、if x not in pathにマッチしないものだけになるか、になるので、これもまた最後のsearchは終了します。そうすると1個前のsearchの後のpopによってpathが1つ前の状態に戻り、forが残ってたら残りのforを回すし、なければ終わりになって、もう1つ前のsearchの実行に戻りまっす。まあ文章で書いてもめちゃくちゃになるけど。再帰を自分でパッと思いつけるようになるのは結構大変だろうな。
これが深さ優先探索といわれるのは、到達可能な深い場所にとりあえずどんどんいって、また戻っては次にいける深いところにどんどん行くことを繰り返すからだと思います。最短経路探索と言われているものをしようとしても、全部やってみて一番短いやつを選択することになるので、いけるところは全部見る必要があるのかなと思います。
幅優先探索
幅優先探索は、最短経路探索に適していて深さ優先探索より効率的だそうです。ただし、深さ優先の場合は諸突猛進型でとりあえず一番深いところまで行って終わったら、戻ってきて、もう今までのことは忘れるのですが、幅優先の場合は、全ての経路を並行して深堀っていきます。そのため、最短経路が発見されるまで全ての経路の道順を記憶しておく必要があり、メモリの必要量が深さ優先に比べて圧倒的に多くなる可能性があります。でも、ものすごい深いグラフだと深さ優先グラフでもメモリが膨大になる可能性があります。
def search(start, goal): q = [[start]] while len(q) > 0: path = q.pop(0) n = path[-1] if n == goal: print(path) else: for x in g[n]: if x not in path: new_path = path[:] new_path.append(x) q.append(new_path)
使い方
search(0, 6)
結果
[0, 2, 4, 6] [0, 1, 2, 4, 6] [0, 1, 3, 4, 6] [0, 2, 1, 3, 4, 6]
qをキューとして使っている。先入れ先出ししている。先入れ先出し。このqで全部の経路を記憶しており、最初に記憶したものは階層が低いパスになるので、最初に記憶したものから順番に取り出している。qがからになるまでwhileを続けている。popで一番古いパスを取り出して、そのパスの最後尾がゴールだったらprintで経路を書き出している。ゴールでない場合、現在地から次にいける地点を取り出して、順番に処理している。処理内容は、単純に今までの経路に取り出した次にいける地点を追加したものを、qに加えているだけ。
このキューをスタックにすると、深さ優先探索になるらしいのでやってみる。
深さ優先探索のwhileバージョン
def search(start, goal): q = [[start]] while len(q) > 0: path = q.pop() n = path[-1] if n == goal: print(path) else: for x in g[n]: if x not in path: new_path = path[:] new_path.append(x) q.append(new_path)
こういうことでしょうか？キューは先入れ先出し、スタックは後入れ先出。qに入っているものをpop()で末尾から取り出せば、後入れ先出になる。とりあえず全部探索できるし、結果もあってるんだけど、最初に再帰でやったやつとは出力順序が異なる。これは、再帰でやったやつは、各配列の先頭から深堀していくのに対して、whileの場合は、配列の末尾から深堀していくから。メモリ的には再帰でやった方がいいんじゃないかと思う。再帰の場合記憶しているのは一つの経路だけだから。
反復深化
反復深化というのは、深さ優先の深堀する最大階層を決めるやつ。1階層目まででまず深さ優先をやって、ダメだったら2階層目まででやるという感じで進めていく。必要となるメモリ量は深さ優先と同じになるので、幅優先と比べるとメモリ使用量は少ない。ただし、1階層目でだめだったら、2階層目までの制限で再度一からやり直すことになり、同じ探索を何度もすることになるため、時間的には無駄が多く効率が悪い。
def id_search(limit, goal, path): n = len(path) m = path[-1] if n == limit: if m == goal: print(path) else: for x in g[m]: if x not in path: path.append(x) id_search(limit, goal, path) path.pop() for x in range(1, g.shape[0] + 1): print(x, 'moves') id_search(x, 6, [0])
結果
1 moves 2 moves 3 moves 4 moves [0, 2, 4, 6] 5 moves [0, 1, 2, 4, 6] [0, 1, 3, 4, 6] 6 moves [0, 2, 1, 3, 4, 6] 7 moves
