六边形网格中的 A* 寻路
谁能告诉我一个简单的例子，它实现了A*寻路算法在 六角形 网格上(在 JS 中).我已经让它在方形网格上工作，但是我所有尝试让它在六边形网格上工作都失败了. 这是我的网格的样子: 我使用相同的技术来绘制网格并生成坐标，如下所示 主题. 这是网格坐标数据以及开始、结束坐标: [0, 0] , [0, 1], [0, 2],[1, 0], [1, 1], [1, 2], [1,
..
a-star相关内容
IDA* 与 A* 算法的重点是什么
我不明白 IDA* 如何节省内存空间.从我理解的IDA* 是A* 迭代深化. A* 和 IDA* 使用的内存量有什么区别. IDA* 的最后一次迭代不会与 A* 的行为完全一样并使用相同数量的内存.当我跟踪 IDA* 时，我意识到它还必须记住低于 f(n) 阈值的节点的优先级队列. 我知道 ID-Depth 优先搜索有助于深度优先搜索，因为它允许它像搜索一样进行广度优先搜索，而不
..
AStar - 名称解释
我正在寻找为什么 AStar/A* 算法被称为 AStar 的解释.所有相似的(最短路径问题)算法通常都以其开发者的名字命名，那么 AStar 代表什么? 解决方案 有称为 A1 和 A2 的算法.后来证明A2是最优的，实际上也是最好的算法，所以他给它取了个名字A*，象征性地包含了所有可能的版本号. 来源: 1964 年，Nils Nilsson 发明了一种基于启发式的方法来提
..
您如何使用 A-Star 或 Dijkstra 算法解决 15 难题?
我在我的一本 AI 书籍中读到，在模拟或游戏中用于寻路的流行算法(A-Star、Dijkstra)也用于解决众所周知的“15 拼图". 谁能给我一些关于如何将 15 拼图简化为节点和边图以便我可以应用其中一种算法的指示? 如果我将图中的每个节点都视为一个游戏状态，那这棵树会不会变得很大?或者这只是这样做的方式? 解决方案 对于 A-Star 的 15 谜题来说，一个很好的启发式
..
为什么 A* 在内存中的复杂度是指数级的?
维基百科对 A* 复杂性的说明如下(此处链接): 比那个时代更成问题复杂度是 A* 的内存使用量.在最坏的情况，它也必须记住指数数量的节点. 我看不出这是正确的，因为: 假设我们探索节点 A，有后继节点 B、C 和 D.然后我们将 B、C 和 D 添加到开放节点列表中，每个节点都伴随着对 A 的引用，然后我们从开放节点中移动 A到封闭节点. 如果在某个时候我们找到另一条通往
..
在大地图上寻路
我正在创建一个带有 10,000 x 10,000 地图的游戏. 我希望用户能够设置位置并让计算机立即找到最佳路径. 但是，由于地图是 10,000 x 10,000，因此有 100,000,000 个节点，通过 A* 或 Dijkstra 等常规方法找到此路径需要大量内存和长时间. 所以我的问题是:我怎样才能找到最佳路径? 我正在考虑的算法会将世界分成 100 个部分，每个部分有 1,0
..
带有传送器的网格上的 A* 可接受的启发式方法?
假设您有一个 2D 单元格网格，其中一些被墙填充.角色可以从一个方格走一步到与其水平或垂直一步的任何方格，但不能跨墙. 给定一个开始位置和一个结束位置，我们可以通过使用具有可接受启发式的 A* 算法找到从开始位置到结束位置的最短路径.在当前设置中，曼哈顿距离是可以接受的，因为它永远不会高估到目的地的距离. 现在假设除了墙壁之外，世界还有成对的传送器.踏上传送器会立即将角色传送到链接的传
..
最快的跨平台 A* 实现?
有这么多可用的实现，使用小网格的 C++ 执行速度最快(CPU 占用最少、二进制最小)、跨平台(Linux、Mac、Windows、iPhone)A* 实现是什么? 实施 谷歌返回: http://www.heyes-jones.com/astar.html(该网站上的大多数链接都已失效.) http://www.grinninglizard.com/MicroPather(据
..
A* 算法的正确公式化
我在看 A* 寻路算法的定义，似乎在不同的地方定义有点不同. 区别在于在遍历节点的后继节点时执行的操作，并发现后继节点在关闭列表中. 一种方法(由维基百科和这篇文章) 说:如果继任者是在关闭的列表中，忽略它 另一种方法(建议此处 和 这里，例如)说:如果继任者在封闭名单上，检查它的成本.如果它高于当前计算的分数，请从关闭列表中删除该项目以备将来检查. 我很困惑 - 哪种方法是正
..
解决 8 个难题的有效方法是什么?
8 拼图是一个有 9 个位置的方板，由 8 个编号的瓷砖和一个缺口填充.在任何时候，与间隙相邻的瓷砖都可以移动到间隙中，从而创建新的间隙位置.换句话说，间隙可以与相邻的(水平和垂直)瓷砖交换.游戏的目标是从任意配置的瓷砖开始，移动它们以使编号的瓷砖按升序排列，要么围绕棋盘周边运行，要么从左到右排列，左上角为 1-手的位置. 我想知道什么方法可以有效地解决这个问题? 解决方案 我将尝试
..
适用于非常大图的 A* 算法，对缓存快捷方式有什么想法吗?
我正在 OpenStreetMap 地图上编写快递/物流模拟，并意识到如下图所示的基本 A* 算法对于大型地图(如大伦敦)来说不够快. 绿色节点对应的是放在开放集/优先级队列中的节点，由于数量庞大(整个地图大约有 1-2 百万个)，找到图中的路线需要 5 秒左右.不幸的是，每条路线 100 毫秒大约是我的绝对限制. 目前，节点既存储在邻接列表中，也存储在空间 100x100 二维数组中
..
启发式使用 A* 找到具有最高增益的路径
假设我想改变A*中的逻辑，试图找到最有用的路径(即增益最高的路径)而不是找到最短的路径(即成本最低的路径). 就我而言，目标没有固定为唯一的结束节点.一个节点被定义为任何距离起点B的节点. 在普通版本(“寻找最短路径")中，我被要求不要高估成本(即找到小于或等于实际成本的启发式). 在我修改后的版本中(“找到最有用的路径")，边被标记为效用而不是成本，我想最大化最终收益，考虑到通
..
如何使用A*算法找到最好的三条路线
在 A* 中，您得到的结果通常只有一条路径.根据 A*，给定的起点和目的地是否有可能有 3 条推荐路径?所以第二个返回的是第二个最佳路径，第三个是第三个最佳路径.. 我正在考虑以某种方式修改启发式以反映第二和第三条最佳路径..你们怎么看? 更新:我的实现是在 PHP 中，我使用的是封闭集.所以如果有办法做到这一点，请告诉我. 解决方案 如果您的语言支持回溯/生成器/迭代器/协程
..
大地图实现A星(A*)路径算法，性能低
我正在使用这个 A 星 (A*) Pathfinder.java 来计算 &在 Android 地图应用程序中生成我的路线.https://github.com/xSmallDeadGuyx/SimpleAStar/blob/master/Pathfinder.java 地图的尺寸很大，尺寸在8000x8000左右，当我使用A星Pathfinder.java计算地图中从一个点到另一个点的
..
boost 隐式图和 astar_search_no_init
我想实现机器人的路径规划子系统.我将使用 boost 库中的 A*. 我需要隐式图.我必须使用 astar_search_no_init 函数(它写在文档中).不幸的是，我找不到使用 astar_search_no_init 和隐式图的示例. 我发现了“BGL 框架内的 A* 图搜索".作者使用 astar_search 作为隐式图.他试图在访问者的 examine_vertex 方法
..
A* 中的曼哈顿距离
我正在使用 A* 搜索算法并使用曼哈顿距离作为启发式实现 NxN 拼图求解器，但我遇到了一个奇怪的 bug (?). 考虑这些谜题(0 个元素是空格): (初始) 1 0 2 7 5 4 8 6 3 (目标) 1 2 3 4 5 6 7 8 0 从初始状态达到解的最小移动次数是 11.但是，我的求解器在 17 次移动中达到目标. 这就是问题所在——我的
..
A* 算法:封闭列表包含太多元素/太大
我目前正在 JavaScript 中实现 A* 算法.但是，我遇到了一个问题:我的 closedList 似乎太大了.这是输出的屏幕截图: 是什么导致了这个问题?我的启发式计算是错误的吗? Node.prototype.getHeuristic = function(pos0, pos1){//曼哈顿距离var horizontalDistance = Math.abs(pos1.x
..
Astar 可以多次访问节点吗?
我一直在阅读维基百科的 Astar 文章.在他们的实现中，他们检查每个节点是否在 closed 集合中，如果是，则跳过它.如果启发式可以接受但不一致，我们可能需要两次(或多次)重新访问一个节点以提高它的f值，这是否可能??这是相关代码 对于neighbor_nodes(current)中的每个邻居如果封闭集中的邻居//这个if条件困扰着我继续tentative_g_score := g_scor
..
为 A* 算法寻找启发式的一些好方法是什么?
您有一张方形图块的地图，您可以在其中向 8 个方向中的任何一个方向移动.鉴于你有一个名为 cost(tile1, tile2) 的函数，它告诉你从一个相邻的瓷砖移动到另一个的成本，你如何找到一个既可以接受的启发式函数 h(y,goal)并且一致?在给定此设置的情况下，是否可以推广用于查找启发式的方法，还是会根据 cost 函数而有所不同? 解决方案 Amit 的教程是我在 A* 上见过的最
..
最佳优先搜索和 A* 搜索有什么区别?
在我的教科书中，我注意到这两种算法的工作原理几乎完全相同，我试图了解它们之间的主要区别. 教科书使用A*遍历这个例子，就像使用最佳优先搜索一样. 任何帮助将不胜感激. 解决方案 Best-first search 算法基于启发式函数访问下一个状态f(n) = h with最低启发式值(通常称为贪婪).它不考虑通往该特定状态的路径成本.它只关心当前状态的下一个状态具有最低的启发式
..