gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:59:32 24 4
gpt4 key购买 nike

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

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

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

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

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

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

还有其他想法吗?

提前致谢!

最佳答案

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

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

关于c++ - 具有时间相关图的 Astar,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38660381/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com