BFS算法 - 在约束步骤的网格上最短步行

问题如下：流浪者开始在网格坐标（x，y）上并希望到达坐标（0,0）。从每个网格点，流浪者可以向北8步或向南3步或向东5步或向西6步（8N/3S/5E/6W）。BFS算法 - 在约束步骤的网格上最短步行

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

澄清：

无限网格
负坐标被允许
队列（链表或阵列）必须用于
本

来源

2010-11-21 Gorkamorka

对不起，但我没有找到任何解释你的问题... – 2010-11-21 12:33:41

任何障碍出现在网格？网格的尺寸是多少？ – bjskishore123 2010-11-21 12:34:26

你为什么不考虑（8N/3S/5E/6W）。我的意思是为什么只推一次北/南/东/西。这不会改变BFS的答案吗？请解释... – 2011-01-04 22:52:11

-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-27 19:12:17 Gorkamorka

你确定这可以吗？如果你总是按顺序添加到队列N，S，E，W，那么你就会有偏见。每四步完成一次，最终向北移动5个单位，向西移动1个单位。如果你的出发点恰好在（0,0）的北部和西部，你将会离开它。 – miked 2011-01-04 23:03:39

的算法没有障碍这个问题将是：

对于每个轴，朝它步骤，直到你对其他的轴位置为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-21 12:37:42 thejh

是的，没有队列需要。愚蠢的家庭作业问题。 – miked 2011-01-04 23:00:42

由于“thejh”表示不需要搜索，但您的任务需要一个。

一种合理的方法是

分析。对于任意（x，y）起始位置是否全部为？检查允许的移动，你可以看到它们可以组合产生1步的水平移动和1步的垂直移动，所以答案是肯定的（为你的介入提供了这个细节）。
找出“广度优先搜索”是什么。维基百科是你的朋友（尽管如果你有机会去大学图书馆，我确实推荐帕特里克·亨利·温斯顿的旧版人工智能，它非常好，非常清晰的解释）。尝试一下更简单的问题。
以几乎相同的方式完成作业的问题。如果遇到任何技术上的C++问题，请到这里询问。

干杯&心连心，

来源

2010-11-21 12:47:42

关注点2：这几乎是我发布的原因:)我一直在四处寻找BFS搜索的解释和代码示例，但是当我找不到任何可以掌握的东西时，我发布了这个问题，因为我明白了它提出的问题以及如何使用DFS（深度优先搜索）而不是BFS来实现和解决此问题。 – Gorkamorka 2010-11-21 13:03:47

这里是我的答案（其实是建立关闭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-05 00:02:13 miked

BFS算法 - 在约束步骤的网格上最短步行

回答

相关问题