只要我没有弄错，ucs和bfs是一样的，唯一的区别是它没有扩展最浅的节点，而是以最低的路径成本扩展节点。（也使用priority queue而不是queue）因此我复制了我的bfs代码，创建了一个额外的映射来跟踪每个节点的路径成本，并且只更改了在queue/priority队列中推送/弹出项目的方式。
注意：getSuccessivers（state）返回一个三元组列表（state、action、cost）
这两个都是我的实现：
博士后：
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()
加州大学：
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()
根据签名者的说法，我有一个完美的工作，但我的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']
最佳答案
无论当前值如何，都会更新costMap因此，您反复增加了以前访问过的和当前孩子的尚未访问的共同继承者的成本。
以这个例子为例：从A开始，到C结束。每个转换都有成本为1的节点链：A->A1->A2->A3->A4->A5->A6->A7->A8->A9->A10每一个节点都有B，代价是3现在的实现将从至少3个节点（a，a1，a2）多次更新b的开销，即使它的实际开销是3（a->b）。
您应该检查子节点是否在costMap中，将当前costMap值与新值进行比较，如果新值更好，则只推送到队列中如果costMap不包含子项，则将其添加到costMap和队列中。
关于python - BFS和UCS算法。我的BFS实现有效，但我的UCS无效。不知道为什么，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/40439810/