BFS和UCS算法。我的BFS实现可以工作，但我的UCS不工作。

Question

只要我没有弄错，UCS和BFS是一样的，唯一的区别是，它不是扩展最浅的节点，而是以最低的路径成本扩展节点。(同时使用PriorityQueue而不是队列)所以我复制了BFS代码，创建了一个额外的Map来跟踪每个节点的路径开销，并且只改变了条目在队列/优先级队列中被推送/弹出的方式。

注意: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']

Answer 1

无论当前值如何，都可以更新costMap。因此，您会反复增加以前访问的和当前的子级未访问的公共后继者的成本。

考虑这个例子:从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)。

您应该检查子值是否在costMap中，将当前的costMap值与新的值进行比较，并且只有在新值更好的情况下才进入队列。如果costMap不包含子元素，则将其添加到costMap和队列中。

Answer 2

看来你没有正确构造你的接班人。不知怎么的，你到了e1，却没有从D到D，我想你是在使用字典或列表。尝试使您的代码只使用元组。这样，您将不会传递任何引用和混淆您的代码。

我会用下面的数据。第一个是优先级，第二个是我们已经访问过的节点列表，第三个是扩展的下一个节点。

queue.push((2, (A, C), D))