BFS和UCS算法。我的BFS实施有效，但我的UCS无效。不知道为什么 [英] BFS and UCS algorithms. My BFS implementation works but my UCS doesn't. Can't figure out why
问题描述
只要我没记错的话，UCS与BFS相同，唯一的区别是，它不用扩展最浅的节点，而是用路径成本最低的节点进行扩展。 （为此，也使用PriorityQueue而不是Queue）。因此，我复制了BFS代码，创建了一个额外的Map来跟踪每个节点的路径成本，并且只更改了在Queue / Priority Queue中推送/弹出项目的方式。
As long as I am not mistaken, UCS is the same as BFS with the only difference that instead of expanding the shallowest node, it expands the node with the lowest path cost. (Also using PriorityQueue instead of Queue for that)So i copied my BFS code, created an extra Map to keep track of each node's path cost and only changed the way the items are being pushed/popped in the Queue/Priority Queue.
注意：getSuccessors（state）返回一个三元组列表（状态，动作，成本）
Note: getSuccessors(state) returns a list of triples (state, action, cost)
这些是我的两个实现：
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一起提供的自动分级机可以正常工作，但是我的UC S失败。这是它失败的测试及其结果：
According to the autograder I'm provided with BFS works perfectly but my UCS fails. Here is the test that it fails at and its results:
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']
推荐答案
无论如何，您都要更新costMap当前值。因此，您反复增加尚未访问的先前访问的和当前孩子的普通后继者的成本。
You update costMap regardless of current values. Thus you repeatedly increase cost for not yet visited common successor of previously visited and current child.
请考虑以下示例：从A开始，以C结尾。每次转换的费用为1：A-> A1-> A2-> A3-> A4-> A5-> A6-> A7-> A8-> A9-> A10。每个A节点都会导致B的成本为3。B会导致C。您当前的实现会从至少3个节点（A，A1，A2）更新B的成本几次，即使它的实际成本是3（A-> B）。
Consider this example: start from A, end in C. There are nodes chain with cost 1 for each transition: A->A1->A2->A3->A4->A5->A6->A7->A8->A9->A10. Each of A nodes leads to B with cost 3. And B leads to C. You current implementation will update B's cost several times from at least 3 nodes (A, A1, A2), even though it's real cost is 3 (A->B).
您应该检查child是否在costMap中，将当前costMap的值与新值进行比较，并且只有在新值更好的情况下才进入队列。如果costMap不包含子项，请将其添加到costMap和队列中。
You should check if child is in costMap, compare current costMap value to new one and only push into queue if new value is better. If costMap doesn't contain child, add it to costMap and queues.
这篇关于BFS和UCS算法。我的BFS实施有效，但我的UCS无效。不知道为什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
