问题标签 [breadth-first-search]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
c++ - 广度优先搜索中的问题
此代码片段通过构造 bfs 树来计算具有值 n 和 m 的节点的 b/w 距离。但是在外部 while 循环的第一次迭代中构造的 bft 树以某种方式保留了它的值,while 循环的进一步迭代对 bft 没有影响
这里的图表是类型vector<list<gnode>>
bfs 是 bft_data 类的对象:
list - Prolog 使用 BFS 获取不同列表中的元素
我是 prolog 的新手,为了提高我的技能,我正在尝试做一些锻炼。目前我被 BFS 困住了,假设树是这样的:
在我的查询之后,我有类似的东西
或者至少:
我想知道如何将结果按深度级别排序为输出,例如:
或者,在最好的情况下,类似:
帮助!
java - 高效实现广度优先算法的动态队列
我正在构建一个广度优先图形搜索算法,用于搜索伦敦地铁。
我已经弄清楚了算法,但您可能很清楚,该算法需要一个队列 ADS 来跟踪所有需要搜索的边缘(以正确的顺序)。
我一直在阅读有关管理队列和大量或大量排队项目(边缘)的效率问题。
谁能告诉我如何实现一个基于 Java ArrayList 的队列,它可以跟踪头部和尾部,并在内存增长时有效地管理内存?
任何提示/指针非常感谢!
java - 邻接表HashMap> 未能找到其值
我正在调试使用图形数据的邻接列表表示的广度优先搜索算法:HashMap<String, ArrayList<Edge>>
. 每个 String 键是地铁站的名称,每个 ArrayList 是该站的边列表。
我正在使用队列按照遍历的顺序存储图的节点。所以我检查队列中的下一个是孩子的名字。然后我想通过使用类似childEdges = stationsAdjacencyList.get(childNodeName);
.
我的语法有点不同,但请检查下面的代码。
目前 .get() 函数没有返回 ArrayList 而是null
每次都返回。我知道 HashMap 查找正在接收正确的密钥。它只是拒绝从它的相关存储桶中给我任何价值。
如果代码不是很干净或没有像样的注释,请道歉,它会不断变化。希望有人能告诉我为什么ArrayList<Edge> nextNodeEdges = adjacencyList.get(endpointName);
没有获取任何东西。
谢谢!!
c++ - 没有“先前”向量的 Dijkstra 算法
我有兴趣找到图中任何节点与根/源之间的最小距离。所有链接都有权重。我不认为我需要使用previous[]
,在维基百科文章中指出,因为我不需要知道每个节点的父节点。那是对的吗?此外,如果权重都等于 1,我想我可以运行 BFS?
puzzle - Java:使用健身功能解决 15 个难题
我目前正在研究一个使用适应度函数解决 15 个难题的项目。有3种健身功能可以使用,
- 适应度函数1= 1 - (错位棋子数/棋子总数);
- 适应度函数2 = 1-(所有错位瓷砖距离目标位置的距离之和/64)
- 适应度函数3=(适应度2+适应度1)/2
求解器旨在搜索提高适应度函数 VALUE 的可能移动,直到解决整个拼图板(其中适应度函数 = 1)。我在尝试生成动作时备货,因为求解器会打印不成功的搜索路线以及实际路线,例如 W,S,W,N,S,N,S,N,S,N,S,N,S,N,S ,N,S,N (顺序相反),表示 NWSW。然而,求解器来回搜索多次,并打印出不需要的路线。我想在递归中排除以前访问过的位置,并且只打印有效的移动而不是不成功的移动。代码如下:
depth-first-search - 关于广度优先完整性与深度优先不完整性的问题
根据 AIMA(人工智能:现代方法)中的 Norvig 的说法,深度优先算法并不完整(不会总是产生解决方案),因为在某些情况下,正在下降的子树将是无限的。
另一方面,如果分支因子不是无限的,则说广度优先方法是完整的。但这不是与 DFS 中子树无限的情况相同的“事情”吗?
如果树的深度是有限的,就不能说 DFS 是完整的吗?那么 BFS 是完整的而 DFS 不是完整的,因为 BFS 的完整性依赖于分支因子是有限的!
python - 三字母词广度优先搜索,优化
我在 Python 中使用广度优先搜索算法来查找从三个字母单词到另一个单词的最短“路径”。我已经让它工作了,但性能很糟糕,我怀疑我的单词儿童生成功能。
基本上,对于我从队列中弹出的每个单词,我都会生成所有其他可以通过交换一个字母来形成的三字母单词。该函数的工作原理如下:
这通常需要大约 0.03 秒。有没有更快的方法来做到这一点?
search - 如何使用广度优先搜索获取 2 个节点之间的路径?
我试图在图中的两个节点之间找到一条路径,其中边未加权。
我正在使用广度优先搜索,它在找到目标时停止,以查找路径的存在,但我不确定如何获取路径本身。
我尝试查看已访问节点的列表,但这似乎没有帮助。我看到有人使用 prolog 回答了这个问题,但我是一名 C++ 程序员。
我也看过Dijkstras algorithm
,但这似乎有点过头了,因为一个简单的广度优先搜索几乎让我一路走来。
如何使用广度优先搜索获取 2 个节点之间的路径?
java - 如何实现广度优先遍历?
这就是我所拥有的。我以为预购是一样的,先把它和深度混在一起!