7

我正在使用 A* 搜索算法并使用曼哈顿距离作为启发式来实现 NxN 难题求解器，但我遇到了一个奇怪的错误（？），我无法理解。

考虑这些谜题（0 元素是空格）：（
初始）

1 0 2
7 5 4
8 6 3

（目标）

1 2 3
4 5 6
7 8 0

从初始状态达到解决方案的最小移动次数是 11。但是，我的求解器在 17 次移动中达到目标。

这就是问题所在 - 我的谜题求解器主要以正确（最少）的移动数解决可解决的谜题，但对于这个特定的谜题，我的求解器超出了最小移动数，我认为我已经将问题确定为计算错误在这种特殊情况下的曼哈顿距离。

在此链接中，您可以看到我的求解器在做什么（在右侧）以及一个久经考验的求解器在做什么（Brian Borowski 的优秀求解器，可在此处获得）。

在第一步中，Brian 的求解器立即选择将元素 5 向上推的解决方案，但我的求解器有其他想法，并且在堆栈跟踪（在链接上给出）上，我的求解器选择将 2 推到左侧的解决方案（因为该板的曼哈顿距离越小，板子在优先队列的前面）。我看不出问题出在哪里，也不能怪我的曼哈顿距离计算，因为它正确地解决了许多其他 3x3 难题。

以下是我计算给定 Board 的曼哈顿距离的方法：

/**
 * Calculates sum of Manhattan distances for this board and stores it in private field to promote immutability.
 */
private void calculateManhattanDistance() {
    int manhattanDistanceSum = 0;
    for (int x = 0; x < N; x++) // x-dimension, traversing rows (i)
        for (int y = 0; y < N; y++) { // y-dimension, traversing cols (j)
            int value = tiles[x][y]; // tiles array contains board elements
            if (value != 0) { // we don't compute MD for element 0
                int targetX = (value - 1) / N; // expected x-coordinate (row)
                int targetY = (value - 1) % N; // expected y-coordinate (col)
                int dx = x - targetX; // x-distance to expected coordinate
                int dy = y - targetY; // y-distance to expected coordinate
                manhattanDistanceSum += Math.abs(dx) + Math.abs(dy); 
            } 
        }
    manhattanDistance = manhattanDistanceSum;
}

如果您有任何见解或想法，我将不胜感激。

如果需要任何其他代码，我会立即发布。

4

2 回答 2

4

有时我被困在同一个地方，我在 17 步中解决了这个问题。问题是我只对 A* 算法使用启发式 h(n)，而选择下一个节点 A* 使用曼哈顿距离（启发式) + pathcost（从根到达节点的成本称为 g(n)）来做出选择。一旦你把它插入算法，它就像一个魅力。

希望这可以帮助被困在同一个地方的人。

于 2017-11-04T16:13:24.327 回答
1

如果您的启发式方法是可以接受的（并且确实如此，请检查此），那么 A* 总是返回最佳解决方案。可以更慢或更快（扩展更多或更少的节点），但它会返回最佳解决方案。

因此，由于您的启发式是可以接受的，因此问题必须在 A* 算法实现中。

此外，它的第一步不同于最优的这一事实是没有意义的：该算法可以正确地执行回溯以获得未来正确的解决方案路径。所有打开的节点都是下一步的候选者，而不仅仅是当前节点的子节点。

于 2012-09-22T10:25:42.650 回答