A* 搜索的最佳启发式

Question

我正在使用 A* 搜索实现 Ricochet Robots 游戏。游戏的目标是将特定的机器人放在棋盘的特定位置。棋盘可以有几面墙，还有 3 个机器人可以移动。

我使用曼哈顿距离作为启发式方法，但搜索在我尝试的所有情况下都不起作用，有时会出现无限循环。我想是因为棋盘上有障碍物吧。

对于这种情况最好的启发式是什么？

这是 a* 搜索功能的代码。它接收启发式函数作为输入。该节点是一个具有当前状态和当前板的对象。

def astar_search(problem, h, display=False):
    h = memoize(h or problem.h, 'h')
    return best_first_graph_search(problem, lambda n: n.path_cost + h(n), display)

def best_first_graph_search(problem, f, display=False):
    f = memoize(f, 'f')
    node = Node(problem.initial)
    frontier = PriorityQueue('min', f)
    frontier.append(node)
    explored = set()
    while frontier:
        node = frontier.pop()
        if problem.goal_test(node.state):
            if display:
                print(len(explored), "paths have been expanded and", len(frontier), "paths remain in the frontier")
            return node
        explored.add(node.state)
        for child in node.expand(problem):
            if child.state not in explored and child not in frontier:
                frontier.append(child)
            elif child in frontier:
                if f(child) < frontier[child]:
                    del frontier[child]
                    frontier.append(child)
    return None

Answer 1

A* 使用的启发式绝不能高估成本。由于可以在 Ricochet Robots 中使用一次移动移动任意距离，因此曼哈顿距离将无法作为启发式方法使用。

我能想到的唯一有效的启发式是“如果不在同一行+列上则为 2，否则如果不是最终目标则为 1”，因为对角线移动是不可能的。

A* 搜索的最佳启发式

Best heuristic for A* search

search

artificial-intelligence

a-star