Я работаю с двумя разными структурами данных над этой проблемой поиска. Поиск по унифицированной стоимости реализует 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 * Search:
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 работают и находят решение, однако я получаю одно и то же значение расширенных узлов поиска, что является моим вопросом. Почему A* возвращает 620, если UCS также возвращает 620? (Расширение целевого узла для A* в этом сценарии равно 549)
