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

Question

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

我已经实施了几种提高效率的方法（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

如果我没看错的话self.blocks是字典。您可以使用

复制它

newBlocks = self.blocks.copy()  # or: dict(self.blocks)

节省一些时间。 deepcopy 在这里不需要。

Answer 2

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

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

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

这应该会自动实现 tie-breaking，我们更喜欢成本主要是 g（实际成本，可靠信息，已知是正确的）的路径，而不是那些同样的总成本f更大程度上是由启发式h决定的（启发式，猜测，可能不完全是correct/reliable）。这通常是 A* 的最佳 tie-breaker。从理论上讲，该乘法可能会使您的启发式算法不可接受，但如果乘数足够接近 1.0，那将无关紧要。

假设 current 的得分为 f_current，并且刚从 openHeap 中被淘汰。假设一个新生成的邻居最终得到完全相同的 f 分数（只是现在一个更大的 g 分量和一个更小的 h 分量）。您肯定知道，在下一次迭代中，具有此分数的节点将立即再次弹出。这意味着实际将其推入堆中然后再次弹出是低效的。

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

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

Answer 3

Dennis 和 jsmolka 都帮助了我，但我的代码的致命缺陷就在这里：

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

    ...

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

我的理解是对象的 lt() 函数在它被推入堆时被调用。如果是这种情况，我会将我的状态推送到堆中——然后再更改值，但为时已晚，无法更改顺序。

我修改了这部分，现在同样的谜题需要 5.3 秒，感谢 jsmolka 和 Dennis，从 86 秒下降到他们帮助之前的 250 秒。

完成代码为here，相关部分如下

for neighbor in current.get_neighbors(cameFrom.get(current)):
        # Skip it if it's already been evaluated
        if neighbor in closedSet:
            continue

        tentative_gScore = gScore[current] + 1
        # If this path costs less than previous paths here...
        if tentative_gScore < gScore[neighbor]:
            # Update the values for this state.
            cameFrom[neighbor] = current
            gScore[neighbor] = tentative_gScore
            fScore[neighbor] = gScore[neighbor] + (1.0001 * neighbor.heuristic_estimate_manhattan(goal))

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

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

N-puzzle a-star python solver efficiency

python

performance

a-star