python - 为什么我的 A* 搜索返回与 UniformCostSearch 相同的扩展空间？

Question

我正在使用两种不同的数据结构来解决这个搜索问题。 Uniform Cost Search 实现了一个 PriorityQueue ，而 A* Search 实现了一个 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 方法，它是我实现代理通过迷宫寻找目标的最佳方法。 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 []

这是最优的，并且使用迷宫的特定布局返回总节点扩展值为 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 都可以工作并找到解决方案，但是我得到相同的搜索节点扩展值，这是我的问题。如果 UCS 也返回 620，为什么 A* 返回 620？ (本场景中A*的目标节点扩展为549)

Answer 1

我认为您对这两次搜索的费用处理不正确。

对于 uniformCostSearch，您只需指定每个节点最后一步的成本(由 getSuccessors 返回的 cost)。由于这是恒定的，因此您的优先级队列只是一个常规队列，整个过程是广度优先搜索。现在，由于优先级队列更喜欢较旧的值(具有较低的计数)，因此实际上与您实际传递实际成本值(例如旧的成本加上新步骤的成本)，但您可能应该首先正确地执行此操作:

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 代替close 列表。使用 is 进行成员资格测试时，set 比列表快得多(恒定时间，而不是 O(N))，并且您可以在(摊销的)恒定时间内向它们添加新值。