相关疑难解决方法(0)

我正在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几乎将执行时间减半,同时保持相同的路线.

过去几周我一直在使用nodejs和玩多人HTML5游戏websockets.

我已经陷入了这个问题一段时间了.想象一下,我有一个用数组实现的tileheet map(如下所示).

1或棕色瓷砖 - 路上有障碍物,玩家无法通过它.

0或绿色瓷砖 - 是允许玩家移动的自由路径.

通过以下方式访问地图上的任何图块:

 array[x][y]

我想创建最快的算法,找出地图两点之间的最短路径(如果有的话).你会如何解决这个问题？我知道这是常见的问题.

示例:

位置(1,7)的玩家用一些人工智能发射子弹,该AI会朝向位置(6,0)的敌方玩家.子弹必须计算两个球员之间的最短路线,如果没有,它只会在墙上爆炸.

问题:

如何有效地找到两点之间的最短路线？

我目前正致力于实现A*算法,两个节点之间的距离不规则.包含节点的图是定向和加权图.每个节点连接到至少一个其他节点,也可以存在具有不同距离的对称连接.节点只不过是一个标签,不包含任何特殊信息

我需要的是一种启发式方法,以确定从任何节点A到另一个节点B的最短路径尽可能准确.我尝试使用一种启发式方法来返回到节点最近邻居的距离,但当然这并不像没有启发式算法那样有效(= Dijkstra).

我对A*算法的实现主要包括2个类,算法本身的类(AStar)和节点(Node)的类.该代码主要基于Wikipedia伪代码.

源代码 AStar.java

public class AStar {
    private AStar() {}

    private static Node[] reconstructPath(Map<Node, Node> paths, Node current) {
        List<Node> path = new ArrayList<Node>();
        path.add(0, current);
        while (paths.containsKey(current)) {
            current = paths.get(current);
            path.add(0, current);
        }
        return path.toArray(new Node[0]);
    }

    public static Node[] calculate(Node start, Node target, IHeuristic heuristic) {
        List<Node> closed = new ArrayList<Node>();
        PriorityQueue<Node> open = new PriorityQueue<Node>();
        Map<Node, Double> g_score = new HashMap<Node, Double>();
        Map<Node, Double> f_score = new …

除了 Dijkstra 之外，还有其他方法可以计算近乎完整的图的最短路径吗？我有大约 8,000 个节点和大约 1800 万条边。我已经浏览了“地图上的 a 到 b”线程并决定使用 Dijkstra。我使用 Boost::Graph 库在 Perl 中编写了脚本。但结果并不是我所期望的。使用调用 $graph->dijkstra_shortest_path($start_node,$end_node); 计算一条最短路径大约需要 10 多分钟。

我知道有很多优势，这可能是运行时间缓慢的原因。我是死在水里了吗？还有其他方法可以加快这个速度吗？

我想知道Google map使用哪种算法来计算2点之间的方向？谷歌曾经提到过它吗？

p/s:我问谷歌使用的算法找到2点之间的最短路线.

我有大约1000分.我试图根据距离对这个点进行分组.我使用的是harversine配方,但它似乎超级慢.在android中1000分需要4秒.在我的本地环境需要60毫秒.

我不关心岁差,积分不超过25公里.

我可以使用另一种配方吗？

自sdk 3.0以来,可以在iPhone中轻松使用GPS功能,但明确禁止使用Google的地图.我认为这有两个含义:

1. 您必须自己提供地图
2. 您必须自己计算最短的路线.

我知道计算最短的路线已经困扰了数学家多年,但汤姆汤姆和谷歌都做得很好,所以这个问题似乎已经解决了.在网上搜索,我自己不是数学家,我遇到了Dijkstra算法.您是否有人在iPhone中的类似地图的应用程序中成功使用此算法？您愿意与我/社区分享吗？这是正确的方法,还是其他选择？非常感谢你的考虑.