これができたら中級者？探索アルゴリズム

12000 ワード
Python3 プログラミング アルゴリズム プログラミング教育 初心者 アルゴリズム テキストリンク

プログラミング中級者への道

プログラミングを勉強し、ある程度コーディングができるようになったけれどもなかなか自分の成長を感じることができないあなたに

幅優先探索と深さ優先探索

深さ優先探索とは

深さ優先探索（ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう）は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行う。「縦型探索」とも呼ばれる。
from wikipedia

はい。わかりませんね。
細けぇこたぁいいんだよ！
実践あるのみ！

今回使うデータ(構造)はこれだ！

"幅優先探索"の場合には1, 2, 3, 4, 5...というように番号順にノードを処理していきます。
"深さ優先探索"では、1, 2, 4, 7, 8...という順番になります。

前置きはここまで

実際にコードを紹介していきましょう。

まずはデータを用意します。

s10 = {"content": 10, "children": None}
s9 = {"content": 9, "children": None}
s8 = {"content": 8, "children": None}
s7 = {"content": 7, "children": None}
s6 = {"content": 6, "children": [s10]}
s5 = {"content": 5, "children": [s9]}
s4 = {"content": 4, "children": [s7, s8]}
s3 = {"content": 3, "children": [s6]}
s2 = {"content": 2, "children": [s4, s5]}
s1 = {"content": 1, "children": [s2, s3]}
root = {"content": None, "children": [s1]}

print(root)
# {'content': None, 'children': [{'content': 1, 'children': [{'content': 2, 'children': [{'content': 4, 'children': [{'content': 7, 'children': None}, {'content': 8, 'children': None}]}, {'content': 5, 'children': [{'content': 9, 'children': None}]}]}, {'content': 3, 'children': [{'content': 6, 'children': [{'content': 10, 'children': None}]}]}]}]}

深さ優先探索

深さ優先のアルゴリズムではループにおける一時変数にスタックを使います。
なお、今回スタック変数とキュー変数では同じdequeを使用します。
dequeとはDouble ended queueというデータ構造でスタックとキューの両方の性質を持つデータ構造です。
スタックとして使いたい場合popメソッド、キューとして使いたい場合popleftメソッドを使います。

from collections import deque
# 上記の変数rootをそのまま使います。
result = []
stack = deque()
stack.extend(root.get("children"))
while stack:
  tmp = stack.pop()# スタックとして扱うためpop()
  content = tmp.get("content")
  children = tmp.get("children")
  result.append(content)
  if children:
    stack.extend(children[::-1])

print(result)
# [1, 2, 4, 7, 8, 5, 9, 3, 6, 10]

幅優先探索

幅優先探索の場合のアルゴリズムはどうなるのでしょう？
簡単です。深さ優先探索の処理のループ一時変数をスタックからキューに変えるだけ！

from collections import deque
result = []
queue = deque()
queue.extend(root.get("children"))
while queue:
  tmp = queue.popleft()# キューのためpopleft()
  content = tmp.get("content")
  children = tmp.get("children")
  result.append(content)
  if children:
    queue.extend(children)

print(result)
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

これで君も中級者？ちょっと待って！

中級者への道は再起表現をマスターすることで開かれます。
再起表現はプログラムのメモリ空間のスタック領域をそのまま使いループ処理を実行するもの。

わざわざスタック変数を定義せずに直感的に書くことができるのが利点
言語仕様でtail recursionという機能をサポートしていないと処理の規模によってスタックオーバーフローを引き起こしてしまうのが欠点

再起表現(深さ優先探索)

def recursive(tmp, acc=[]):
  content = tmp.get("content")
  children = tmp.get("children")
  acc.append(content)
  if children is not None:
    for c in children:
      recursive(c, acc)
  return acc

result = recursive(root.get("children")[0])
print(result)
# [1, 2, 4, 7, 8, 5, 9, 3, 6, 10]

後日更新予定