Bloxorza-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、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、D、R、U、L、L、L、L、大、小、大

這是我的實作，完整代碼在這里，我該怎么做？

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))

uj5u.com熱心網友回復：

假設您的實作中的其他所有內容都是正確的，那只是因為您的啟發式方法是不可接受的。

考慮迷宮：

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 的事實（當一個塊從站立變為躺下時，反之亦然）。為此，您可以將當前啟發式函式的結果除以 2。

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

這給出了長度 28 path ULURRURRRRRRDRDDDDDRULLLLLLD。

uj5u.com熱心網友回復：

正如間接所說，問題在于啟發式函式。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 個點中選擇的。

標籤：Python 蟒蛇-3.x 算法 最短的路径 一个明星

上一篇：將坐標線寫入表示網格的二維陣列

下一篇：獲取比為質數的數的除數