java - 在具有双向加权边的图上生成路径

Question

我正在尝试在具有双向加权边的图上执行路径生成器的 Java 实现。问题在于根据兴趣点 (POI) 列表和用户兴趣为用户提供路线。已经计算了所有 POI 之间的用户兴趣、距离和旅行时间。利用这些数据，我能够创建一个具有双向边的图，其中边的权重是源节点和目标节点之间的行进时间。

有一些相关的用户输入:

• 他想要旅行的时间跨度，即 6 月 30 日下午 4 点到 6 月 30 日晚上 8 点。
• 行程的起点(坐标)，从那里选择最近的 POI 作为行程起点。

由于节点的权重是POI之间的行程时间，因此结果路径权重总和不能超过用户定义的时间跨度。这将是停止条件，而不是目标节点。

用户对 POI 的兴趣定义在 0 到 5 之间的范围内。理想情况下，在路径计算中也会考虑此变量，因为用户希望访问得分较高的 POI。

这个问题是在学术背景下提出的，我在这方面的知识不是很好。如果您有任何算法建议或任何其他想法来在合理的时间内解决此问题，我将不胜感激。

Answer 1

考虑以下过程:

• 在运行搜索时累积旅行时间和兴趣分数
• 如果满足以下条件之一，则停止探索当前路径:
  • 超过旅行时间限制
  • 访问过的所有兴趣点
• 如果满足以下条件之一，则将当前路径保持为最佳路径:
  • 这是探索的第一条路
  • 当前路径的兴趣分数高于最佳路径
  • 当前路径具有与最佳路径相同的兴趣分数和更短的旅行时间
• 原路返回探索另一条路