如何使用BFS重建二维迷宫的路径以找到最短路径

文章/答案/技术大牛

发布

1回答

c++

我已经在C++中实现了呼吸优先搜索算法，如下所示，我知道该算法是有效的，并找到从给定房间到其中一个出口的最短路径。但由于算法的性质，它找不到实际路径，而是从开始节点到结束节点所需的步数。我正在尝试用这个算法重建找到的最短路径。我在一个与我的迷宫大小相同的矩阵中存储了每个访问节点的父节点

浏览 17提问于2021-07-31得票数 1

1回答

如何只使用一次bfs来求解该算法？

algorithm、breadth-first-search

问题出在uva1599，请访问迷宫由n个房间组成，由m条路径相连。每条路径被着色为某种颜色ci。找到从1号房间到n号房间的理想路径。如果该路径的颜色序列是最短路径中按字典排序最小的，则该路径是理想路径。(2<=n<=100000，1<=m<=200000，1<=c<=10^9) 我可以从最后一个房间

浏览 3提问于2017-03-26得票数 0

1回答

迷宫解算的最佳算法？

algorithm、graph、graph-algorithm、path-finding、maze

最近我做了一个项目，用不同的路径搜索算法来解决一个给定的迷宫。为此，我导入了一个黑白迷宫图像，并使每个节点成为一个节点。我尝试使用DFS、BFS、Dijkstra和A*来解决这个问题，但注意到DFS给了我最短的运行时间。那么，我的问题是，在一个完美的迷宫(只有一个解决方案的迷宫)上使用更先进的算法(比如Dijkstra或A* )

浏览 3提问于2020-04-14得票数 3

回答已采纳

1回答

获取最短路径中的第一步- 2d数组- java

java、arrays

我有一个二维数组(假设如下所示)：####.#####..#.## 我已经能够计算出从迷宫中的一点到另一点的最短路径然而，我只想得到计算出的最短路径的第一步，而不是这样做。我可以轻松地在a*、d

浏览 15提问于2016-09-26得票数 0

1回答

在没有先验知识的情况下在迷宫中寻找实体的算法

algorithm、breadth-first-search、a-star、maze

我有一个像加权迷宫一样的网格，我需要在没有任何关于迷宫的先验知识的情况下找到通向实体的最短路径。像A* expect priot knowledge这样的算法在环顾四周时会“跳来跳去”，但当我有一个机器人的时候，这是不可能的。我的第一个想法是最初使用BFS探索整个迷宫，然后在探索的迷宫

浏览 0提问于2018-12-10得票数 3

3回答

迷宫勘探BFS和DFS可以使用哪种程序？

algorithm、time-complexity、depth-first-search、breadth-first-search、maze

我知道我们可以用DFS进行迷宫探索。但我认为我们也可以使用BFS进行迷宫探索。我在这里有点困惑，因为我读过的大多数书和文章都是用DFS解决这个问题的。我认为，与BFS相比，DFS的最佳情况时间复杂度将更好。但是平均和最坏的情况下的时间复杂度对于BFS和DFS都是一样的，这就是为什么我们更喜欢DFS而不是BFS。我是对的，还是我有一些误解

浏览 2提问于2013-11-25得票数 6

回答已采纳

2回答

遍历迷宫和深度优先搜索

c++、c

