BFS 算法 - 具有约束步数的网格上最短行走

Question

问题如下：一个流浪者从网格坐标（x，y）开始，想要到达坐标（0，0）。从每个网格点开始，漫游者可以向北走 8 步或向南 3 步或向东 5 步或向西 6 步（8N/3S/5E/6W）。

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

说明：

• 无限网格
• 允许负坐标
• 必须使用队列（链表或数组）
• 不存在任何障碍

Answer 1

这个问题的算法是：

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

伪代码：

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

但是，我不明白为什么你需要搜索路线 - 这并不复杂。

Answer 2

正如“thejh”所说，不需要进行搜索，但您的作业需要进行搜索。

一个合理的方法是

1. 分析。任意（x，y）起始位置都可能吗？检查允许的移动，您会发现它们可以组合起来产生 1 步水平移动和 1 步垂直移动，所以答案是肯定的（在您的提交中提供详细信息）。

2. 弄清楚什么是“广度优先搜索”。维基百科是你的朋友（不过，如果你可以访问大学图书馆，我真的推荐帕特里克·亨利·温斯顿的旧人工智能，它真的很好，非常清晰的解释）。尝试解决一些更简单的问题。

3. 以几乎相同的方式解决作业问题。如果您遇到任何 C++ 技术问题，请在此处询问。

干杯&呵呵，

Answer 3

这是我使用队列的答案（实际上是基于 thejh 的答案）：

//set x to start position
//set y to start position
do {
  if (x<0) Queue.Push(8N);
  if (x>0) Queue.Push(3S);
  if (y<0) Queue.Push(5E);
  if (y>0) Queue.Push(6W);
  while (!Queue.Empty())
  {
    Move(Queue.Pop());
  }
} while (x && y);

它很复杂，但遵循指示。

Answer 4

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

伪代码：

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

还应该注意的是，该应用程序的执行时间增长得非常非常快，因此请使用较小的坐标值对其进行测试。例如，坐标 (1,1) 给出 7 个级别的宽度，需要 16384 次迭代。