1
誤解されていない限り、UCSはBFSと同じですが、最も浅いノードを展開する代わりに、パスコストが最も低いノードを展開します。 （そのためにQueueの代わりにPriorityQueueも使用しています）私はBFSコードをコピーし、各ノードのパスコストを追跡するための追加マップを作成し、アイテムがキュー/優先キューにプッシュ/ポップされる方法を変更しました。BFSおよびUCSアルゴリズム。私のBFSの実装は動作しますが、UCSは動作しません。理由を理解できない
注：GETSUCCESSORS（状態）のトリプルのリストを返す（状態、行動、コスト）
これらは私の実装の両方がある：
BFS：
def breadthFirstSearch(problem):
"""Search the shallowest nodes in the search tree first."""
queue=Queue()
objectQueue=Queue()
visited=set()
actions=[]
flag=0
objectMap={}
actionMap={}
start=problem.getStartState()
objectMap[start]=start
queue.push(start)
objectQueue.push(start)
if problem.isGoalState(start):
return actions
while queue:
parent=queue.pop()
object=objectQueue.pop()
if parent in visited: continue
visited.add(parent)
if problem.isGoalState(parent):
while object!=start:
action=actionMap[object]
actions.append(action)
object=objectMap[object]
return actions[::-1]
children=problem.getSuccessors(parent)
for child in children:
queue.push(child[0])
objectQueue.push(child)
objectMap[child]=object
actionMap[child]=child[1]
flag=1
util.raiseNotDefined()
UCS：
def uniformCostSearch(problem):
"""Search the node of least total cost first."""
queue=PriorityQueue()
objectQueue=PriorityQueue()
visited=set()
actions=[]
flag=0
objectMap={}
actionMap={}
costMap={}
start=problem.getStartState()
costMap[start]=0
objectMap[start]=start
queue.push(start, 0)
objectQueue.push(start, 0)
if problem.isGoalState(start):
return actions
while queue:
parent=queue.pop()
object=objectQueue.pop()
if parent in visited: continue
visited.add(parent)
if problem.isGoalState(parent):
while object!=start:
action=actionMap[object]
actions.append(action)
object=objectMap[object]
return actions[::-1]
children=problem.getSuccessors(parent)
for child in children:
costMap[child]=costMap[object]+child[2]
queue.update(child[0], costMap[child])
objectQueue.update(child, costMap[child])
objectMap[child]=object
actionMap[child]=child[1]
flag=1
util.raiseNotDefined()
私はBFSが完全に機能していますが、私のUCSは失敗しています。ここで失敗するテストとその結果は次のとおりです。
B1 E1
^\ ^\
/ V / V
*A --> C --> D --> F --> [G]
\ ^ \ ^
V/ V/
B2 E2
A is the start state, G is the goal. Arrows mark
possible state transitions. This graph has multiple
paths to the goal, where nodes with the same state
are added to the fringe multiple times before they
are expanded.
The following section specifies the search problem and the solution.
The graph is specified by first the set of start states, followed by
the set of goal states, and lastly by the state transitions which are
of the form:
<start state> <actions> <end state> <cost>
start_state: A
goal_states: G
A 0:A->B1 B1 1.0
A 1:A->C C 2.0
A 2:A->B2 B2 4.0
B1 0:B1->C C 8.0
B2 0:B2->C C 16.0
C 0:C->D D 32.0
D 0:D->E1 E1 64.0
D 1:D->F F 128.0
D 2:D->E2 E2 256.0
E1 0:E1->F F 512.0
E2 0:E2->F F 1024.0
F 0:F->G G 2048.0
student solution: ['1:A->C', '0:C->D', '0:E1->F']
student expanded_states: ['A', 'B1', 'C', 'B2', 'D', 'E1', 'F', 'E2']
correct solution: ['1:A->C', '0:C->D', '1:D->F', '0:F->G']
correct expanded_states: ['A', 'B1', 'C', 'B2', 'D', 'E1', 'F', 'E2']