Subproblem ordering heuristics for AND/OR best-first search

作者：

Highlights：

• Subproblem ordering impacts the performance of AND/OR Best-First search.

• Look-ahead (and thus MBE bucket errors) can be used to guide subproblem ordering.

• Several schemes to approximate bucket errors are proposed to deal with overhead.

摘要

•Subproblem ordering impacts the performance of AND/OR Best-First search.•Look-ahead (and thus MBE bucket errors) can be used to guide subproblem ordering.•Several schemes to approximate bucket errors are proposed to deal with overhead.

论文关键词：Graphical models,Heuristic search,Combinatorial optimization,Artificial intelligence

论文评审过程：Received 15 May 2017, Revised 17 October 2017, Accepted 27 October 2017, Available online 9 November 2017, Version of Record 14 March 2018.

论文官网地址：https://doi.org/10.1016/j.jcss.2017.10.003