我有一个非常简单的寻路任务-一个在8x8网格上玩的棋盘游戏，每个方块要么可以通过，要么不能通过。我正在寻找的是一个算法，它将给我从某个正方形A到正方形B的最佳n条路径(假设有)。
我一直在寻找A*，但据我所知，没有明确的方法来扩展它以找到多个路径。
所以，关键是它给出的路径实际上是最短的n条路径，它不会遗漏任何路径。效率也非常重要。有没有人能建议一个合适的算法，或者给我指明正确的方向？
浏览 0提问于2011-06-05得票数 3
3回答
假设我有一个二维网格。寻路是我的问题中的次要步骤。
我的问题是，假设我在网格的中间有一个单元。我希望能够告诉用户“这些都是您可用的目的地。”
基于单元可以遍历多少个方块，我想向用户展示，“这些是您可以到达的所有方块。”然后通过路径找到用户选择的目的地。
进行第一次搜索以显示可到达的目的地的最佳方式是什么？
根据地形的不同，地形也可以有限制或奖励。
我不知道这叫什么，所以在哪里寻找或谷歌什么的指针将非常感谢。
干杯！:)
/E
浏览 0提问于2011-02-05得票数 3
回答已采纳
3回答
我做了一些关于(“寻路”|“路径规划”)的研究，我发现许多算法基本上都在做同样的事情(找到一条从A点到B点的带有或多或少约束的方法)，我找不到寻路算法和路径规划算法之间的任何区别。
这两种算法之间有真正的区别吗？
浏览 1提问于2011-12-01得票数 4
我正在开发一个个人项目。在这个视频游戏中有一个基于网格的移动、创建和寻路系统。在此之前，我曾使用A*寻路来使某些字符移动到某个已知位置。
但现在我遇到了一个大问题。在我的游戏中有一个角色必须去一个特定的对象，但是这个角色不知道这个物体的精确坐标。最简单的方法是真正知道这些物体的坐标，计算出哪个是最近的，并使用A*路径查找来达到这个点，但是这种方法看起来确实是被操纵的，而且对我所做的游戏的类型来说还不够动态。
因此，我想知道是否有一些路径查找算法可以在某个点(正在使用该算法的字符的位置)附近搜索，比如以径向方式进行搜索，并一直搜索直到它找到正在寻找并返回到该特定对象的路径的对象类型。
浏览 7提问于2016-06-01得票数 0
回答已采纳
缓存(不经意|最佳|感知)算法通常会在其模型中考虑寻道时间。如果没有，有没有考虑到寻道时间的模型的例子，并且在这个模型中有算法分析。
浏览 2提问于2014-06-25得票数 3
诸如A* 100%之类的寻径算法可保证最短路径。但是我们可以手动分析图中给定的路径是否是最短路径吗？ 假设我们有这个加权图Weighted Graph 假设我们的起始节点是节点1，我们想转到节点2。我们采用的路径是节点1 ->节点2。显然，这是最短的路径。如果没有任何计算机，我们如何手动证明或确定这条路径是否是最短路径？
浏览 22提问于2021-10-30得票数 0
7回答
我正在寻找一种寻路算法，用于AI控制2D网格中的实体，需要找到从A到B的路径。它不一定是最短的路径，但需要计算得非常快。网格是静态的(永远不会改变)，一些网格单元被障碍物占据。
我目前使用的是A*，但对我来说它太慢了，因为它总是试图计算最快的路径。主要的性能问题发生在路径不存在时，在这种情况下，A*将尝试探索太多的单元格。
有没有不同的算法可以用来找到比A*更快的路径，如果路径不一定是最短路径的话？
谢谢,
流明
浏览 1提问于2013-03-20得票数 9
回答已采纳
2回答
在许多A* Start寻路教程中，最后的部分总是这样；
保存路径。从目标方块开始向后移动，从每个方块到其父方块，直到到达起始方块。这就是你的道路。
我真的不知道我应该做什么来在我的A* star寻路中实现这一点。我当前使用的方法如下:我保存路径，反转它，再次运行探路器，但我通过检查它们是否在原始路径列表中，如果它们在列表中，添加它们来获得相邻节点。
这种方法的问题是我有时会得到一些奇怪的路径。
浏览 1提问于2011-02-20得票数 0
3回答
我需要一个简单的寻路算法，从A点到B点，A*似乎是一个过火，因为它不重要，我撞到墙壁，没有地形。我想知道是否有一个更简单的方法，可以找到从A点到B点的直接路径(一条直线)。
浏览 0提问于2014-07-16得票数 1
1回答
我正在构建一个在立方体表面播放的。目前，它使用Dijkstra算法进行寻路。尽管对set和priority队列数据结构进行了优化，但它仍然有点太慢。你注意到当蛇吃了一种食物并开始寻找新的食物时的延迟。
我试图让它使用A*，但我找不到一个好的启发式方法。在一个有4个移动方向的平面网格上，我会使用曼哈顿距离。我试过使用3D曼哈顿距离abs(dx) + abs(dy) + abs(dz)，这是有充分理由的:对蛇来说，游戏世界真的是具有不同寻常的环绕属性的。
在代码中，每个正方形都存储在一个grid[15][15] 2D数组中。有6个这样的数组来存储每个人脸。因此，每个正方形都有一个(arrayX,
浏览 2提问于2012-12-07得票数 6
回答已采纳
2回答
如何找到两个抽象节点之间的路径
、、、、
我想测试“小世界”或“六度分离”假设，即任何人都可以通过6个共同的朋友到达另一个人的理论。(即朋友的朋友)
示例节点数据(JSON)：
{
"name": "John Smith",
"friends": [
"Foo Bar",
"John Doe"
]
}
将会有成百上千个这样的对象，每个对象都相互链接。我想找出他们之间的最短路径。像那些在游戏中发现的寻路算法是否适合于这样的抽象概念(即:在2D或3D世界中无法表示的概念)，或者是否有更优雅的解决方案？
我
浏览 0提问于2015-10-01得票数 1
1回答
一种将大区域分割为凸多边形的算法
、、、、
我正在将A*寻路算法实现到一个基于网格的引擎中，但我想在多边形区域中创建节点，而不仅仅是使用网格点。
在这个区域会有障碍物，不应该被移动。
我在想，有没有什么算法可以把一个有障碍物的较大区域分割成一个具有尽可能少的连通凸多边形的图？
浏览 15提问于2016-08-17得票数 2
回答已采纳
我在许多书和论文中读到过，考虑到磁盘性能，平均寻道时间大约是完整寻道时间的三分之一，但没有人真正对此提供任何解释。这是从哪里来的？
浏览 3提问于2012-03-23得票数 7
回答已采纳
3回答
我正在尝试使用A*寻路算法实现第二条，最好是第n条最短路径。我已经实现了最短路径：
while(open.length > 0) {
max = worldSize;
min = -1;
for(i in open) {
if(open[i].f < max) {
max = open[i].f;
min = i;
}
}
node = open.splice(min, 1)[0];
if(node.value === nodeEnd.value) {
浏览 0提问于2014-05-13得票数 0
众所周知，A星算法是完全的。然而，我发现搜索web的所有实现似乎只返回第一个(最佳)解决方案。
例如，这个实现：
由于算法总是以最小f值扩展节点，而且当第一个节点是解决方案时，实现似乎停止了，那么如何调整上述代码，从而输出所有(或第一个n)导致目标的路径，而不考虑重复的操作(即一次又一次包含相同操作的路径)？
浏览 2提问于2013-01-30得票数 1
1回答
我正在尝试实现一个*寻路算法。我刚接触iphone开发，尤其是游戏方面。我想问一下，我有一个从json文件读取的平铺映射数组m。在NSArray中获取平铺地图的所有值。现在我想在上面实现一个*寻路算法。我是否必须自己创建A*寻路算法，并将输入作为NSArray，或者我们也有它的任何教程。我已经尝试了互联网，但得到了有关tmx文件的教程。有没有人可以给我发一些很好的教程或者示例代码，或者至少给我指引一个正确的方向。你们真是太好了。谢谢。
浏览 2提问于2012-03-01得票数 0
1回答
简单寻路
、、、、
我正在尝试按照 awesome介绍A*寻路算法。然而，由于某些原因，我的的JS实现倾向于90度路径：，尽管本文中的示例表现不同。也许从frontier数组中弹出/移出next节点应该有一些条件？我想不出如何让它的行为与python示例一样。
浏览 1提问于2018-01-22得票数 1
6回答
我的任务是(coursework @ university)实现一种形式的寻路。现在，在规范中，我可以只实现暴力，因为搜索的节点数量是有限制的(开始，中间两个，结束)，但我想重用这段代码并实现。
我在维基百科上看过这个伪版，一个朋友也给我写了一些，但它完全没有意义。算法看起来很简单，对我来说理解它不是问题，但我就是无法想象实现这种事情的代码。
有什么建议/建议吗？
对一些混淆进行编辑：
是的，有目标节点和源节点。
我希望在一般情况下实现Dijkstra，而不是“只有两个中间停顿”的情况，因为我想在之后再次使用代码。否则，我只会写一个暴力实现。
我遇到一点麻烦的具体问题是存储次优的半成形路径，以
浏览 0提问于2010-05-25得票数 5
回答已采纳
2回答
我现在已经编写了各种图搜索(A*，DFS，BFS等)。算法重复了很多次。每次，唯一真正的区别是我正在搜索的实际搜索状态，以及如何从现有状态生成新状态。
我现在面临着另一个搜索繁重的项目，希望避免再次编写和调试通用搜索算法。如果我可以定义一个搜索状态类，包括生成连续状态的信息，启发式成本等，并将其插入到某种现有的搜索框架中，就可以为我完成所有繁重的任务，那就太好了。我知道算法并不是特别难编码，但总是有足够的技巧让它变得令人讨厌。
真的存在这样的东西吗？我什么也找不到。
浏览 0提问于2010-12-02得票数 4
回答已采纳
从我到目前为止所读到的。在找到到达目标的最短路径方面，似乎更快，因为Dijkstra的算法在遍历图形时必须放松所有节点。是什么让Dijkstra的算法比Best First Search更好？
浏览 1提问于2012-04-30得票数 13
回答已采纳
我目前正在研究非负边权图中的最短路径问题。
我知道Dijkstra算法可以给出单源最短路径问题的解决方案，也就是可以找到从一个节点到所有其他节点的最短路径，但是我还没有找到算法，可以给我一个先验的更简单的问题:找到两个节点之间的最短路径。
直觉上，我认为可以找到例子，表明“简单”问题并不比单源最短路径问题更简单，但我正在寻找参考资料，在简单的图(即有几个节点)上显示这种矛盾(先验)。
浏览 4提问于2022-05-11得票数 2
我正在研究一个A*算法。这是寻路方法的代码。作为参考，这是我正在使用的板：每种颜色的瓷砖代表不同的启发式数值。由于某些未知的原因，它每次都会找到一条路径，只是并不总是正确的路径。以下是寻路方法的代码。如果任何人需要任何澄清，我很乐意提供。
public List<Point> findPath(Point start, Point end) {
//declarations and instantiations
List<PathState> closedList = new ArrayList<PathState>(); //the
浏览 0提问于2014-12-10得票数 0
1回答
图算法问题给你。
我有一个图表，用来表示一个道路网络。因此，在它的循环(一个回旋将是一个微不足道的)。还有一些边缘是双向的，有些是单向的(单向街道).边是按长度加权的。
假设我有两个节点，并且已经计算了它们之间的最短路径。我想要做的是找到连接两个节点的所有其他路径，它们都比某个距离还要短。
下面是ascii技术中的一个例子，其中我用字母标记了边，用数字标记了节点。
F
5----6
E / \ G
3--------4
/ D \
B / \ C
1--------------2
浏览 3提问于2013-09-07得票数 0
回答已采纳
1回答
我正在尝试找出电梯算法相对于最短寻道时间优先(SSF)算法的一些优势。
维基百科说：“然而，电梯算法并不总是比最短搜索优先算法更好，后者更接近最优，但当新请求在现有请求之前不断得到服务时，可能会导致响应时间的巨大差异，甚至导致饥饿。
反饥饿技术可以应用于最短搜索时间优先算法，以保证最佳的响应时间。“来源：
我不知道如何破译这些信息。所以我的问题是：
与最短寻道时间优先(SSF)算法相比，电梯算法有哪些优势？
浏览 4提问于2015-03-15得票数 2
嗨，我想知道按顺序插入元素的最好容器是什么？我认为映射是不必要的，因为我只是访问前面的元素，弹出它，然后插入更多的元素(我正在实现一个带权重的寻路算法(Dijkstra) )。
我自己可能已经使用了一个列表并按顺序插入，但无法一分为二(因为您从前面或后面开始访问)将阻碍性能。
浏览 0提问于2011-03-13得票数 3
回答已采纳
5回答
使用A*并仍然避免冲突？
、、、、
我正在设计一个塔防御游戏，为此，我使用A*寻路算法从我的产卵区域到达我的目的地。
这里的问题是所有的单元都堆叠在一起，这在视觉上看起来并不好。如果没有足够的空间，有没有办法让它们以某种方式组合在一起，并传播得更多？
该算法的工作原理是，所有单元一次移动一个平铺。
浏览 0提问于2011-04-14得票数 5
回答已采纳
2回答
我想知道是否有一种算法可以在图中找到最短路径。
假设我有一个图，从一个顶点到另一个顶点有一对路径。这些路径中的两条或更多条具有相同的成本。如何标记、查找这些顶点之间的所有最短路径？据我所知，Dijkstra或Bellman-Ford算法会找到最短路径，但他们只“选择”一条。
浏览 1提问于2010-08-09得票数 1
回答已采纳
1回答
我有一个非常大的向量，它存储了100000个不同的值，范围从0到50000。它们表示硬盘上的柱面，我想根据用于磁盘调度的三种不同算法对这个向量进行排序。到目前为止，我从一个文件中读取了这100000个值，将它们存储到一个向量中，然后根据所需的算法(FCFS，SCAN，SSTF)对它们进行排序。.The的问题是，它花费的时间太长了，因为我用的是最没有创意的方法：
public static Vector<Integer> sortSSTF(Vector<Integer> array){
Vector<Integer> positions = new Ve
浏览 4提问于2013-05-16得票数 1
回答已采纳
我有一个由节点和边的权重组成的网络。我都认识他们。我得到了一个“包”，我知道它目前正在节点A上从B到C。如何获得当前可以遍历的最小路径(下一个和以前的节点)？
浏览 3提问于2020-06-04得票数 0
回答已采纳
3回答
所以基本上我编写了一个A*探路器，它可以找到通过障碍物的路径，并对角地移动。我基本上将中的伪代码实现为真实代码，并使用二进制堆方法在openlist中添加和删除条目。
使用二进制堆带来了显著的性能提升，比我以前使用的插入排序算法快了大约500倍。
问题是，它仍然平均需要大约150万纳秒，大约是一秒的.0015。
所以问题是，我的计划是做一个塔防御游戏，每次我在地图上添加一个塔时，每个暴徒的寻路都需要更新。如果我在地图上最多有50个左右的暴徒，这意味着更新整个暴徒的所有路径大约需要.0015 *50= .075秒。那么我该怎么做呢？我是否需要找到一种更好的算法来对打开列表进行排序，或者以某种方式
浏览 0提问于2013-02-27得票数 3
回答已采纳
3回答
基于C#的图形导航
、、、、
我有点困惑，想想出一个很好的算法来浏览下面的图表。
如果用户选择“表21”作为起点，我需要能够从该起始表获得任何其他表的路径。
示例:如果用户选择“表21”作为开始，然后从“表8”中添加值，则需要创建以下路径"Table 21 -> Table 12 -> Table 9 -> Table 6 -> Table 8<code>E 210</code>“，表之间的所有权重都是相同的。
我似乎忘记了处理有向图的技巧，也想不出一个好的算法。我不是在要求解决问题，而是朝正确的方向前进。
谢谢!
浏览 5提问于2009-05-01得票数 3
回答已采纳
2回答
贾尼克斯特拉最短路径算法
、、、、
我正在学习different的代码，我已经准备了下面的代码，所依据的是与different略有不同的想法。现在，在许多网站上，我看到了使用提取min和布尔数组访问的边缘。我没有用过，我的答案也是正确的。是否有任何测试用例或场景让我的algo无法工作。
import java.util.*;
class ShortestPath2 {
static int Ar[][];
static int dist[];
static int nodes;
public static void djikstra(int sou
浏览 1提问于2016-09-30得票数 0
回答已采纳
5回答
我正在尝试实现吃豆人。它工作得很好，但到目前为止，幽灵没有使用任何寻路，而是在每个路径交叉点上随机决定采取哪条路径。所以你可以想象，吃豆人赢得这场比赛并不是真的困难;)
我在《吃豆人》中读了一点关于路径查找算法的文章，所以我找到了一个非常好的答案：
答案是指
这一切都很好，但在我的吃豆人实现中，有两个吃豆人，由两个不同的玩家扮演。所以我想知道如何调整寻路算法，这样幽灵就不会总是追逐一个玩家。
有没有想过如何修改算法，让幽灵对两个玩家或多或少都是公平的？
浏览 11提问于2010-06-23得票数 3
回答已采纳
2回答
隧道路线图
、、、
给定多个城市之间的路线图，其中两个城市之间的道路包含隧道，您的目标是找到起始城市和所有其他城市之间可能的最短路径，使得每条路径至少包含一个隧道。(问题并不总是有解决方案)。假设道路的成本是给定的。输入-从一个文件，输出-到一个文件，包含起始城市和到其他城市的路径。
现在我试着用Dijkstra的算法来做这件事，它解决了我的大部分问题，除了隧道是强制的部分。有人能帮我吗？这是我的代码。提前感谢！
文件输入：
10
1 2 10
1 4 5
2 3 1
2 4 3
3 5 6
4 2 2
4 3 9
4 5 2
5 1 7
5 3 4
#include <stdio.h>
#defi
浏览 4提问于2014-01-11得票数 0
1回答
我知道这里有大约100个图形算法。记忆图中哪一个是可用的？有没有像help list algorithms这样的命令可以告诉我可以使用什么？
浏览 1提问于2022-09-09得票数 0
回答已采纳
1回答
在询问了一些关于最短路径算法()的一般性建议，然后询问了更具体的实现()之后，我决定使用JUNG库()。
我现在的目标是从A点到B点的最短路径，方法是使用点列表中的任意组合点(大小~1000)，其中每个点直接连接到x距离内的所有点。
为此，我需要建立一个树图。我相信这是树映射实现的列表：
对吗？现在，所有这些实现都局限于稀疏树映射，但是我必须创建一个相当密集的树映射。
那么，我应该用什么树图来完成我的目标呢？
浏览 0提问于2011-03-09得票数 2
回答已采纳
2回答
使用数组的Dijkstra算法的时间复杂度为O(V^2)，如果采用优先级队列，则可以进一步将复杂度提高到O(E log V)。但是它的空间复杂性如何呢？在两种情况下都是O(V)吗？
浏览 10提问于2018-06-14得票数 4
这是我的Dijkstra的实现。它正在传递pytest input.n.txt文件中的所有情况，但是当我提交评分软件(不提供测试或任何输出)时，我得到的结果无效。
这是我的解决方案(通过所有提供的测试用例，但不是隐藏的)。
# Uses python3
import queue
import sys
from math import inf
def dijkstra(adj, cost, s, t):
seen = set([s])
dist = [inf] * len(adj)
dist[s] = 0
prev = [None] * le
浏览 2提问于2021-08-30得票数 0
回答已采纳
我们正在寻找一个SilverLight库，它将允许我们创建用链接节点来描述关系的图。如果存在的话，我希望有人能给我一个建议。
我正在寻找的一个例子是；，它是一个java库。
谢谢
浏览 1提问于2010-11-10得票数 0
回答已采纳
我需要一些帮助在Mysql和Php中实现最短路径问题。据我所知，BFS算法是在无向图和无权图中找到这些路径的最佳方法。不过，我必须得到从一个顶点到另一个顶点的所有最短路径，这就变得更复杂了。我已经找到了一个Java实现，但它太复杂了，我无法将其转换为Sql。
所以，第一个问题是:我应该在哪里进行计算？Mysql还是Php？哪里会更快？
而且，BFS是最好的选择吗？是否有更容易实现的解决方案？如果没有，是否有人可以很容易地使用我的代码作为参考呢？
谢谢!
浏览 3提问于2015-11-06得票数 1
2回答
我试着用图论写一个抽象的算法。
给出了一个无向无权图G=(V，E)，两个顶点: m，n∈V和一个特定边e∈E.我想检查边e是否是m和n之间所有最短路径的一部分.
My算法：
做BFS扫描从m到到达n.o(V+E)
int <-- dn \ O(1)
布尔ret \ O(1)
从G. O(1)中取出边缘e
从m到n\ O(V+E)进行BFS扫描
- if d[n] = ∞, ret <-- true
- if d[n] == temp, ret <-- false
- if d[n] > temp, ret <-- true
将边
浏览 3提问于2014-06-11得票数 0
回答已采纳
1回答
我已经检查过其他人的解决方案，但我不知道他们是如何解决这个问题的。
如果有人能帮我建议我应该从哪里开始学习来理解这些问题，那就太好了。
浏览 4提问于2016-06-20得票数 1
回答已采纳
1回答
在雾计算的上下文中，计算卸载决策决定在哪里卸载-在云上还是在雾上或在本地执行。同时，任务调度还决定了在雾上或云上执行任务的位置。那么这两者的区别是什么呢？
浏览 73提问于2020-03-17得票数 0
1回答
我正在做一个在图中寻找最短路径的项目，并且我必须能够指定开始和结束顶点。我已经使用Boost完成了大部分工作，但我还剩下一个问题。如何指定起始顶点？这是我的代码。如果您能为我指明正确的方向，我将不胜感激。有问题的那一行是所有**的那一行，靠近底部。
#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#includ
浏览 2提问于2013-12-16得票数 0
1回答
假设我有一系列的关系，例如
信任一些朋友而不是另一些朋友的朋友
需要在因特网上定位对等点的IPv6路由器
一个PGP信任Web，需要两个人找到彼此的信任级别
我感兴趣的不仅仅是确定最短路径，还要确定每条路径的成本(通过添加任意权重)、每条路径的节点以及其他通常用于此通用需要的信息。
有什么办法来满足这一需要？理想情况下，我可以在手机或计算机上本地运行，并以O(N)的速度或更好的速度搜索大图。
浏览 0提问于2013-09-22得票数 1
2回答
我目前正在写一个基本的平台游戏，我的想法是学习2D游戏开发的基本模式。其中之一是令人惊叹的A Star寻路。在阅读和研究了几篇文章(其中两篇是最好的：和)、教程和源代码之后，我使用曼哈顿方法做了一个简单的A星寻路，这种方法对我的个人学习过程很有效。
下一步，也是合乎逻辑的一步，是在平台方案上做同样的事情，全国人民代表大会必须跳或爬梯子才能达到目标目标。我找到了这些截图和，它们完美地展示了我想要做的事情。
目前我还没有找到任何资源来解释实现它的方法。有人能给我一个我可以工作的起点吗？
提前感谢
浏览 1提问于2012-09-01得票数 1
我有进程，它经常更新单列。最后，在执行压缩之前，我的列的值存储在多个SSTables中。
Memtable被排序，并被同步刷新到磁盘，在这种情况下，我也假设磁盘上的SSTables是排序的。基于此，Cassandra需要查看single SSTable (使用正布隆过滤器)来查找我的列的最新值，对吗？
我有点困惑，因为我在某处读到，频繁更改单列的值会导致无法执行read，但我的理解是，只有压缩工作才会有更多的工作要做，读取应该不受影响。
浏览 2提问于2012-08-07得票数 1
回答已采纳
我读到了有关图算法的文章，我发现了这两种算法：
Dijkstra算法和BFS算法在寻找节点间最短路径时有什么区别？
我找了很多关于这件事，但没有得到满意的答案！
在图中查找最短路径的BFS规则如下：
我们发现所有连通的顶点，
将它们添加到队列中，并且
存储从源u到顶点v的距离(重量/长度)。
更新的路径从源u到那个顶点v的最短距离，我们有它！
这正是我们在Dijkstra算法中所做的事情！
那么，，为什么这些算法的时间复杂度如此不同？
如果有人能用伪代码来解释它，我会非常感激的！
我知道我错过了什么！请帮帮我！
浏览 8提问于2014-08-22得票数 65
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
