Hone star:Bloxorz a-Star搜索

我正在努力在Bloxorz游戏上实现 a-Star 算法。其目标是使用 1 x 1 x 2 块到达终点。我实现了算法,但它是不一致的。有时它没有给出最短的解决方案。例如:

maze = ['00011111110000',
        '00011111110000',
        '11110000011100',
        '11100000001100',
        '11100000001100',
        '1S100111111111',
        '11100111111111',
        '000001E1001111',
        '00000111001111']

对于这个迷宫,我的实现给出了这个结果:

U,L,U,R,R,U,R,R,R,R,R,R,D,R,D,D,L,L,L,D,R,D,L,U,R,U,L,D

它有 29 个动作。但是有一个更短的解决方案有 28 个动作:

U,L,U,R,R,U,R,R,R,R,R,R,D,R,D,D,D,R,U,L,L,L,L,L,L,L,D

这是我的实现,完整的代码是here,我能做些什么呢?

class Node:
    def __init__(self,parent:'Node', node_type:str, x1:int, y1:int, x2:int, y2:int, direction:str=''):
        self.parent = parent
        self.node_type = node_type
        self.g = 0
        self.h = 0
        self.f = 0
        self.x1 = x1
        self.y1 = y1
        self.x2 = x2
        self.y2 = y2
        self.visited = False
        self.direction = direction
    def get_positions(self) -> tuple:
        return (self.x1, self.y1, self.x2, self.y2)
    def __eq__(self, other):
        if type(other) is Node:
            return self.x1 == other.x1 and self.y1 == other.y1 and self.x2 == other.x2 and self.y2 == other.y2
        elif type(other) is tuple:
            return self.x1 == other[0] and self.y1 == other[1] and self.x2 == other[2] and self.y2 == other[3]
        else:
            return False
    def __lt__(self, other:'Node'):
        return self.f < other.f
def aStar(start:Node, end:Node, grid:List[List[str]]) -> List[tuple]:
    open_list = []
    closed_list = []
    heapq.heappush(open_list, start)
    while open_list:
        current:Node = heapq.heappop(open_list)
        if current == end:
            return reconstruct_path(current)
        closed_list.append(current)
        for neighbor in get_neighbors(current, grid):
            if neighbor not in closed_list:
                neighbor.g = current.g + 1
                neighbor.h = get_heuristic(neighbor, end)
                neighbor.f = neighbor.g + neighbor.h
                if neighbor not in open_list:
                    heapq.heappush(open_list, neighbor)
    return []
def reconstruct_path(current:Node) -> List[tuple]:
    path = []
    while current.parent is not None:
        path.append(current.direction)
        current = current.parent
    return ''.join(path[::-1])
def get_heuristic(current:Node, end:Node) -> int:
    return max(abs(current.x2 - end.x1), abs(current.y2 - end.y1))
1

假设你的实现中的其他一切都是正确的,这只是因为你的启发式是不可接受的。

考虑迷宫:

B 1 1 X

你可以在 2 个动作达到目标:

1 B B X : move1
1 1 1 B : move2

但是你的试探法表明至少需要 3 步

max(abs(current.x2 - end.x1), abs(current.y2 - end.y1))
= max(abs(0-3), abs(0-0)) = max(3, 0) = 3

启发式函数不能高估达到 A * 的目标所需的移动次数,以始终给出最佳路径,因为这样做可能会在达到目标时留下未探索的潜在最佳路径(最佳路径可能从未扩展过,因为它的成本被 h(n)高估了)。

你会想要一个启发式的,考虑到一个给定的坐标可以在任何给定的移动中最多改变 2(当一个块从站到躺,反之亦然)。

def get_heuristic(current:Node, end:Node) -> int:
    return 1/2 * max(abs(current.x2 - end.x1), abs(current.y2 - end.y1))

这给出了长度为 28 的路径ULURRURRRRRRDRDDDDDRULLLLLLD

0

正如 inordirection 所说,问题是关于启发式功能。inordirection 的答案不是直接工作,而是给了我一些想法,我想出了这个工作。

return 1/4 * max(max(abs(current.x1 - end.x1), abs(current.y1 - end.y1)), max(abs(current.x2 - end.x2), abs(current.y2 - end.y2)))

因为可能有两个点定位块我应该选择 x1 和 x2 的最大差异从结束,y1 和 y2 从结束比选择它们的最大值,并乘以 1 / 4,因为它是从 4 点中选择的。

本站系公益性非盈利分享网址,本文来自用户投稿,不代表边看边学立场,如若转载,请注明出处

(34)
伺服转矩控制实例:伺服速度控制(arduino servo sweep)
上一篇
小程序换行代码:换行时在“代码”环境中自动添加换行符号
下一篇

相关推荐

发表评论

登录 后才能评论

评论列表(69条)