a-star相关内容

在使用可接受的启发式算法时,A* 是否需要知道最佳解决方案成本?

我已经阅读了一些关于这个主题的 stackoverflows,以及关于 A* 的维基百科,但我仍然有点困惑.我认为这篇文章几乎完全向我解释了它:A* 启发式,高估/低估? 我唯一的困惑是,A* 如何知道最优解?似乎对于可接受的启发式,您可以丢弃超过已知最佳解决方案的路径,因为启发式保证小于或等于.但是 A* 如何提前知道最优值? 如果您不知道最优路径成本,这种搜索是否有效并保证得到最优 ..
发布时间:2021-11-30 13:12:27 AI人工智能

在二维网格 c# 中找到最接近的值

我创建了一个用于模拟机器人应用程序的 c# 控制台应用程序.我已经为机器人创建了一个 2D 网格来移动: List地图; 地图是一个 25x25 的网格(开始时)并填充了以下值: 0 = 未探索的空间,1 = 探索空间,2 = 墙,3 = 障碍物,9 = 机器人 机器人从位置 (12,12) 开始.我希望能够在此网格中搜索最近的未探索空间并返回该位置,以便我可以将该位置和机器人位置提供给 ..
发布时间:2021-11-30 13:12:20 C#/.NET

Astar 父级,getpath

有我的 astar 算法,但我不知道如何获得父级并从目的地获得快速路线. 节点脚本方法getPos() (Vector2)父(节点)节点 n = ?.Parent;while(n != null){path.add(n.getPos());n = n.Parent;} 解决方案 您必须将“当前"设置为相邻节点的父节点.然后如果找到目的地,你就按照父条目的路径,这就是路径 编辑:我也看不 ..
发布时间:2021-11-30 13:12:08 其他开发

在这些条件下,A* 是否会返回一个恒定的 fscore?如果是这样,我如何更好地打破领带?

编辑:我回答了我自己的问题.我无法将其发布为答案,因为我的代表不到 10 人.我已将其作为编辑包含在 ~~~~~~~~~~ 行下. 我相信这个问题不需要代码示例,因为它是关于算法的.不是具体的实现. 假设您有一个节点网格,每个节点都连接到四个边权重为 1 的邻居(即没有对角线移动).使用的启发式是曼哈顿距离.起点在左上角,目标在右下角. 自然,算法会倾向于向右或向下扩展节点.每个 ..
发布时间:2021-11-30 13:11:59 其他开发

A*(A-star) 算法给出错误的路径和崩溃

我正在 react.js 中实现 A*(A-star) 算法,但只要 startNode(green) 或 destinationNode(blue) 有多个邻居,或者图中存在循环,我的程序就会崩溃.从/向 openList 添加和删除邻居或在 getPath() 函数中更新 parentId 时,会出现问题.我什至看不到控制台,因为网站宕机了.每个节点有:id、name、x、y、connecte ..
发布时间:2021-11-30 13:11:42 前端开发

Java:更改对象值而不更改所有引用

这可能是一个菜鸟问题,但我就是不明白. 我正在尝试在我的游戏中实现 A* 寻路.我正在关注 本教程 和 AstarPathfinder.java 中的代码.但是,我没有实例化 AStarPathfinder 类并为所有 Nodes 设置一个 2D 数组,而是创建了一个静态方法,将我的 2D 数组(关卡/世界)、开始和结束节点传递给该方法.因此,我总是必须将当前和下一个 Node 存储在 No ..
发布时间:2021-11-30 13:11:34 Java开发

A* 算法 Java

