我试图在离散能量景观中找到两个最大值之间的最短路径，其中最短路径是在整个路径过程中高度降低最少的路径。可能最大能量路径是更正确的术语，但换句话说，即使一条路径绕着景观走了很长一段距离但没有下到山谷，它也会被认为是好的。
我最初的想法是创建一个景观图，其中权重是邻居之间景观高度的差异，上升和下降分别为正或负。我刚刚意识到这不会给出我需要的结果，实际上局部最大值之间的所有路径都将具有完全相同的成本。
然后我意识到，如果此图上节点之间的距离取决于路径的当前位置和历史记录，那么我可以获得我需要的结果。例如如果这条路径从一个山谷上下移动，那么我不会为沿着另一个山谷向下移动分配额外的成本(只要该路径没有超过以前从未达到过的低点)。
那么是否存在可以在探索路径时距离动态变化的图形搜索算法？
或者还有其他解决这个问题的建议吗？
最佳答案
这被称为瓶颈最短路径问题。它实际上比最短路径问题更容易，并且可以在无向图上以线性时间解决。参见示例 here .
关于algorithm - 图上距离动态变化的最短路径？ (最大能量路径)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3544083/