Studies in the use and generation of heuristics (greedy algorithms)
Rina Dechter · 1985
This dissertation is composed of three studies having a common theme: the strengthening of weak methods by improving the advice that guides them. The first study examines the effects of removing some of the restrictions imposed on A* and, reexamines whether A* is computationally optimal relative to other algorithms that have access to the same heuristic information. It is shown that the wide class of algorithms which, like A*, return optimal solutions when all cost estimates are optimistic, does not contain an optimal algorithm. On the other hand A* is optimal in a somewhat more restricted sense: either (1) relative to the set of instances in which the heuristic estimates are consistent, or (2) relative to the subclass of algorithms which are Best-First. The second and third studies examine various means of mechanically generating heuristic advice for weak methods, using the paradigm that heuristics are generated by consulting a simplified model of the task domain. The second study generates advice to help Backtrack solve Binary Constraint Satisfaction Problems. The advice is generated automatically by consulting relaxed models known to yield a backtrack-free solutions. The information retrieved from these models induces a preference order among the choices pending in the original problem. Optimal algorithms for solving easy problems are presented and analyzed, and the utility of using the advice is evaluated experimentally, using a synthetic domain of CSP problem instances. The last study is devoted to the analysis of optimization problems that are solvable by Greedy algorithms since such easily solved problems are natural targets for simplification. The contribution of this study is in dealing with ordering optimization problems in which a set of n elements should be ordered to minimize a certain cost function. We give several necessary and sufficient conditions characterizing order dependent cost functions which can be optimized by greedy schemes, and distinguish two types of greedily optimized ordering problems; dominant and non-dominant.