我正在使用两种不同的数据结构来解决这个搜索问题。 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)
最佳答案
我认为您对这两次搜索的费用处理不正确。
对于 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)
),并且您可以在(摊销的)恒定时间内向它们添加新值。
关于python - 为什么我的 A* 搜索返回与 UniformCostSearch 相同的扩展空间?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35427739/