いろんなアルゴリズム"00.00.00.12"

立ち位置・仕様

• いろんなアルゴリズムをコピペできるように記録するのみ
• 最適化が目的でない
• たまにメモとして解説を残す
• 最低限でまとめる
• データを抽出しやすいように個別のIDを付与
• あるアルゴリズムにおいて、他のアルゴリズムが登場する際にはそのIDを付与
• IDは16進数表記
• なるべく最低限なパッケージで実装
• なるべく特殊なオブジェクト型は使用しない

TargetID

00.00.00.12

ReferenceID

深さ優先探索と幅優先探索との差分がわかりやすいアルゴリズム

• 左優先にするため，深さ優先探索のときにはリストを逆順にしている

def depthOrBreadthFirstSearch(graph_dict, startNode, goalNode, searchMethod='d'):
	if searchMethod == 'd':
		index = -1		#-1の場合は深さ優先探索
	elif searchMethod == 'b':
		index = 0		# 0の場合は幅優先探索
	flag = False
	open_list = []
	close_list = []
	output_list = []
	open_list.append((startNode,None))
	while True:
		if not open_list:
			break

		node, parent = open_list.pop(index)
		close_list.append((node, parent))
		if node == goalNode:
			flag = True
			break

		
		children = graph_dict[node]
		if searchMethod == 'd':
			children.reverse()
		for childNode in children:
			if childNode not in close_list:
				open_list.append((childNode, node))

	if flag:
		child = goalNode
		parent = None
		output_list.append(goalNode)
		while True:
			for c, p in close_list:
				if child == c:
					parent = p
					break
			if parent is None:
				break
			output_list.append(parent)
			child = parent
		return list(reversed(output_list))
	else:
		return None

使用方法

graph_dict = {
    1:[2,3],
    2:[4],
    3:[5,6,7],
    4:[8],
    5:[],
    6:[9],
    7:[10],
    8:[],
    9:[],
    10:[]}
print(depthOrBreadthFirstSearch(graph_dict,1,9,'d'))