我正在处理这个搜索问题，使用两种不同的数据结构。统一成本搜索实现了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方法，该方法在实现代理通过迷宫寻找目标时是最佳的。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* 搜索和 UniformCostSearch 都可以工作并找到解决方案，但是我得到了相同的搜索节点扩展值，这是我的问题。如果 UCS 也返回 620，为什么 A* 返回 620？(本场景下 A* 的目标节点扩展为 549(
我认为您错误地处理了两次搜索的成本。
对于uniformCostSearch，您只需指定每个节点的最后一步的成本(getSuccessors返回的cost(。由于这是常量，因此您的优先级队列只是一个常规队列，整个事情是广度优先搜索。现在，由于优先级队列更喜欢较旧的值(具有较低的count(，这实际上与您实际传入实际成本值(例如旧成本加上新步骤的成本(时得到的值没有任何不同，但您可能应该首先正确执行此操作：
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新值。