A*算法的正确表述
我正在研究A*寻路算法的定义，不同的地方似乎有些不同。 区别在于当经过节点的后继节点时，在发现后继节点已在关闭列表中时所执行的操作。 一种方法（由维基百科和此文章建议）：如果后继节点在关闭列表中，则忽略它 另一种方法（例如在这里和这里建议）：如果后继节点在关闭列表中，则检查其成本。 如果成本...
3D搜索使用A * JPS
我如何将Jump Point Search推广到3D搜索空间？ 到目前为止，我已经为一个3D立方体定义了每个三维移动（直线（0,0,1），一阶对角线（0,1,1）和二阶（1,1,1））的修剪规则。 我最关心的是论文中定义的最优转折点。我无法确定它们是如何推导出来的，因此也不知道如何在三维空...
以最少步数同时解决所有4x4迷宫
我遇到了一个非常有趣的问题，我们有一个4x4的迷宫和一个机器人在里面试图到达目标。问题是，你必须找到一系列预定义的命令序列，这些命令序列将始终导致机器人到达目标。 假设我们有一个像这样的迷宫：x . . . . # # . . # # . . . . g 这个特定的迷宫可以用例如命令序列DD...
地图导航项目，道路数据通常如何存储/表示？
导航系统，如Garmin和TomTom，一直让我很着迷。我想实现小型地图/导航应用程序，以尝试各种路径算法并扩展我的知识。 这是一个两部分的问题： 1.) 地图数据是如何存储的？- 当你有一条道路网络时，这些数据通常如何存储？保留哪些数据以便之后能够生成地图？每个道路是否被存储为一系列改变...
PacMan：主要使用哪些启发式算法？
除了A*、BFS、DFS等算法之外，还有哪些好的路径寻找算法/启发式算法在Pacman中广泛使用？如果有多个水果要让Pacman寻找，我不认为我提到的那些算法会起作用。 我需要一些好的路径寻找算法，可以使PacMan以最少的步数完成迷宫。我尝试搜索指南，但到目前为止没有运气。A*算法与曼哈顿...
无限制地随机移动物体而不发生碰撞
我有一个应用程序，需要在屏幕上以随机方式移动许多对象，并且它们不能相互碰撞。我正在寻找一种算法，允许我生成不会产生碰撞的路径，并可以无限期地继续移动（即：对象继续在程序中移动，直到用户驱动的事件将其从程序中删除）。 我不是游戏程序员，但我认为这似乎是一个AI问题，你们可能闭着眼睛就能解决。根...
什么算法可以计算在地图上从点A到点B的方向？
地图提供商（比如谷歌或雅虎地图）是如何建议路线的呢？ 它们可能有某种形式的真实世界数据，肯定包括距离，但也可能包括行驶速度、人行道存在情况、火车时间表等等。但假设数据以更简单的格式存在，例如一个非常大的有向图，边缘权重反映距离。我想能够快速计算从任意一点到另一点的方向。有时这些点会很近（在同...
IDA*算法与A*算法相比有何优劣之处？
我不理解IDA*如何节省内存空间。 根据我的理解，IDA*是使用迭代加深的A*算法。 A*与IDA*在内存使用量上有什么区别。 难道IDA*的最后一次迭代行为不会像A*那样并且使用相同数量的内存吗？当我追踪IDA*时，我意识到它还必须记住所有低于f(n)阈值的节点的优先级队列。 我了解I...
查找具有最大最小权重的路径
我正在尝试设计一种算法，以寻找有向图上的路径。这不是传统的路径，我找不到已经完成此任务的任何参考资料。 我希望找到最小权重最大的路径。 例如，如果有两条路径，它们的权重分别为10->1->10和2->2->2，则第二条路径被认为比第一条更好，因为最小权重（2）大于第一条路径的最小权重（1）...
A*是最优秀的路径规划算法吗？
一般认为A*算法是解决路径规划问题最好的算法。 但是否存在某些情况下A*算法不是寻找解决方案最好的算法呢？ 与BFS、DFS、UCS等算法相比，A*算法的效率如何？