标签: a-star

我不明白如何IDA*节省内存空间.从我的理解IDA*是A*迭代加深.

什么是内存量之间的差额A*使用VS IDA*.

最后一次迭代的IDA*行为是否完全相同A*并且使用相同数量的内存.当我跟踪时,IDA*我意识到它还必须记住低于f(n)阈值的节点的优先级队列.

我知道ID-Depth第一次搜索有助于深度优先搜索,允许它首先像搜索一样进行广度,而不必记住每个节点.但我认为它的A*行为首先就像深度一样,因为它忽略了沿途的一些子树.迭代加深如何使用更少的内存？

另一个问题是使用迭代加深的深度优先搜索允许您通过使其首先表现为宽度来找到最短路径.但A*已经返回最佳最短路径(假设启发式是可接受的).迭代加深如何帮助它.我觉得IDA*的最后一次迭代与之相同A*.

我一直在寻找一种强大的寻路方法,我正在开发基于平台游戏的游戏,A*看起来像是最好的方法.我注意到有一个关于Godot中AStar实现的演示.然而,它是为基于网格/磁贴的游戏编写的,我无法适应平台,其中Y轴受到重力的限制.

我找到了一个非常好的答案,描述了A*如何应用于Unity中的平台游戏.我的问题是......是否可以在Godot中使用AStar来实现上述答案中描述的相同内容？如果不使用内置的AStar框架,可以做得更好吗？在GDscript中它是如何工作(有或没有AStar)的一个非常简单的例子是什么？

虽然我已经发布了100点奖金(它已经过期),但我仍然愿意发布另外100点赏金并奖励它,等待回答这个问题.

PS:如果你在这个问题的正文中看到一些你觉得不合适的东西,需要注意或澄清......不要贬低我的投票!展示一些诚信并发表评论.你所做的一切都在伤害那些投票给我的其他人,并且实际上对这个问题的答案感兴趣.

我正在做作业中的3x3三维盒子拼图问题.我将用C编码.

有26个盒子,起初,第一个地方是空的.通过滑动盒子,我必须按正确的顺序排列它们.红色数字显示正确的顺序,第27个位置最后必须为空.我不想让你给我代码; 我在论坛中搜索,似乎我必须使用A*搜索算法,但是如何？

你能给我一些关于如何在这个问题上使用A*算法的技巧吗？我应该使用什么类型的数据结构？

我有一个应用程序将受益于使用A*; 但是,由于遗留原因,我需要它继续生成与之前有多个最佳路径可供选择的路径完全相同的路径.

例如,考虑这个迷宫

...X
FX.S
....

S = start
F = finish
X = wall
. = empty space

方向优先级Up; 对; 下; 离开了.使用广度优先,我们将找到路径DLLLU; 然而,使用A*我们立即离开,最终找到路径LULLD.

我一直试着确保在打破领带时始终朝着正确的方向扩展; PreviousNode从更重要的方向移动时覆盖指针,但在该示例中都不起作用.有没有办法做到这一点？

我尝试了标签搜索计算器[a-star] [and] [python]和[a-star] [and] [numpy],但一无所获.我也谷歌搜索它,但无论是由于标记化还是存在,我什么也没得到.

它并不比你的编码 - 访谈树遍历更难实现.但是,为每个人提供正确有效的实施将是一件好事.

numpy有A*吗？

我有一个100,100个瓷砖的空白网格.起点是(0,0),目标是(99,99).瓷砖是4路连接.

我的Floodfill算法在30ms内找到最短路径,但我的A*实现速度慢了大约10倍.

注意:无论网格或布局的大小如何,A*始终比我的填充更慢(3 - 10x).因为洪水填充很简单,所以我怀疑我在A*中缺少某种优化.

这是功能.我使用Python的heapq来维护一个f排序列表.'graph'包含所有节点,目标,邻居和g/f值.

import heapq

def solve_astar(graph):

    open_q = []

    heapq.heappush(open_q, (0, graph.start_point))

    while open_q:

        current = heapq.heappop(open_q)[1]

        current.seen = True # Equivalent of being in a closed queue

        for n in current.neighbours:
            if n is graph.end_point:
                n.parent = current
                open_q = [] # Clearing the queue stops the process

            # Ignore if previously seen (ie, in the closed queue)
            if n.seen:
                continue

            # Ignore If n already has a parent and the parent is closer
            if …

如果将游戏地图划分为子图,如何最小化子图之间的边缘？

我有一个问题,我试图通过像pacman或sokoban这样的基于网格的游戏进行A*搜索,但我需要找到"附件".外壳是什么意思？用尽可能少子图切割边缘尽可能给出的每个充当软约束的子图的顶点的数目的最大尺寸和最小尺寸.
或者你可以说我希望找到子图之间的桥梁,但它通常是同样的问题.

例

基于网格的游戏地图示例http://dl.dropbox.com/u/1029671/map1.jpg

鉴于一个看起来像这样的游戏,我想要做的是找到外壳,以便我可以正确地找到它们的入口,从而获得一个良好的启发式,以达到这些外壳内的顶点.

alt text http://dl.dropbox.com/u/1029671/map.jpg

所以我想要的是在任何给定的地图上找到这些彩色区域.

