python - BFS 和 UCS 算法。我的 BFS 实现有效，但我的 UCS 无效。不知道为什么

Question

只要我没记错，UCS 和 BFS 是一样的，唯一的区别是它不是扩展最浅的节点，而是扩展路径成本最低的节点。 (也为此使用 PriorityQueue 而不是 Queue)所以我复制了我的 BFS 代码，创建了一个额外的 Map 来跟踪每个节点的路径成本，并且只改变了项目在 Queue/Priority Queue 中被推送/弹出的方式。

注意:getSuccessors(state) 返回一个三元组列表(状态、 Action 、成本)

这些都是我的实现:

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']

Answer 1

无论当前值如何，您都更新 costMap。因此，您会反复增加先前访问过的和当前 child 的尚未访问过的共同继承人的成本。

考虑这个例子:从 A 开始，在 C 结束。有节点链，每次转换的成本为 1:A->A1->A2->A3->A4->A5->A6->A7-> A8->A9->A10。每个 A 节点以成本 3 通向 B。B 通向 C。您当前的实现将从至少 3 个节点(A、A1、A2)多次更新 B 的成本，即使它的实际成本是 3(A-> B).

您应该检查 child 是否在 costMap 中，将当前的 costMap 值与新值进行比较，只有在新值更好时才将其插入队列。如果 costMap 不包含 child，则将其添加到 costMap 和队列中。