Weighted heuristic anytime search: new schemes for optimization over graphical models |
| |
Authors: | Natalia Flerova Radu Marinescu Rina Dechter |
| |
Affiliation: | 1.University of California Irvine,Irvine,USA;2.IBM Research,Dublin,Ireland |
| |
Abstract: | Weighted heuristic search (best-first or depth-first) refers to search with a heuristic function multiplied by a constant w 31]. The paper shows, for the first time, that for optimization queries in graphical models the weighted heuristic best-first and weighted heuristic depth-first branch and bound search schemes are competitive energy-minimization anytime optimization algorithms. Weighted heuristic best-first schemes were investigated for path-finding tasks. However, their potential for graphical models was ignored, possibly because of their memory costs and because the alternative depth-first branch and bound seemed very appropriate for bounded depth. The weighted heuristic depth-first search has not been studied for graphical models. We report on a significant empirical evaluation, demonstrating the potential of both weighted heuristic best-first search and weighted heuristic depth-first branch and bound algorithms as approximation anytime schemes (that have sub-optimality bounds) and compare against one of the best depth-first branch and bound solvers to date. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|