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

Question

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

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

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

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

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

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

最后，我想出了一组问题想问你:

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

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

Answer 1

分析

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

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

结论

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

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

---

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