algorithm - A* 与最长路径中的树

Question

令 T 为一棵树，其中每个节点代表一个状态。根代表初始状态。从父级到子级的边指定可以在父级上执行的操作，以更改状态(新状态将是子级)。每条边都与一个增益相关联，即，我通过从父状态转换到子状态来获得一些东西。

此外，假设从根到叶节点的每条路径的长度为Q。

我的目标是找到长度为 Q 的最有希望的路径，即保证最大增益的路径(其中路径增益定义为路径中边缘的增益之和)。

显然，我想在不探索整个树的情况下执行此操作，因为 T 可能非常大。

因此，我想到了申请A*。我知道 A* 可用于查找图中的最短路径，但是:

• 我没有成本，我有收获
• 我想找到最长的路径(实际上不是距起始节点距离最长的路径，而是权重相加后给出最高值的路径)
• 我有一个树，而不是一个图(没有循环!)

最终，我想向您提出一系列问题:

1. A* 适合解决此类问题吗？我能通过应用找到最佳解决方案吗？
2. 由于 A* 需要在最短路径的情况下使用从当前节点到目标的成本(低估)估计，我是否需要寻找从当前节点到目标的增益(高估)目标并将其用作启发式？
3. 给定 T 中的节点 n，我的想法是将启发式 h(n) 计算为 n 的子节点所获得的增益的总和，这可能不是那么严格。您认为还有更好的解决方案吗？

编辑:给定树中的节点 n，附加到从 n 发出的边的增益不能大于数量 U(n)。而且，随着n深度的增加，U(n)变得越来越小。

Answer 1

分析

原因如下。假设您断言路径 P 是最佳路径，并且尚未检查边 e。在不失一般性的情况下，我可以将 e 的增益设置为大于树中所有其他增益之和的值。那么您的路径P不是最佳。

因此，在检查所有边的增益之前做出的任何最优性断言都是错误的。

结论

如果没有给出有关边缘增益的附加信息，如果不探索整个树，就无法找到最佳路径。

例如，如果您有增益值的上限，则可以使用 A* 更有效地找到最佳路径，而不是检查每条边。

---

在写完此答案后，您对问题所做的更改的回复位于下面的评论中。请务必查看它们。