我整个周末都在玩这个.我正在尝试将节点存储在 PriorityQueue 数据结构中.我的 astar 函数似乎没有做它应该做的.有人介意看看吗? public void aStar(Node from, Node to) {PriorityQueueexploreList = new PriorityQueue();ArrayList访问 = 新 ArrayList();ArrayList后继 ..
发布时间:2021-11-30 13:11:24 Java开发

在*搜索中跟踪图块

我很难跟踪 getAdjacentTiles(..) 生成的图块.我已经确定了下面的 A* 实现的性能问题是我没有跟踪之前看到的图块,每次调用 getAdjacentTiles 都会返回新的图块(Node's) 而不是 openSet 或 closedSet 中的任何图块.我决定使用 Node 对象列表作为迄今为止创建的所有图块,并将其传递给 getAdjacentTiles 以确定它生成的图块是 ..
发布时间:2021-11-30 13:11:12 Python

A* 算法错误

我尝试在 Java 中创建 A* 算法,但遇到了这个奇怪的错误.我知道 A* 并不总能找到最佳路径,但在这里它似乎违背了理性并选择了一条更糟糕的路径,而且我在代码中找不到导致这种情况的错误.似乎在我创建的其他地图上找到了最佳解决方案.这是错误的图片,以及节点的打印输出 http://i.imgur.com/IudT7.png 这是我使用的(部分)代码. import java.uti ..
发布时间:2021-11-30 13:11:04 Java开发

A* 与最长路径中的树木

设 T 是一棵树,其中每个节点代表一个状态.根代表初始状态.从父级到子级的边指定了可以在父级上执行的操作以更改状态(新状态将是子级).每条边都与一个增益相关联,即我通过从父状态转换到子状态而获得了一些东西. 此外,假设从根节点到叶节点的每条路径的长度为 Q. 我的目标是找到长度为 Q 的最有希望的路径之一,即保证最大增益的路径(其中路径增益定义为附加到路径边缘的增益的总和). 显 ..
发布时间:2021-11-30 13:10:55 其他开发

可以在未加权图中简化 A* 搜索吗?

这是一个几乎是 A* 搜索的算法.本质上它是带有使用 A* 优先级的优先级队列的 BFS. frontier 这个算法缺少处理这个事实的 A* 部分:找到的第一个顶点的路径不一定是到那个顶点的最短路径. 很容易想出缺少部分至关重要的示例……对于加权图.对于未加权的图表,我一直无法想出任何. 这个更简单的 A* 版本是否可能适用于未加权的图? 解决方案 不,它不适用于任意 ..
发布时间:2021-11-30 13:10:44 其他开发

如何为这个 A* 程序构建一个邻接表

我正在尝试了解 A* 寻路算法,以及如何在 Python 程序中实现它.我发现 这个网站 做得很好解释算法本身如何工作的工作,以及提供一些示例代码. 这里是我卡住的地方: def make_graph(mapinfo):节点 = [[AStarGridNode(x, y) for y in range(mapinfo.height)] for x in range(mapinfo.widt ..
发布时间:2021-11-30 13:10:33 Python

A* 认识到实现目标是不可能的

我在 wiki 文章 但即使我已经关闭,我仍然在应该失败的板上获得无限运行时间. 似乎打开新节点的速度大于关闭它们的速度,因为对于每个节点,大约有 1-4 个新节点添加到 open 但只有一个节点从 移动打开到关闭. 那么如何才能认识到给定的起跑板没有通向目标的路径而无需永远等待? 这是代码: public List>搜索(GameBoard startBoard,GameBo ..
发布时间:2021-11-30 13:10:23 C#/.NET

A*寻路不走最短路径

我的 A* 寻路函数总能到达预期的目的地,但它几乎总是有点偏离.举个例子: [我制作了一张漂亮的图片来展示我的问题,但显然要等到我的声誉达到 10 时才会发布;对不起,我是新来的.:P] 本质上,它会尽可能向左或向上拉,而不会实际向路径添加更多图块.这听起来像是计算 gScore 的问题,或者可能是根据相邻图块的 gScores 重新分配图块的父级的部分,但我无法弄清楚哪里出了问题.我 ..
发布时间:2021-11-30 13:10:11 C/C++开发

A* 用于寻找最短路径并避免作为障碍物的线

我必须得到二维中两点之间的(最短)/(最佳)距离.我必须避免可能连接在一起的线条形状.关于如何表示我可以旅行的节点的任何建议?我曾想过制作一个网格,但这听起来不太准确或优雅.如果一条线的任何一点在一个正方形内(该节点是正方形的中心),我会认为一个节点是不可行走的. 一个例子是从 A 点到 B 点. 网格是解决这个问题的推荐方法吗?提前致谢! 解决方案 我认为这基本上是 Lars ..
发布时间:2021-11-30 13:10:00 其他开发

当网格图中有多个目标时,如何设计 A* 的启发式?

我面临一个问题,我必须使用 A* 来搜索地图,而这张地图中有多个目标要达到.我的目标是扩展地图中的最少节点,关于如何设计此 A* 算法的启发式方法有任何想法吗?谢谢 解决方案 假设“多个目标"是指您想要达到任何一个,只需采用所有启发式中的最小值.假设您的启发式是一致,这是仍然是一致的启发式. 如果您想覆盖所有人,这基本上是旅行商问题,NP-Complete. ..

将航点添加到 A* 图形搜索

我有能力使用 A* 计算起点和终点之间的最佳路线.现在,我通过将 A* 应用于点的所有排列中的对来包括起点和终点之间的航点. 示例: 我想从第 1 点到达第 4 点.另外,我想通过第 2 点和第 3 点. 我计算 (1, 2, 3, 4) 的排列: 1 2 3 41 2 4 31 3 2 41 3 4 21 4 2 31 4 3 22 1 3 42 1 4 32 3 1 42 ..
发布时间:2021-11-30 13:09:38 其他开发

路径未到达我的 A* 算法中的结束节点

继 如何在大空间范围内加速最小成本路径模型,我尝试在 Netlogo 中编写 A* 算法以在大空间范围内增加我的最小成本路径模型.这是我的代码: 到findPath [ID-start-node ID-end-node]让 currentNodesInList [ ]让当前节点节点 ID-起始节点let end-node 节点 ID-end-node询问当前节点 [设置颜色为红色]询问终端节点[ ..
发布时间:2021-11-30 13:09:31 其他开发

有哪些常见的可接受的距离启发式方法?

在智能搜索问题中最常用的用于估计距离的启发式方法是什么?特别是,我对可以(通常)用作 A* 搜索的可接受启发式的指标感兴趣.我遇到了直线距离和曼哈顿距离,还有其他的吗? 解决方案 启发式方法往往针对给定的问题非常具体,因为它的想法是结合您可能拥有的关于该问题的其他知识.所以“一般启发式"不是一个非常有用的类别.也就是说,听起来您是在专门讨论距离度量,它是一个定义更明确的子集. 就距离 ..
发布时间:2021-11-30 13:09:21 AI人工智能