BFS算法-具有约束步长的网格上最短步长

Question

问题如下:流浪者从网格坐标(x，y)开始，并希望到达坐标(0,0)。从每个gridpoint，流浪者可向北走8步或向南走3步或向东走5步或向西走6步(8N/3S/5E/6W)。

如何使用宽度优先搜索找到从(X，Y)到(0,0)的最短路径？

澄清：

• 无限网格
• 负坐标允许
• 队列(链接列表或数组)必须使用
• 没有障碍出现

Answer 1

我将继续回答我自己的问题，以供将来参考。

Psuedocode：

while (true) {
    if (destination reached)
        break;
    addToQueue(go north);
    addToQueue(go south);
    addToQueue(go east);
    addToQueue(go west);
    getNextFromQueue;
}

还应该注意到，这个应用程序的执行时间增长非常非常快，所以用小的坐标值来测试它。例如，坐标(1,1)提供7级宽度，需要16384次迭代。

Answer 2

这个问题的算法是：

对于每个轴，向它迈进，直到你在另一个轴上的位置是0。

伪码：

while (x!=0) {
  if (x>0) x-=6;
  else x+=5;
}
while (y!=0) {
  if (y>0) y-=8;
  else y+=3;
}

不过，我不明白你为什么要找一条路--没那么复杂。

Answer 3

正如“As”所说，没有必要进行搜索，但您的任务需要搜索。

合理的方法是

1. 分析。是否可以任意(x，y)开始位置？检查允许的移动，您可以看到，它们可以组合产生1步水平移动，和1步垂直移动，所以答案是肯定的(为您的手-提供这方面的细节)。
2. 搞清楚什么是“广度优先搜索”。维基百科是你的朋友(虽然，如果你能进入大学图书馆，我确实推荐帕特里克·亨利·温斯顿(PatrickHenry云斯顿)的“人工智能”()，它确实是很好、非常清晰的解释)。用一些简单的问题试一试。
3. 用同样的方式做作业的问题。在此询问是否遇到任何技术性C++问题.

干杯.