问题标签 [breadth-first-search]

我正在解决这个 BFS 作业问题，我相信我遵循的逻辑是正确的，但我陷入了无法确定的实现错误。我正在寻求帮助调试此解决方案，而不是提出新的解决方案。

问题陈述：

一个孩子有两个他远程控制的机器人，两个机器人都在 NxN 棋盘上，应该放在棋盘的 A 和 B 位置。

两个机器人同时受到遥控器的影响，相同的命令会影响它们的两个状态。

遥控器只能使两个机器人同时顺时针或逆时针转动 90 度或命令两个机器人前进。

示例： 最左侧的图像显示初始设置。向右的箭头是朝东的机器人，朝上的箭头是朝北的机器人。位置 A 和 B 是机器人的命运。

中心图像显示了将两个机器人向前移动一步的结果。

右图显示了使机器人逆时针旋转的结果。

孩子希望计算将机器人从初始位置带到目的地所需的最少移动次数。

如果机器人被命令翻墙，它会留在原地。

如果两个机器人被命令移动到同一个位置，它们将留在原来的位置。

图 2 显示了这种特殊情况。

两个机器人应该同时到达不同的命运。

输入： 输入由各种测试用例组成，第一行以输入矩阵（棋盘）大小为 N 的整数开头，其中 2<= N <=25。

以下 N 行描述了棋盘格，每行有 N 个字符。

一个 '。' 表示空位。

N、E、S 或 O（西班牙语为 Oeste=West）表示机器人的原始位置和方向。

D 表示棋盘中机器人的命运，“*”表示障碍物。

输入以 N=0 的情况结束。

输入.txt

input.txt 的正确输出：

输入2.txt：

input2.txt 的“正确”（？）输出：

我的解决方案：

问题： 1)在第一个 input.txt 文件中，找到了 9 个动作来找到第一道菜的解法（什么时候应该是 8）和 6 个动作来找到第二道菜的解法（什么时候应该是 3）。最后（不可能的）课程配置正确打印出 -1。

2）在第二个 input.txt 文件中，教授说它应该为第一门课程打印 -1 和 -1，尽管我的程序为第二种情况找到了一个合理的解决方案，而为第一种情况找到了一个奇怪的解决方案（这是我认为一个更有经验的调试器可以提供帮助，我不知道在第一种情况下跟踪命运输出的原因）。我的教授提出的输出正确吗？我的算法也卡在应该打印 46 的情况下。

在 Python 中，我有一个 Graph 类，它有一个顶点对象字典。每个顶点对象都有一个边字典（它由一个起始节点、结束节点和一个权重组成……想象一下箭头的末端指向另一个节点，并为其分配了一个旅行成本号）。

通过这些课程，我正在绘制 - 嗯，一个图表 - 飞机从一个城市飞到另一个城市所花费的时间。从这个图中，我应该使用 Dijkstra 算法确定两个节点之间的最短路径（最快路径）。我还应该确定从起始顶点可到达的所有顶点。

我能够在图表中完美地添加边和删除边（因此，添加节点）。然而，在我的一生中，我似乎无法找到一种简单的方法来使用我创建的数据结构来实现 Dijkstra 算法或广度优先搜索（以确定可达顶点）。

如果有人可以建议我需要做些什么来更改或实现这些算法以使其正常工作，我将非常感谢任何帮助。这是一个家庭作业，我已经做了将近一周，每天好几个小时，但我似乎无法通过这堵墙。再次，我将不胜感激任何建议或帮助。我不希望任何人为我编写代码，但伪代码会有所帮助（并且应用它——从维基百科复制和粘贴伪代码不会帮助我，因为我已经去过那里）。

我对无向图有一个问题，听起来像这样：“对图进行广度优先遍历并列出图的关节点。”。我发现只有使用 DFS 来查找关节顶点的算法。有没有办法用 BFS 找到这些顶点？谢谢你。

更新：删除每个节点，然后在剩余的图上执行 BFS 怎么样？如果它覆盖所有节点，则删除的节点不是关节点。我知道它效率低下，但我认为没关系。

我正在尝试在二叉树中编写广度优先搜索的代码。我已经将所有数据存储在一个队列中，但我无法弄清楚如何前往所有节点并使用它们的所有子节点。

这是我在 C 中的代码：

我已经将根数据排入队列，但它仍然无法正常工作。谁能指出我的错误？

我想使用BFS实现搜索。算法说我必须使用队列才能获得 FIFO 效果。我阅读了 Chris Okasaki 的Purely Functional Data Structures书，发现了如何创建队列（我使用 F# 编写的）：

任何人都知道如何将其实施到 BFS？

我有这段代码可以从列表中创建一棵树：

（想结合这两个代码）

我遇到了一个涉及集合和双端队列的BFS 代码，但我不太理解。我希望这里的一些pythonistas可以帮助n00b。

问题：

1) |= 运算符似乎与按位运算有关-我不知道它与 BFS 有何关系，有什么提示吗？

2) popleft()应该只返回我所理解的一个值，那么它如何返回 parent 和 n 呢？

3)访问的节点系列是新的吗？如果我想要节点，我是否只是继续将它们附加到列表中？

提前致谢。

克雷格

嗨，我正在做一些与反射有关的事情，我不明白我的代码有什么问题。我尝试清理我的代码但是，第一段代码不会更新我的实例值，当我单步执行调试器时，我可以从“newobj”看到正确的结果，但是“下一个”引用由于以下原因而丢失不更新我的实例值。我所做的唯一更改是将“this”添加到队列中，对我来说没有区别。有人可以解释这背后的原因吗？

其他支持代码

有一群人 [比如说 1874 人]，他们都代表世界上不同的公司 [比如说 236 人]。我的任务是最好地确定每个人工作的公司。诀窍是我不能简单地问一个人“你在哪里工作”并得到答案，但我所拥有的是一份包含许多问题的问卷 [比如说 290 个问题] 以及我应该期望员工的确切回答每个公司的。有些公司可能有相同的答案，所以最后，即使我不能确切地确定一个人在哪家公司工作，我应该能够缩小范围并说他/她必须为其中一家公司工作。

使用多值映射和其他一些数据结构，我已经确定了我可以用 1 个问题 [query] 识别的所有公司。使用这些查询来表示树数据结构的根，我需要使用其他查询/问题作为分支来构建树的其余部分以识别其余部分。

有什么建议/帮助/建议吗？

我需要写一篇关于网络爬虫的论文，这个网络爬虫以广度优先探索链接。

我制作了一张图片，展示了爬虫探索的方式。这是正确的广度优先探索吗？：

是否可以仅使用（图形大小）+ 恒定内存量进行呼吸优先搜索 - 换句话说，不记录已访问过哪些节点？