标签: a-star

我在看马里奥人工智能大赛中的人一直在做什么,其中一些人利用A*(A-Star)路径算法构建了一些漂亮的马里奥机器人.

替代文字http://julian.togelius.com/mariocompetition2009/screen1.png
(马里奥·博特在行动视频)

我的问题是,A-Star与Dijkstra相比如何？看着它们,它们看起来很相似.

为什么有人会使用一个而不是另一个？特别是在游戏路径的背景下？

有关DFS,A*人工智能搜索的图搜索和树搜索版本有什么区别？

我正在OpenStreetMap地图上写一个快递/物流模拟,并且已经意识到如下图所示的基本A*算法对于大型地图(如大伦敦)来说不够快.

绿色节点对应于放置在开放集/优先级队列中的绿色节点,并且由于数量巨大(整个地图大约为1-2百万),需要5秒左右才能找到所示的路线.不幸的是,每条路线100毫秒是我的绝对限制.

目前,节点存储在邻接列表和空间100×100 2D阵列中.

我正在寻找可以在预处理时间,空间和路线最佳性能之间进行权衡的方法,以便更快地进行查询.根据剖析器,启发式成本的直线Haversine公式是最昂贵的函数 - 我尽可能地优化了我的基本A*.

例如,我在想是否从2D阵列的每个象限中选择一个任意节点X并在每个象限之间运行A*,我可以将路径存储到磁盘以供后续模拟.查询时,我只能在象限中​​运行A*搜索,以便在预先计算的路径和X之间进行搜索.

是否有我上面所描述的更精致的版本,或者我应该追求的另一种方法.非常感谢!

为了记录,这里有一些基准测试结果,用于任意加权启发式成本并计算10对随机选取的节点之间的路径:

Weight // AvgDist% // Time (ms)
1       1       1461.2
1.05    1       1327.2
1.1     1       900.7
1.2     1.019658848     196.4
1.3     1.027619169     53.6
1.4     1.044714394     33.6
1.5     1.063963413     25.5
1.6     1.071694171     24.1
1.7     1.084093229     24.3
1.8     1.092208509     22
1.9     1.109188175     22.5
2       1.122856792     18.2
2.2     1.131574742     16.9
2.4     1.139104895     15.4
2.6     1.140021962     16
2.8     1.14088128      15.5
3       1.156303676     16
4       1.20256964      13
5       1.19610861      12.9

令人惊讶的是,将系数增加到1.1几乎将执行时间减半,同时保持相同的路线.

我需要一些帮助找到一个良好的启发式解决以下问题:

您将得到一个R-by- C网格和六面的骰子.设start和 end是在这个网格两种截然不同的细胞.找到一条路径start,end使得当模具沿路径转动时,模具面朝上的总和是最小的.

模具的起始方向如下("2"朝南):

我模拟这个问题的方法是将模具的面值视为图形中边缘的成本.图形的顶点具有形式(row, col, die)(即,网格中的位置和模具的当前状态/方向).顶点不是简单的原因(row, col)是因为你可以使用骰子的多个配置/方向结束相同的单元格.

我用A*来找到问题的解决方案; 给出的答案是正确的,但效率不高.我已经确定问题是我正在使用的启发式问题.目前我正在使用曼哈顿距离,这显然是可以接受的.如果我将启发式乘以常量,则不再允许:它运行得更快,但并不总能找到正确的答案.

我需要一些帮助才能找到比曼哈顿距离更好的启发式方法.

哪个应该是在C#中简单实现A*(A star)算法的方法？

我编写了我的第一个稍微复杂的算法,即A Star Pathfinding算法的实现.我遵循了一些关于实现图形的Python.org建议,因此字典包含每个节点都链接的所有节点.现在,因为这是游戏的全部,每个节点实际上只是节点网格中的一个区块,因此我如何计算启发式和偶尔引用它们.

感谢timeit我知道我可以成功运行这个功能一秒钟一百多次.可以理解这让我有点不安,这是没有任何其他'游戏的东西'继续下去,如图形或计算游戏逻辑.所以我很想知道你们中是否有人可以加速我的算法,我完全不熟悉Cython或者它的亲属,我不能编写一行C.

没有更多的漫步,这是我的A Star功能.

def aStar(self, graph, current, end):
    openList = []
    closedList = []
    path = []

    def retracePath(c):
        path.insert(0,c)
        if c.parent == None:
            return
        retracePath(c.parent)

    openList.append(current)
    while len(openList) is not 0:
        current = min(openList, key=lambda inst:inst.H)
        if current == end:
            return retracePath(current)
        openList.remove(current)
        closedList.append(current)
        for tile in graph[current]:
            if tile not in closedList:
                tile.H = (abs(end.x-tile.x)+abs(end.y-tile.y))*10 
                if tile not in openList:
                    openList.append(tile)
                tile.parent = current
    return path

任何一致的启发式也是可以接受的.但什么时候启发式可以接受但不一致(单调)？

请举例说明这种情况.

我喜欢玩益智游戏Flood-It,它可以在线播放:

https://www.lemoda.net/javascript/flood-it/game.html

它也可以作为iGoogle小工具使用.目的是用最少数量的连续填充填充整个委员会.

我正在尝试编写一个可以最佳地解决这个难题的程序.解决这个问题的最佳方法是什么？理想情况下我想使用A*算法,但我不知道估算剩余步数的功能应该是什么.我写了一个程序,进行了深度4强力搜索,以最大化填充区域.它工作得相当好,并且在解决这个难题时打败了我,但我对这个算法并不完全满意.

有什么建议？提前致谢.

我们是否可以让人们在每种语言中发布A*寻路算法的简单优化实现代码？

这主要是为了获得乐趣,并且可以使用stackoverflow本身的功能......虽然我实际上对获取ActionScript 3版本感兴趣.

但是这个想法是,即使创建了不同的编程语言,这个"问题"将继续在未来永久更新!

我不知道在线的任何其他地方你可以看到伪代码"翻译"成许多(少得多)的不同语言.看起来它是一个有价值的资源,虽然不一定是这个网站的设计目的,但尝试它并看看是否有可能用于堆栈溢出的有价值的东西是没有害处的!

通常认为A*是解决寻路问题的最佳算法.

当A*不是找到解决方案的最佳算法时,是否存在任何情况？

与BFS,DFS,UCS等相比,A*有多好？