A* 与最长路径中的树木 [英] A* vs trees in longest path
问题描述
设 T 是一棵树，其中每个节点代表一个状态.根代表初始状态.从父级到子级的边指定了可以在父级上执行的操作以更改状态(新状态将是子级).每条边都与一个增益相关联，即我通过从父状态转换到子状态而获得了一些东西.
Let T be a tree in which each node represents a state. The root represents the initial state. An edge going from a parent to a child specifies an action that can be performed on the parent in order to change state (the new state will be the child). Each edge is associated with a gain, i.e., I gain something by transitioning from the parent state to the child state.
此外，假设从根节点到叶节点的每条路径的长度为 Q.
Moreover, suppose that each path from the root to a leaf node has length Q.
我的目标是找到长度为 Q 的最有希望的路径之一，即保证最大增益的路径(其中路径增益定义为附加到路径边缘的增益的总和).
My objective is the one of finding the most promising path of length Q, i.e., the path that guarantees the largest gain (where the path gain is defined as the summation of the gains attached to the edges in the path).
显然，我不想探索整个树，因为 T 可能非常大.
Obviously, I would like to do this without exploring the entire tree, since T could be very huge.
因此，我考虑申请 A*.我知道 A* 可用于在图中找到最短路径，但是:
Thus, I thought about applying A*. I know that A* can be used to find the shortest path in a graph, but:
- 我没有成本，我有收获
- 我想找到最长的路径(实际上不是到起始节点的距离最长的路径，而是权重相加后给出最高值的路径)
- 我有一棵树而不是图(没有循环！)
最后，我想出了一组问题想向您提出:
Eventually, I came up with a set of question that I would like to pose to you:
- A* 适合此类问题吗?我会通过应用找到最佳解决方案吗?
- 由于 A* 需要在最短路径的情况下使用从当前节点到目标的成本的(低估)估计，我是否需要寻找从当前节点到目标的增益的(高)估计?目标并将其用作启发式方法?
- 给定 T 中的一个节点 n，我的想法是将启发式 h(n) 计算为 n 的子节点所获得收益的总和，这可能不那么严格.您认为还有更好的解决方案吗?
给定树中的节点 n，附加到从 n 出的边上的增益不能大于数量 U(n).而且随着n的深度增加，U(n)变得越来越小.
given a node n in the tree, the gain attached to an edge outgoing from n cannot be greater than a quantity U(n). Moreover, U(n) becomes smaller and smaller as the depth of n increases.
推荐答案
分析
原因如下.假设您断言路径 P 是最优的，并且没有检查边 e.不失一般性，我可以将 e 的增益设置为大于树中所有其他增益总和的值.那么你的路径 P 是不是最优的.
Analysis
The reason is as follows. Suppose you assert that a path P is optimal, and have not examined edge e. I can, without loss of generality, set the gain for e to a value greater than the sum of all other gains in the tree. Then your path P is not optimal.
因此，在检查所有边的增益之前所做的任何最优性断言都是错误的.
So any assertion of optimality made before examining all edges' gains is false.
如果没有给出关于边增益的额外信息，如果不探索整棵树，你就无法找到最佳路径.
If no additional information is given about the gains on edges, you cannot find the optimal path without exploring the entire tree.
例如，如果您有增益值的上限，则可以使用 A* 更有效地找到最佳路径，而不是检查每条边.
If you had, for example, an upper bound on gain values, you could use A* to more-efficiently find the optimal path and not examine every edge.
在编写此答案后对您对问题所做的更改的回复在下面的评论中.请务必查看它们.
这篇关于A* 与最长路径中的树木的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
