-
1 votesanswersviews
在没有先验知识的情况下在迷宫中查找实体的算法
我有一个像加权迷宫的网格,我需要找到一个实体的最短路径,而不需要任何先前的迷宫知识 . 像A *这样的算法可以预见到知识渊博并在环顾四周时“跳跃”,但是当我拥有一个机器人时,这是不可能的 . 我的第一个想法是最初使用BFS探索整个迷宫,然后在探索上应用A *以考虑权重也找到最短的 . 但这似乎很幼稚 . 有人能指出一些可能适合这个问题的算法吗? -
23 votesanswersviews
广度优先搜索时间复杂度分析
遍历顶点的每个相邻边的时间复杂度是 O(N) ,其中N是相邻边的数量 . 因此,对于V个顶点,时间复杂度变为 O(V*N) = O(E) ,其中E是图中边的总数 . 由于从队列中删除和添加顶点是 O(1) ,为什么将它添加到BFS的总时间复杂度为 O(V+E) . -
0 votesanswersviews
广度优先搜索可用于有向无环图吗?
可以在 Directed Acyclic Graph 上使用广度优先搜索吗? 例如,你从根节点开始(假设它有3个连接的节点,边缘都从根指向它们),在BFS之后,你在有向边缘之后从根访问第一个连接节点,你必须回来到根节点并访问第二个连接节点,如果它是一个无向图,但你不能在有向图的情况下,所以我假设BFS不能用于有向无环图? 此外,一行节点 1 -> 2 -> 3 -> 4 可以被认... -
12 votesanswersviews
随机优先搜索?
遍历图形的两种最常用方法是breadth-first search和depth-first search . 这两种搜索算法都遵循一个通用模板: 创建一个工作清单W,用起始节点s播种 . 虽然工作清单不是空的: 删除工作清单的第一个元素;叫它v . 如果未访问v: Mark v as visited . 对于直接连接到v的每个节点,将u添加到W. 在广度优先搜索中,工作... -
0 votesanswersviews
通过选择根节点来减小广度优先树的深度
如果可以在图形中随机选取根节点,是否存在选择根节点的现有算法,使得生成的广度优先树具有最小的深度或高度? 我有一种预感,我应该选择具有最大扇出的节点作为根节点 . 让我举一个例子 . 有一个循环有向图{(0,1),(1,2),(1,5),(1,6),(2,3),(3,4),(4,2),( 5,2),(6,0)} 如果节点0被选为根,则广度优先树为{(0,1),(1,2),(1,5),(1,6)... -
3 votesanswersviews
使用广度优先搜索从图中生成树?
我正在尝试使用广度优先搜索来创建一个(跨越)树自然地来自遍历图形(未定向和连接),但是我在修改算法时遇到了困难,因此它会生成一棵树 . 我正在使用Java . 这是我的BFS算法 . public void traverse(Node node){ Queue queue= new Queue(); node.visited= true; //Maybe do someth... -
2 votesanswersviews
在clojure中使用广度优先搜索的最短路径
我代表一棵树 A / \ B C /\ D E 像一个clojure矢量中的 [A [B [D] [E]] [C]] . 我需要使用广度优先搜索来找到目标的最短路径 . 我的实际矢量看起来像这样 - ["33L" ["32R" ["31L" ["30R" [false]] [&qu... -
1 votesanswersviews
图形与BFS和DFS树的等价性
我有这个问题,我无法证明 . 有人可以提供一些洞察这个问题 我们有一个连通图G =(V,E),并且作为特定顶点u∈V . 假设我们计算一个以u为根的深度优先搜索树,并获得一个包含G的所有节点的树T.假设我们然后计算以u为根的广度优先搜索树,获得相同的树T.证明G = T.(换句话说,如果T既是深度优先搜索树又是以u为根的广度优先搜索树,那么G不能包含任何不属于T的边 . ) -
149 votesanswersviews
广度优先与深度优先
遍历树/图时,广度优先和深度之间的区别首先是什么?任何编码或伪代码示例都会很棒 . -
8 votesanswersviews
广度优先或深度优先搜索
我知道这个算法是如何工作的,但是不能决定何时使用哪种算法? 是否有一些指导方针,哪一个比其他或任何考虑更好? 非常感谢 . -
4 votesanswersviews
在图中查找所有可能的路径
我正在寻找一些 algorithm ,这将帮助我在图表中找到 all possible 路径 . 到目前为止我发现的一切并不完全令人满意 . 让我们假设我们有一个像这样的图形(树): 让我们使用像 Breadth-First Search 或 Depth-First Search 这样的算法 . 作为回报,我们会得到类似的东西 1, 2, 4, (2), 5, (2), 6, (2), (1),... -
9 votesanswersviews
如何在功能上生成树广度优先 . (使用Haskell)
假设我有以下Haskell树类型,其中“State”是一个简单的包装器: data Tree a = Branch (State a) [Tree a] | Leaf (State a) deriving (Eq, Show) 我还有一个函数“expand :: Tree a - > Tree a”,它接受一个叶子节点,并将它扩展为一个... -
246 votesanswersviews
什么时候使用深度优先搜索(DFS)与广度优先搜索(BFS)是否可行?
我理解DFS和BFS之间的区别,但我很想知道何时使用一个而不是另一个更实用? 任何人都可以提供任何有关DFS如何胜过BFS的例子,反之亦然? -
9 votesanswersviews
广度优先搜索Java中的8x8网格
我要做的是计算使用最短路径到达目标需要多少动作 . 必须使用广度优先搜索来完成 . 我将8x8网格放入一个2d数组,其中填充了四个字符之一,E表示空(可以移动到这些点),B表示阻塞(无法移动到这里),R表示机器人(起始点)或G为了目标 . 该算法必须按顺序向上,向左,向右,然后向下检查可移动空间,我相信我已经正确完成了 . 检查节点后,将其内容更改为“B” . 如果无法达到目标,则应返回0 . 我... -
0 votesanswersviews
为什么要为节点着色而不是在数据结构中跟踪它们?
我正在比较两本书之间的图形遍历材料:CLRS的算法导论,第3版(简称为CLRS)和RN的人工智能:现代方法,第3版(简称为AIMA) . 在广度优先搜索和深度优先搜索的两个部分中,我注意到CLRS通过分别对白色,灰色和黑色着色来跟踪未访问的节点,边界节点和访问节点,同时AIMA跟踪未访问的,边界和访问的通过跟踪图形及其节点外部的数据结构来跟踪边界和受访节点 . 似乎AIMA中使用数据结构来跟踪边界... -
26 votesanswersviews
如何检测有向图是否是循环的?
我们如何检测有向图是否是循环的?我认为使用广度优先搜索,但我不确定 . 有任何想法吗? -
1 votesanswersviews
广度优先与深度优先搜索的输入/输出
我的问题不是关于任何一种搜索类型的机制 . 我觉得它比那更平凡 - 我不理解任何一个的输入和输出 . 更具体地说,在CLRS中,BFS将图形和源节点作为输入,但DFS仅采用图形 . DFS不关心你从哪里搜索? 这就是输入混乱 . 输出混乱是在DFS中,当你完成时,你有一个类似于表格的结构,记录每个节点的发现并完成时间,对吗?如何从中提取解决方案,即从源节点到目标节点的路径? 我希望我有意义 . ... -
13 votesanswersviews
如何实现广度优先搜索到一定深度?
我理解并且可以轻松实现BFS . 我的问题是,我们怎样才能将这个BFS限制在一定深度?假设,我只需要深入10级 . -
0 votesanswersviews
深度优先搜索和广度优先搜索图表
我正在尝试在文本文件上实现深度优先搜索和广度优先搜索 . 代码应该跳过文本文件中的单词,但是在单词后面的字母上执行深度优先搜索和广度优先搜索 . 我收到了一个不兼容的类型错误 . 下面是我的代码和文本文件 . PROG Scanner myScanner = new Scanner(new File(args[0])); Graph obj = new Graph(); ... -
1 votesanswersviews
重复搜索树上的节点? (AI)
我正在做以下问题: 考虑3拼图问题,其中电路板是2X2矩阵 . 有三个瓷砖编号为1,2和3,并且有一个空白瓷砖 . 有四个操作员可以向上,向下,向左或向右移动空白 . 开始和目标状态如下图所示 . 在搜索树的帮助下,显示如何使用以下命令找到目标的路径: 一个 . 深度优先搜索(3分) 湾广度优先搜索(3分) C . A *搜索,启发式是移动次数和错位瓦片数量的总和 . (3分) 如果搜索方... -
14 votesanswersviews
如何使用广度优先搜索获得2个节点之间的路径?
我试图找到 path between two nodes in a graph ,其边缘是 unweighted . 我正在使用广度优先搜索,它在找到目标时停止,以便找到路径的存在,但我不确定如何获取路径本身 . 我试着查看访问过的节点列表,但这似乎没有帮助 . 我看到有人用prolog回答这个问题,但我是一名C程序员 . 我也看了 Dijkstras algorithm ,但这似乎过度杀人,因... -
98 votesanswersviews
在寻找最短路径时,广度优先搜索如何工作?
我做了一些研究,我似乎错过了这个算法的一小部分 . 我理解广度优先搜索是如何工作的,但我不明白它究竟是如何让我到达一条特定的路径,而不是只告诉我每个节点可以去哪里 . 我想解释我困惑的最简单方法是提供一个例子: 例如,假设我有一个这样的图形: 我的目标是从A到E(所有边缘都没有加权) . 我从A开始,因为那是我的起源 . 我排队A,然后立即将A排队并探索它 . 这产生B和D,因为A连接到B和D.... -
2 votesanswersviews
广度优先搜索生成的节点数是多少?
没有 . 根据我的书,广度优先搜索生成的节点是: N(BFS) = b + b^2 + .... + b^d + ( b^(d+1) - b ) 其中b是分支因子,d是最浅节点的深度 . 但它不应该只是 b + b^2 + .... + b^d ?因为那,根据我是不 . 节点直到目标的深度 . 那么为什么那里 + ( b^(d+1) - b ) ? -
12 votesanswersviews
在有向图上的广度优先搜索期间的边缘分类
在有向图上的广度优先搜索时,我很难找到正确分类边的方法 . 在广度优先或深度优先搜索期间,您可以对满足4个类的边进行分类: 树 返回 CROSS FORWARD Skiena [1]给出了一个实现 . 如果沿着从v1到v2的边缘移动,这里是一种在Java中的DFS期间返回类的方法,以供参考 . 父映射返回当前搜索的父顶点,以及 timeOf() 方法,即发现顶点的时间 . if... -
1 votesanswersviews
在图中查找特定边
我有一个无向图,它有一些节点和边 . 每个节点都具有一定的颜色,每个边缘都是某种类型,由它连接到的节点的颜色决定: 连接红色和蓝色节点的边缘为红蓝色 . 由于图表是无向的: red-blue == blue-red . 我的任务是编写能够找到所有“孤立”边缘的算法 . 当原始边缘和与原始边缘相同类型的下一个边缘之间至少有2个边缘距离时,边缘被隔离 . 最好的方法是什么?最有可能的是它... -
23 votesanswersviews
什么是广度优先搜索有用?
通常当我由于空间复杂度较低时总是使用深度优先搜索 . 我老实说从来没有见过需要广度优先搜索的情况,尽管我的经验非常有限 . 什么时候使用广度优先搜索是有意义的? UPDATE :我想我的回答here显示了我仍然很想知道的情况,为什么它在这种情况下很有用 . -
0 votesanswersviews
在邻接矩阵上应用广度和深度优先搜索?
我给了这个邻接矩阵,我必须从文本文件中读取,并且应该返回读取宽度优先和深度优先的结果 . 我知道广度优先使用FIFO队列,深度优先使用LIFO堆栈 . 当我有图表时,我可以手动获取这些搜索 . 我只是不确定如何在计算机上进行此操作,并在C上使用矩阵 . 我很感激如何解决这个问题的指导 . 我有一些问题: 我是否将矩阵从文本文件保存到我的程序中作为常规矩阵? 读完文本文件以显示搜索结果后该怎... -
1 votesanswersviews
Java - 广度优先搜索航班的多图
我有一个图表,城市作为节点,一个类作为边缘 . 每个航班都有出发时间,到达时间,航班号和航班运营的一系列天数 . 多个边可以连接每对节点,使图形成为多图 . 我需要回答这个问题: What are the available flights from Place1 to Place2 on a given day, with transfers being possible? 以下两种方法使用深度... -
2 votesanswersviews
在二叉树上进行广度优先搜索的空间复杂度是多少?
这是我的Java解决方案,用于逐级打印二叉树,并进行广度优先搜索(它可以正常工作!!) public void printByLevel() { System.out.print("Elements By Level:"); if(overallRoot!= null) { Queue<IntTreeNode> bfs = new L... -
0 votesanswersviews
Gremlin查询找到k个距离顶点
我试图运行一个gremlin查询来查找给定顶点v的k个距离顶点,并省略直接连接的顶点到v . 我正在使用Gremlin 3.2.6 . 所以,这样的事情,对于k距离(朋友的朋友)不能正常工作 g.V(v).both().as(“x”).repeat(both()).times(k).where(neq("x")).dedup() 上面应该省略“x”中的顶点,但事实并非如此 . ...