An expected-cost analysis of backtracking and non-backtracking algorithms

摘要: Consider an infinite binary search tree in which the branches have independent random costs. Suppose that we must find optimal (cheapest) or nearly path from root to a node at depth n. Karp and Pearl [1983] show bounded-lookahead backtracking algorithm A2 usually finds linear expected time (when costs take only values 0 1). From this successful performance one might conclude similar heuristics should be of more general use. But here equal success for simpler non-backtracking algorithm, so model cannot support conclusion. If, however, is generated by branching process there possibility nodes having no sons (or prohibitive costs), then hopeless while still performs very well. These results suggest guideline becomes attractive when "dead-ends" prohibitively costly outcomes.