c++ - 具有时间相关图的 Astar

Question

我有一个表示路线网络的图表 - 航路点是顶点，路线是边。问题在于，在某些时期内，航路点之间可能存在无法穿越的区域。但这些区域不一定会影响顶点，只会影响边。

我使用时间作为成本函数，因此对于每个顶点(以及边缘)，我可以获得访问者和/或启发式中的到达时间。但是，由于权重图是可读的，我无法更改边的权重以使其“太长”。

另一方面，我无法创建自定义权重图，因为我不知道提前到达的时间，因为它取决于路径。

我在论坛上发现的知识是使用启发式并将其设置为 inf 以防出现“坏”顶点。但我需要的是选择“坏”边。

您是否有关于访问启发式中当前检查的边的想法(默认情况下，它的唯一输入是顶点描述符)？

我知道我可以在 examine_edge 访问者中做出决定，但是我应该在其中调用什么来让 astar 知道这条边不好，不应该使用？也许我可以创建一个外部 bool “坏边”属性映射(对于所有顶点)，如果当前边是“坏”，则在 examine_edge 访问者中将目标顶点设置为真？然后可以通过试探法访问这个“坏边”属性映射。但是，在我看来，这可能不是最佳解决方案。

还有其他想法吗？

提前致谢!

Answer 1

解决此类问题的一种常见方法是构建一个新图，其节点包含的信息比原始节点多。在您的情况下，请考虑创建一个包含每个节点的多个拷贝的图形，可能每个不同的时刻一个。然后，如果在适当的时间点相应节点之间有一条边，则让每条边都在一对节点之间。例如，始终打开的边将带您从某个时间点的节点到稍后时间点的相应节点，而仅在某个时间点处于事件状态的边将仅在该时间点出现在图中.

这种方法的缺点是会增大图表的大小，但如果您可以选择延迟评估图表，则这种方法可能非常合理。