Searching for an optimal path in a tree with random costs

摘要

We consider the problem of finding an optimal path leading from the root of a tree to any of its leaves. The tree is known to be uniform, binary, and of height N, and each branch independently may have a cost of 1 or 0 with probability p and 1−p, respectively.We show that for p<1/2 the uniform cost algorithm can find a cheapest path in linear expected time. By contrast, when p>1/2, every algorithm which guarantees finding an exact cheapest path, or even a path within a fixed cost ratio of the cheapest, must run in exponential average time. If, however, we are willing to accept a near optimal solution almost always, then a pruning algorithm exists which finds such a solution in linear expected time. The algorithm employs a depth-first strategy which stops at regular intervals to appraise its progress and, if the progress does not meet a criterion based on domain-specific knowledge, the current node is irrevocably pruned.