12章は最適化問題についてです。 空き巣が最適な盗みをはたらくためにはどのようなアルゴリズムで物を選んで盗んでいけば良いかを考えるナップザック問題や、 島をつなぐ橋を丁度一度ずつ渡るような散歩が可能か、オイラーによって定式化されたケーニヒスベルクの橋の問題などのグラフ最適化問題が題材になっています。
最短路問題としては深さ優先探索と幅優先探索が取り上げて、実装について丁寧に説明してくれています。 グラフ最適化問題の仕上げとして、章の最後に重み付き有向グラフの探索アルゴリズムについての練習問題があります。 この練習問題を元に重み付き有向グラフの探索問題を考えていきました。
探索アルゴリズム
練習問題をみていく前に、12章で紹介されている探索アルゴリズムについて軽くみていきます。
幅優先探索 (breadth first search: BFS)
まずは探索をスタートするノードに接続する全ての子ノードを探索します。 探索対象がなければ、それぞれの子ノードについて、さらにその子ノードを探索していきます。 まずは同じレベルの子ノードを全て探索してから、次の深さの子ノードを探索していきます。
深さ優先探索 (depth-first search: DFS)
探索した子ノードにさらに子ノードがあった場合は、その子ノードを優先して探索していきます。 とにかく子ノードが見つかったら真っ先にそちらを探索していく形です。
重み付き有向グラフと幅優先探索
そして本章の最後には下記の問題が提示されています。
重み付き有向グラフを考えよう.
幅優先探索アルゴリズムによって最初に見つけられたパスは,
枝の重みの合計が最小であることを保証されているか？ 下記の図は重み付きの有向グラフの例です。ノードをつなぐ枝に重みが付いています。この重みを足した数字が幅優先探索で最小になるかというのが練習問題の問いになります。
この例で0からスタートして5を探索する幅優先探索を実施すると0 -> 1 -> 5 (重み6) が導き出されてしまいます。欲しい答えは 0 -> 2 -> 5 (重み4) ですから枝の重みが最小であることは保証されていませんね。 さて、どうすれば良いかというと、優先順位付きキューを用います。この場合、合計した重みが少ないパスを優先的に探索します。
下記は本書のプログラムを一部拝借しつつ、重みを扱えるようにしました。そして重みが一番少ないパスを探索するUCSメソッドを優先順位付きキューを用いて実装しています。 ちょっと長いですが全部載せておきます。
class Node(object):
def __init__(self, name):
self.name = name
def getName(self):
return self.name
def __str__(self):
return self.name
def __lt__(self, i):
return None
class WeightedEdge(object):
"""重み付きの枝を表すクラス"""
def __init__(self, src, dest, weight):
self.src = src
self.dest = dest
self.weight = weight
def getSource(self):
return self.src
def getDestination(self):
return self.dest
def getWeight(self):
return self.weight
def __str__(self):
return self.src.getName() + '->(' + str(self.weight) + ')' + self.dest.getName()
class Digraph(object):
"""有向グラフを表すクラス"""
def __init__(self):
self.nodes = []
self.edges = {}
def addNode(self, node):
if node in self.nodes:
raise ValueError('Duplicate node')
else:
self.nodes.append(node)
self.edges[node] = []
def addEdge(self, edge):
src = edge.getSource()
dest = edge.getDestination()
weight = edge.getWeight()
if not (src in self.nodes and dest in self.nodes):
raise ValueError('Node not a graph')
self.edges[src].append((weight, dest))
def childrenOf(self, node):
return self.edges[node]
def __str__(self):
result = ''
for src in self.nodes:
for dest in self.edges[src]:
result = result + src.getName() + '->' + dest.getName() + '\n'
return result[:-1]
def printPath(path):
"""パスを表示するメソッド"""
result = ''
for i in range(len(path)):
result = result + str(path[i])
if i != len(path) - 1:
result = result + '->'
return result
def UCS(graph, start, end):
"""重み付き有向グラフを探索するメソッド"""
initPath = [start]
pathQueue = []
from heapq import heappush, heappop
heappush(pathQueue, (0, initPath))
while len(pathQueue) != 0:
(weight, tmpPath) = heappop(pathQueue)
print('Current UCS path:', printPath(tmpPath), ' weight:', weight)
lastNode = tmpPath[-1]
if lastNode == end:
return tmpPath
for (next_weight, nextNode) in graph.childrenOf(lastNode):
if nextNode not in tmpPath:
newPath = tmpPath + [nextNode]
heappush(pathQueue, (weight + next_weight, newPath))
def BFS(graph, start, end):
"""幅優先探索を行うメソッド"""
initPath = [start]
pathQueue = [initPath]
while len(pathQueue) != 0:
tmpPath = pathQueue.pop(0)
print('Current BFS path:', printPath(tmpPath))
lastNode = tmpPath[-1]
if lastNode == end:
return tmpPath
for (weight, nextNode) in graph.childrenOf(lastNode):
if nextNode not in tmpPath:
newPath = tmpPath + [nextNode]
pathQueue.append(newPath)
def testSP():
"""テストメソッド"""
nodes = []
for name in range(9):
nodes.append(Node(str(name)))
g = Digraph()
for n in nodes:
g.addNode(n)
g.addEdge(WeightedEdge(nodes[0], nodes[1], 2))
g.addEdge(WeightedEdge(nodes[0], nodes[2], 3))
g.addEdge(WeightedEdge(nodes[0], nodes[3], 4))
g.addEdge(WeightedEdge(nodes[1], nodes[4], 2))
g.addEdge(WeightedEdge(nodes[1], nodes[5], 4))
g.addEdge(WeightedEdge(nodes[2], nodes[5], 1))
g.addEdge(WeightedEdge(nodes[2], nodes[6], 2))
g.addEdge(WeightedEdge(nodes[2], nodes[7], 3))
g.addEdge(WeightedEdge(nodes[3], nodes[8], 6))
sp = BFS(g, nodes[0], nodes[5])
print('Shortest path found by BFS:', printPath(sp), '\n')
sp = UCS(g, nodes[0], nodes[5])
print('Shortest path found by UCS:', printPath(sp))
testSP() 実行結果は下記のようになります。UCSメソッドでは重みを考慮しているため、最終的なパスは0->2->5になっています。
Current BFS path: 0
Current BFS path: 0->1
Current BFS path: 0->2
Current BFS path: 0->3
Current BFS path: 0->1->4
Current BFS path: 0->1->5
Shortest path found by BFS: 0->1->5
Current UCS path: 0 weight: 0
Current UCS path: 0->1 weight: 2
Current UCS path: 0->2 weight: 3
Current UCS path: 0->1->4 weight: 4
Current UCS path: 0->3 weight: 4
Current UCS path: 0->2->5 weight: 4
Shortest path found by UCS: 0->2->5 まとめ
12章では練習問題をみていきながら優先順位付きキューを用いた重み付き有向グラフの経路探索を実装してみました。 実装においてはWikipediaの均一コスト探索のページや、 Pythonの公式ドキュメントにある優先順位付きキューの説明を参考にさせていただきました。