Weighted heuristic anytime search: new schemes for optimization over graphical models

详细信息    查看全文

• 作者：Natalia Flerova ; Radu Marinescu…
• 关键词：Graphical models ; Heuristic search ; Anytime weighted heuristic search ; Combinatorial optimization ; Weighted CSP ; Most Probable Explanation
• 刊名：Annals of Mathematics and Artificial Intelligence
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：79
• 期：1-3
• 页码：77-128
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence (incl. Robotics); Mathematics, general; Computer Science, general; Complex Systems;
• 出版者：Springer International Publishing
• ISSN：1573-7470
• 卷排序：79

文摘

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.