java - OSM 和 A* 算法

Question

我正在尝试编写一个程序，该程序使用 OSM 数据作为输入来计算从 A 到 B 的最短路径(A* 算法)。该程序应该可以在 Android Java 中运行。我使用来自 OSM 的数据并使用 osm_2po(是一个将 OSM xml 文件转换为 sql 文件的应用程序 OSM2PO)进行转换，以将数据放入我的 PostGIS 数据库中。我的数据库有以下条目，据我所知，我需要从中获取以下变量:source_id, target_id, x1, y1, x2, y2, cost 和 reverse cost。其中 source_id 是基于 OSM 数据的源节点的 id。 (长的)其中 target_id 是基于 OSM 数据的目标节点的 id。 (长的)其中x1、y1为源节点坐标(经纬度)。 (漂浮)其中x2，y2为目标节点的坐标(经纬度)。 (漂浮)其中 cost 是从源到目标所产生的成本。 (漂浮)其中反向成本是从目标到源( float )的生成成本。在我的 Java 程序中，我有一个数据类 Node，它将我的节点存储在以下结构中，用于存储我的数据库条目:源、目标、成本、x、y、x2、y2数据类节点本身可以​​存储x1,y1,x2,y2,bool visited,sourcenode,targetnode,cost,g,h,f。这将被存储两次。 src -> target 一次，反之亦然。输入具有以下结构:Start Node:source = 0，target = 选定的起点，所有其他变量都设置为 0。Destination Node: source = selected destination point，其他所有变量都设置为0。

我只有用户想要开始的节点，仅此而已。该算法应该找出下一个节点是什么并分别展开它们。我用来实现的伪代码来自德语维基百科Wikipedia .openlist 是一个 priorityqueue，closedlist 是一个 ArrayList。在算法中我使用曼哈顿距离来计算H。

我的问题/问题是:我的数据结构适合这样的实现吗？或者我是否必须使用为节点存储所有前任和后继的结构？我必须通过从我的数据库中获取数据来设置 h 吗？如果是，我如何计算 h？是从前一个节点到下一个节点的顶​​点成本吗？

Answer 1

如果我理解正确的话，数据库中的每个条目都是一个图边——它有一个源点和一个目标点。不过我不知道“h”代表什么。

考虑将您的 Node 类重命名为“Edge”，因为它似乎代表两个节点之间的路径，而不是单个节点。您可以使用值为 -1、0、1 的整数作为方向，而不是 boolean 值。但是你的数据结构没问题。