2

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.

Moreover, suppose that each path from the root to a leaf node has length 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).

Obviously, I would like to do this without exploring the entire tree, since T could be very huge.

Thus, I thought about applying A*. I know that A* can be used to find the shortest path in a graph, but:

  • I don't have costs, I have gains
  • I want to find the longest path (actually not the longest in distance from the start node, but the one whose weights, if summed up, give the highest value)
  • I have a tree and not a graph (no cycles!)

Eventually, I came up with a set of question that I would like to pose to you:

  1. Is A* suitable for this type of problem? Will I find the optimal solution by applying it?
  2. Since A* requires to use an (under)estimate of the cost from the current node to the goal in case of shortest path, am I required to look for an (over)estimate of the gain from the current node to the goal and use it as a heuristic?
  3. Given a node n in T, my idea was to compute the heuristic h(n) as the summation of the gains achieved by the children of n, which might not be so tight. Do you think there could be a better solution?

EDIT: 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.

4

2 回答 2

4

分析

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

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

结论

如果没有提供关于边增益的附加信息,则不探索整个树就无法找到最佳路径

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


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

于 2013-06-13T16:55:54.033 回答
0

要回答这个问题,A* 通常不是探索树木的正确方法。它适用于加权图,而不是树。如果您正在探索一棵树,则使用回溯。您可以通过使用启发式或修剪使回溯更加智能。

于 2013-06-13T17:52:37.573 回答