Weighted heuristic anytime search: new schemes for optimization over graphical models
Weighted heuristic anytime search: new schemes for optimization over graphical models
复制标题
加权启发式随时搜索：图形模型优化的新方案
DOI：
10.1007/s10472-015-9495-1
复制
发表时间：
2017
影响因子：
1.2
通讯作者：
R. Dechter
中科院分区：
文献类型：
--
作者：
N. Flerova;Radu Marinescu;R. Dechter
加权启发式搜索(最佳优先或深度优先)是指使用启发式函数乘以常量w[31]的搜索。本文首次证明了对于图模型中的优化查询，加权启发式最佳优先和加权启发式深度优先分支限界搜索算法是一种竞争能量最小的随时优化算法。针对路径搜索问题，研究了加权启发式最优优先算法。然而，它们在图形模型中的潜力被忽略了，这可能是因为它们的内存成本，以及因为替代的深度优先分支和界限似乎非常适合于有界深度。对于图形模型，加权启发式深度优先搜索算法还没有被研究过。我们报告了一个重要的经验评估，展示了加权启发式最佳优先搜索和加权启发式深度优先分支定界算法作为近似随时格式(具有次最优界)的潜力，并与迄今最好的深度优先分支定界求解器之一进行了比较。
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.