A*搜索的最佳启发式

Question

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

我使用曼哈顿距离作为启发式，但搜索并不是在我尝试的所有情况下都有效，有时我会得到无限循环。我相信这是由于董事会中存在障碍的事实。

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

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

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*使用的启发式方法决不能高估成本。由于在跳跃机器人中可以使用一个动作来移动任意距离，因此Manhatten距离将不能作为启发式方法使用。

我能想到的唯一有效的启发式方法是“如果不在同一个row+column上就是2，如果不是最终目标就是1”，因为对角线移动是不可能的。