我在我的程序中遇到一个问题。if( flag==false ){ maze[x][y]=0; }} 链接是我写的程序，但我不知道如何找到最短路径。你能给我一些关于如何使用堆栈的建议吗，我只使用递归。我已经看过关于它的wiki，但仍然不明白如何使用堆栈。(例如如何<

浏览 2提问于2012-03-10得票数 1

回答已采纳

4回答

找出两点之间的最小步数？

java、vb.net、algorithm、graph-algorithm

我有一个网格，网格有两个“材料”- 我需要返回对一个对象需要执行的最小操作量。

浏览 3提问于2015-01-23得票数 5

回答已采纳

4回答

最短路径数

python、algorithm、chess

以下是问题所在：然后，我们被要求为骑士确定从棋盘左下正方形到棋盘右上正方形的最短路径(骑士可以在一个轴上移动2个空间，然后在另一个轴上移动1个空间)。我现在的想法是：使用二维数组存储所有可能的移动，在二维数组上执行广度优先搜索(BFS)以

浏览 2提问于2016-09-21得票数 0

1回答

在迷宫上打印PacMan步骤，宽度优先搜索- Java

java、breadth-first-search、maze

我正在尝试创建某种没有鬼的PacMan模拟，其中它用6x10的矩阵表示。我实现了BFS的一个变体，在被搜索的两个节点之间递归调用算法，这给了我满意的结果。然而，我真正想要做的是在每次PacMan运动之后打印迷宫的状态，其中PacMan用"2“表示，盒子用"3”表示，墙壁用"1“表示，自由之路用"0”表示。下面是一个开始的迷宫： 2 0 0 3 1

浏览 7提问于2013-05-22得票数 1

回答已采纳

1回答

广度优先搜索计数器示例

graph-theory

声明：我知道，当涉及到从BFS派生的最短路径树时，顺序很重要，假设邻接表中顶点的顺序就是<em

浏览 5提问于2018-11-20得票数 0

1回答

如何在无向图中找到最短路径和最长路径？

algorithm、graph、depth-first-search、breadth-first-search、longest-path

我有一个关于如何在具有简单边的无向图中找到最短路径和最长路径的一般问题，其中边没有权重。我们需要使用DFS算法来寻找图中的最长路径，而我们需要使用BFS算法来寻找图中的最短路径，这是一个正确的结论吗？我知道当我们使用BFS时，我们逐层访问节点，我们可以使用它

浏览 42提问于2021-03-26得票数 0

1回答

3D迷宫中的最短路径

recursion、3d、shortest-path、maze

我正在试着写一个程序，用递归在3D迷宫中找到最短路径。请注意，我希望保留递归方法。s XX XXe X 一种是从s到e。X是一个障碍，也是解决问题的途径。

浏览 17提问于2016-09-05得票数 2

1回答

关于谦卑的HilbertMaze任务

algorithm、hilbert-curve

如何从谦卑中着手以下任务：我可以通过使用BFS生成迷宫和搜索最短路径来找到最短路径，但是由于最坏的时间复杂度预计为O(N)，我不认为这是正确的方法。BFS的时间复杂度为O(x=0)，其中V为顶点数，E为边数。例如，如果N= 3，我们有一个大小为17x17的网格，很明显，我们不能在三个步骤中找到路径。因此，要么

浏览 1提问于2016-08-04得票数 1

回答已采纳

1回答

非加权二维阵列中的最短路径如何显示BFS期间所采取的步骤/方向

java、multidimensional-array、breadth-first-search、shortest-path

在这个算法中，我要做的是，给定一个二维数组，从给定的起点(S)和给定的端点(D)找到最短路径--记住数组(*)中的一些元素被认为是障碍。通常，我会执行典型的BFS并返回最短路径的距离，但是会有一些额外的皱纹。我需要用基数(北、南、东或西)替换一个遍历元素来显示最短路径。(分别缩写为n，s，e，w)到目的地<em

浏览 3提问于2020-10-02得票数 1

1回答

如何从拍摄到的迷宫图像中生成图形

java、data-structures、robotics

我正在开发一种用于最短路径查找的机器人。该系统由移动机器人、轨迹规划器、运动控制器、视觉传感器、ZigBee无线通信装置和迷宫地形组成。摄像机用于在迷宫中捕捉移动机器人的图像。开发了基于颜色标记识别的图像处理和分析算法，确定了机器人的位置和方向，我正在用java开发其软件部分。我的目标是从捕获的image.And中创建一个连接节点的图，应用最短路径算法(BFS</em

浏览 1提问于2015-10-22得票数 2

回答已采纳

1回答

吃豆人:一条吃掉所有点子的捷径

artificial-intelligence、path-finding、traveling-salesman、pacman

我正在尝试为吃豆人问题找到一个解决方案，即找到一条吃掉大迷宫中所有点的短路径(不是最短的，但很好的)。我见过很多人谈论TSP，Dijsktra，BFS，A*。我不认为这是一个TSP，因为我不需要回到我开始的地方，如果我愿意，我可以重复node。我不认为Dijsktra，BFS和A*会有帮助，因为我不是在寻找最短路径，即使是这样，它也不会在合理的时

浏览 5提问于2012-10-14得票数 2

回答已采纳

1回答

BFS或DFS是Ms Pacman的有效搜索算法吗

java、artificial-intelligence、depth-first-search、breadth-first-search、pacman

我认为从一些基本的搜索开始，比如BFS或DFS，这是一个好主意。我刚刚实现了一个BFS，但是当我运行我的代码时，pacman女士撞到了墙上。我想知道，我的BFS代码有没有什么可以改进的地方，或者仅仅是不够呢？public MOVE BFS(Game game){ EnumMap<Constants.GHOST,MOVE> ghostMove = new EnumMap<>(Constants.GHOST.clas

浏览 50提问于2021-11-06得票数 1

3回答

何时使用DFS和BFS

java、algorithm、graph

以下是Facebook黑客杯中的图形搜索问题。我所使用的方法与社论中描述的方法相同，但我使用的是DFS，而不是BFS，而且我对某些情况的回答是错误的。 DFS是如何发挥作用的--为什么DFS在BFS工作

浏览 1提问于2015-01-17得票数 1

1回答

给定特定步数时，从起始节点到结束节点的最大路径

java、path、dijkstra

目前，我已经实现了Dijkstra的最短路径算法。给定一个迷宫，最短路径算法提供了以最少的步数从入口到出口退出迷宫的最快方法。然而，我想找到一种方法，给定特定的n步，迷宫中可能的最大路径是什么？(您可以到达死胡同并返回，这将被算作额外的步骤)

浏览 31提问于2019-04-27得票数 0

点击加载更多