我的动机

我打扰这样做的原因并不仅仅是坚持使用简单的曼哈顿距离启发式的表现,因为外壳启发式可以提供更优化的结果,我不必实际做A*以获得适当的距离计算和当玩sokoban类型的游戏时,也可以在以后为这些围栏中的对手添加竞争阻挡.外壳启发式也可用于最小化方法,以更正确地找到目标顶点.

可能解决方案

该问题的可能解决方案是Kernighan Lin算法:

function Kernighan-Lin(G(V,E)):
  determine a balanced initial partition of the nodes into sets A and B
  do
     A1 := A; B1 := B
     compute D values for all a in A1 and b in B1
     for (i := 1 to |V|/2)
      find a[i] from A1 and b[i] from B1, such that g[i] = D[a[i]] + D[b[i]] - 2*c[a][b] is maximal
      move a[i] …

几天前我遇到了一个谜题.它可以轻松地手动解决.但我试图建立一个解决它的算法.但我不知道该怎么办.

在这里你可以看到我必须连接所有的彩色圆点.例如,我需要将黄点连接到另一个黄点,绿色连接到其他绿色,蓝色连接到蓝色等等.

这是一个如何解决它的例子.如果描述不清楚.

所以你可以看到我将黄点与另一个黄点相连.蓝色与另一个蓝色.但这会导致问题.你可以看到我已经阻挡了浅绿色的路径.我希望你明白这个主意.

所以我想解决它.蛮力方法可行,但需要很长时间,我对此不感兴趣.我尝试了实现广度优先搜索,深度优先搜索和Dijkstra算法.但我认为在这种情况下他们不会好.如果我错了,请纠正我.A*搜索可能有效,但启发式是什么？

谁能给我一些关于如何解决问题的直觉？

免责声明：我真的相信这不是类似问题的重复。我读过这些，他们（大部分）推荐使用堆或优先级队列。我的问题更多是“我不明白在这种情况下它们将如何工作”。

简而言之：

我指的是典型的 A*（A 星）寻路算法，如（例如）在 Wikipedia 上所述：

https://en.wikipedia.org/wiki/A*_search_algorithm

更具体地说，我想知道什么是最好的数据结构（可以是单个众所周知的数据结构，也可以是这些结构的组合），这样您就不会在算法的任何操作上获得 O(n) 性能需要在 open list 上做。

据我了解（主要来自维基百科的文章），需要对open list进行的操作如下：

此列表中的元素必须是具有以下属性的 Node 实例：

• 位置（或坐标）。为了便于论证，假设这是一个从 0 到 64516 的正整数（我将我的 A* 区域大小限制为 254x254，这意味着任何一组坐标都可以在 16 位上进行位编码）
• F 分。这是正浮点值。

鉴于这些，操作是：

• 将节点添加到打开列表：如果存在具有相同位置（坐标）的节点（但可能具有不同的 F 分数），则替换它。
• 从打开列表中检索（并删除）具有最低 F 分数的节点
• （检查是否存在并）从列表中检索给定位置（坐标）的节点

就我所见，对打开列表使用堆或优先级队列的问题是：

• 这些数据结构将使用 F-score 作为排序标准
• 因此，向这种数据结构添加节点是有问题的：如何以最佳方式检查具有相似坐标集（但 F 分数不同）的节点是否已经存在。此外，即使您以某种方式能够进行此检查，如果您确实找到了这样一个节点，但它不在堆/队列的顶部，那么如何以最佳方式删除它，以便堆/队列保持其正确的顺序
• 此外，根据节点的位置检查是否存在并删除节点不是最佳的，甚至是不可能的：如果我们使用优先队列，我们​​必须检查其中的每个节点，如果找到则删除相应的节点。对于一个堆，如果需要这样的移除，我想所有剩余的元素都需要提取并重新插入，这样堆仍然是一个堆。
• 当我们想要删除具有最低 F-score 的节点时，这种数据结构的唯一剩余操作是好的。在这种情况下，操作将是 O(Log(n))。

此外，如果我们制作自定义数据结构，例如使用 Hashtable（以位置为键）和优先队列的数据结构，我们仍然会有一些操作需要对其中任何一个进行次优处理：为了保持它们同步（两者都应该有相同的节点），对于给定的操作，该操作在其中一个数据结构上总是次优的：按位置添加或删除节点在 Hashtable 上会很快，但在 Priority Queue 上会很慢。删除具有最低 F 分数的节点在 Priority Queue 上会很快，但在 Hashtable 上会很慢。

我所做的是为使用它们的位置作为键的节点创建一个自定义 Hashtable，它还跟踪具有最低 F 分数的当前节点。添加新节点时，它会检查其 F 分数是否低于当前存储的最低 F 分数节点，如果是，则替换它。当您想要删除节点（无论是按位置还是最低的 F 得分为 1）时，此数据结构的问题就出现了。在这种情况下，为了更新保存当前最低 F 分数节点的字段，我需要遍历所有剩余的节点，以找到现在哪个节点的 F 分数最低。 …

我知道A*比Dijkstra的算法更好,因为它考虑了启发式值,但是从A*和Jump Point搜索这是在有障碍的环境中找到最短路径的最有效算法？有什么区别？