使用最小冲突启发式算法求解迷宫的局部搜索

Question

我有一个迷宫(用2D矩阵表示)，如下所示(5 x 5)：

s 1 X 1 X
1 X 1 1 1
1 1 X 1 X
X 1 G 1 X
1 1 1 1 1

其中s是起始位置，G是目标位置，X是障碍物。

如何在迷宫中使用最小冲突启发法应用本地搜索。

我想的是将障碍物用作"冲突"和

1. Start at the starting position, current = start;
2. Find the neighbor that has least number of neighboring obstacles (conflicts), 
3. Update current to that neighbor state, and
4. Repeat until goal is found.

为了简单起见，我只能向左、向右、向上或向下移动；但没有对角线

我做得对吗？如果这里有人能为我指明正确的方向，那就太好了。

Answer 1

这是一个完全有效的解决迷宫的算法。如果有人告诉你，你必须使用最小冲突作为你的启发式方法，我认为这可能是最好的方法，因为它有一些避免死胡同的好特性。然而，我不确定它是否会特别有效。构建一个可以次优处理的迷宫非常容易，例如：

s 1 1 1 1
X 1 X X X
X 1 X G 1
X 1 X X 1
X 1 1 1 1

最关键的是，最小冲突只是一种用于迷宫的奇怪启发式方法。它被设计用于这样的问题，即答案是否解决问题完全取决于它是否与任何规则冲突(例如，N皇后区)。在这些问题中，减少冲突的数量本质上意味着你更接近一个有效的解决方案。迷宫的情况并非如此——决定你是否有解决方案的唯一因素是你是否达到了目标。你可能必须穿过一条障碍隧道才能到达那里。因此，尽管技术上是正确的，但这似乎不是一个理想的方法。