为什么我的 A* 搜索返回与我的 UniformCostSearch 相同的扩展 space？

Question

我正在使用两种不同的数据结构来解决这个搜索问题。统一成本搜索实现了 PriorityQueue，A* 搜索实现了 PriorityQueueWithFunction，它们都是为我预定义的：

class PriorityQueue:
    def __init__(self):
        self.heap = []
        self.count = 0

    def push(self, item, priority):
        entry = (priority, self.count, item)
        heapq.heappush(self.heap, entry)
        self.count += 1

    def pop(self):
        (_, _, item) = heapq.heappop(self.heap)
        return item

    def isEmpty(self):
        return len(self.heap) == 0

class PriorityQueueWithFunction(PriorityQueue):
    # priorityFunction(item) -> priority
    def __init__(self, priorityFunction):
        self.priorityFunction = priorityFunction
        PriorityQueue.__init__(self) # super-class call

    def push(self, item):
        # Adds an item to the Queue with priority from the priority function
        PriorityQueue.push(self, item, self.priorityFunction(item))

所以这是我的 UniformCostSearch 方法，它在我实现通过迷宫寻找目标的 Agent 时是最佳的。 SearchProblem 具有三个组成部分，一个状态，它是一个 int 坐标元组，到达该状态的成本，以及从一开始就到达该状态的方向：

def uniformCostSearch(problem):
    # An empty list to store already expanded states
    closed = set()
    fringe = PriorityQueue()
    fringe.push((problem.getStartState(), 0, []), 0)

    while not fringe.isEmpty():
        node, cost, directions = fringe.pop()

        if problem.isGoalState(node):
            return directions

        if not (node in closed):
            closed.add(node)

            for node, direction, step_cost in problem.getSuccessors(node):
                fringe.push((node, cost + step_cost, directions + [direction]), 
                                                           cost + step_cost)

    if fringe.isEmpty():
        return []

这是最优的，returns 使用迷宫的特定布局，总节点值扩展为 620。我的问题出在我的 A* 搜索实现中：

def aStarSearch(problem, heuristic):
    closed = set()
    totalCost = 0 # Instantiate a totalCost counter
    # A* uses the total cost up to current node + heuristic to goal to decide priority
    fringe = PriorityQueueWithFunction(lambda x: totalCost +
                                       heuristic(problem.getStartState(), problem)
    fringe.push((problem.getStartState(), 0, []))

    while not fringe.isEmpty():
        node, cost, directions = fringe.pop()

        if problem.isGoalState(node):
            return directions

        if not (node in closed):
            closed.append(node)
            totalCost += cost

            for node, direction, cost in problem.getSuccessors(node):
                fringe.push((node, cost, directions + [direction]))

    if fringe.isEmpty():
        return []

A* Search 和 UniformCostSearch 都可以工作并找到解决方案，但是我得到相同的 search nodes expanded 值，这是我的问题。如果 UCS 也返回 620，为什么 A* 返回 620？（本场景A*的目标节点扩展为549）

Answer 1

我认为您对这两项搜索的费用处理不当。

对于 uniformCostSearch，您只需指定每个节点最后一步的成本（getSuccessors 返回的 cost）。因为它是不变的，所以你的优先级队列只是一个常规队列，整个事情就是广度优先搜索。现在，因为优先级队列更喜欢旧值（具有较低的 counts），这实际上与您实际传递实际成本值（例如旧成本加上新步骤的成本）时得到的实际上没有任何不同成本），但你可能应该首先正确地做到这一点：

def uniformCostSearch(problem):
    # An empty list to store already expanded states
    closed = []
    fringe = PriorityQueue()
    fringe.push((problem.getStartState(), 0, []), 0)

    while not fringe.isEmpty():
        node, cost, directions = fringe.pop()

        if problem.isGoalState(node):
            return directions

        if not (node in closed):
            closed.append(node)

            for node, direction, step_cost in problem.getSuccessors(node):
                fringe.push((node, cost + step_cost, directions + [direction]),
                            cost + step_cost)

    if fringe.isEmpty():
        return []

您的 A* 搜索在成本方面更加混乱。成本函数忽略它的输入并且总是将相同的节点传递给启发式函数。将每个成本值添加到 total_cost 的结果是每个节点在添加到队列时都会获得更高的成本。这使得节点得到扩展，与统一成本搜索 FIFO 相同。

您需要让成本函数检查其参数的成本，并将参数的节点用作启发式函数的参数。尝试这样的事情：

def aStarSearch(problem, heuristic):
    closed = []
    # A* uses the total cost up to current node + heuristic to goal to decide priority
    def cost_func(tup):
        node, cost_so_far, directions = tup   # unpack argument tuple
        return cost_so_far + heuristic(node, problem) # I'm guessing at heuristic's API

    fringe = PriorityQueueWithFunction(cost_func)
    fringe.push((problem.getStartState(), 0, []))

    while not fringe.isEmpty():
        node, cost, directions = fringe.pop()

        if problem.isGoalState(node):
            return directions

        if not (node in closed):
            closed.append(node)

            for node, direction, step_cost in problem.getSuccessors(node):
                fringe.push((node, cost + step_cost, directions + [direction]))

    if fringe.isEmpty():
        return []

最后一个建议是使用 set 代替 closed 列表。 set 使用 is 进行成员测试比使用列表（恒定时间，而不是 O(N)）快得多，并且您可以 add 为它们添加新值（摊销）常数时间。

为什么我的 A* 搜索返回与我的 UniformCostSearch 相同的扩展 space？

Why is my A* Search returning the same expanded space as my UniformCostSearch?

python

search

heuristics

priority-queue

nodes