python - N-puzzle a-star python求解器效率

Question

我编写了一个旨在解决 slider /n 谜题的 a-star 算法。它在小谜题上工作得很好，但随着复杂性的增加而变得很困难。

我已经实现了几种提高效率的方法(heapq 等)，但我的想法已经走到了尽头。你能想到我还能做些什么来改进它吗？

我的代码在这里: https://repl.it/@Jaspirian/SimilarWoodenMemoryallocator

一些重要的部分:

启发式:

def heuristic_estimate_manhattan(self, other):
    """
    Finds the heuristic estimation of the cost to reach another state from this one.
    This heuristic is based on "manhattan distance."
    """
    estimate = 0

    for index in range(len(self.blocks)):
        estimate += abs(other.blocks[index][0] - self.blocks[index][0]) + abs(other.blocks[index][1] - self.blocks[index][1])

    return estimate

邻域函数:

def get_neighbors(self, previous):
    """
    Gets all adjacent neighbors of the state, minus the previous.
    This function gives 7 neighbors: 4 orthogonal, 4 diagonal, with the previous state trimmed.
    """
    neighbors = []

    moves = ((-1,0),(1,0),(0,-1),(0,1))
    zeroLoc = self.blocks[0]

    for move in moves:
        # swap 0 and whatever
        newBlocks = copy.deepcopy(self.blocks)
        newZeroLoc = (zeroLoc[0] + move[0], zeroLoc[1] + move[1])
        # skip this state if we've moved off the board
        if newZeroLoc[0] < 0 or newZeroLoc[1] < 0 or newZeroLoc[0] > self.width-1 or newZeroLoc[1] > self.height-1:
            # print("we've moved off the board.")
            continue
        # skip this state if it's the same as the previous
        if previous and previous.blocks[0] == newZeroLoc:
            # print("this is just the same!")
            continue

        # move the 0
        newBlocks[0] = newZeroLoc

        # move whatever's in that location...
        # to the previous one
        for face, location in newBlocks.items():
            if face != 0 and location == newZeroLoc:
                newBlocks[face] = zeroLoc

        neighbor = Block_Puzzle(newBlocks)
        neighbors.append(neighbor)

    return neighbors

a星算法:

def aStar(start, goal):
"""
A star search algorithm. Takes a start state and an end state.
While there are available moves, loops through them and exits if the end is found.
Returns the list of states that are the "quickest" way to the end.
"""
...
openHeap = [start]
heapq.heapify(openHeap)
...
# While there are yet nodes to inspect,
while(len(openHeap) > 0):
    # Pop the lowest f-score state off. 
    current = heapq.heappop(openHeap)

    # print(len(openHeap))

    # If we've reached the goal:
    if current == goal:
        # return the list of states it took to get there.
        ...
        return path

    # make sure we won't visit this state again.
    closedDict[current] = True

    # For each possible neighbor of our current state,
    for neighbor in current.get_neighbors(cameFrom.get(current)):
        # Skip it if it's already been evaluated
        if neighbor in closedDict:
            continue

        # Add it to our open heap
        heapq.heappush(openHeap, neighbor)

        tentative_gScore = gScore[current] + 1
        # If it takes more to get here than another path to this state, skip it.
        if tentative_gScore >= gScore[neighbor]:
            continue

        # If we got to this point, add it!
        cameFrom[neighbor] = current
        gScore[neighbor] = tentative_gScore
        fScore[neighbor] = gScore[neighbor] + neighbor.heuristic_estimate_manhattan(goal)

return None

Answer 1

在 get_neighbors 中，newBlocks 在这些检查(如边界检查)期间不使用。如果这些检查中的任何一个失败，deepcopy()(或按 jsmolka 的回答进行的常规 copy())将是浪费时间。您可以将该副本移动到之后检查。

---

在算法本身中，我建议将启发式乘以一个略大于 1 的数字。例如:

fScore[neighbor] = gScore[neighbor] + 1.0001 * neighbor.heuristic_estimate_manhattan(goal)

这应该以这样的方式自动实现打破平局，我们更喜欢成本主要为 g(实际成本，可靠信息，已知是正确的)的路径，而不是相同的路径总成本 f 在很大程度上由启发式 h 确定(启发式，猜测，可能不完全正确/可靠)。这通常是 A* 的最佳决胜局。理论上，该乘法可能会使您的启发式算法 Not Acceptable ，但如果乘数足够接近 1.0，那将无关紧要。

---

假设 current 有一个分数 f_current，并且刚刚从 openHeap 中弹出。假设一个新生成的邻居以完全相同的 f 分数结束(只是现在一个较大的 g 组件和一个较小的 h 组件)。您肯定知道，在下一次迭代中，具有此分数的节点将立即再次弹出。这意味着实际将其插入堆中然后再次弹出是低效的。

同时提供一个单独的(未排序的)堆栈会更有效。如果 f 分数等于父节点的 f 分数，则将节点插入此堆栈而不是堆。如果这个堆栈是非空的，总是从这个而不是中弹出节点，而不是从你的堆中弹出。仅当此堆栈为空时才从堆中弹出。

注意:结合上述基于乘法的打破平局，这个想法变得复杂起来。如果您可以手动指定堆的排序标准，您还可以以不同的方式实现打破平局(例如，明确地将基于 f 分数相等的节点视为较小，如果它具有更大的 g/更小的 h).