0

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

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

说明：

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

4 回答 4

2

这个问题的算法是：

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

伪代码：

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

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

于 2010-11-21T12:37:42.160 回答
1

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

一个合理的方法是

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

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

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

干杯&hth.，

于 2010-11-21T12:47:42.647 回答
1

这是我使用队列的答案（实际上基于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);

它令人费解，但遵循指示。

于 2011-01-05T00:02:13.637 回答
-2

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

伪代码：

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

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

于 2010-11-27T19:12:17.493 回答