Fundaments of Branching Heuristics
Fundaments of Branching Heuristics
复制标题
分支启发法的基础
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
O. Kullmann
中科院分区：
文献类型：
--
作者：
O. Kullmann
本章的主题是为“分支启发式”提供基础。“启发式”的整个领域是非常多样化的，我们将集中在一个特定的部分，在那里，过去40年的发展可以包含在真正值得被称为“理论”的东西中。这一章的完整版本，包括所有的证明和大量的例子，可以在[Kul08a]中找到。“启发式”的概念是人工智能领域的基础。“启发式”概念的(早期)历史在[BF81]第二节A节中讨论过，在SAT文献中这个概念的使用遵循了他们对启发式的定义，即一种使用额外信息来限制搜索空间大小的方法，尽管在本章中我们考虑的是受限上下文，其中完整性不是问题，但搜索过程的启发式部分只影响资源使用，而不是正确性。此外，我们在这里只研究一种特定形式的搜索过程，即回溯搜索。我们考虑这样一种情况，我们有一个问题实例F，其中所有直接(“有效”)方法都失败，因此F必须被拆分为子问题。在本章的上下文中，我们基本上假设已经给出了分裂F的方法，从而产生了可能的“分支”F；。。，Fm，将F分成m个子问题Fi，启发式算法的任务是比较不同的分支，并找到其中最好的分支。让我们假设我们已经给出了三个分支进行比较：
The topic of this chapter is to provide foundations for “branching heuristics”. The whole field of “heuristics” is very diverse, and we will concentrate on a specific part, where developments in the last four decades can be comprised in what actually deserves to be called a “theory”. A full version of this chapter, containing all proofs and extensive examples, is available in [Kul08a]. The notion of a “heuristics” is fundamental for the field of Artificial Intelligence. The (early) history of the notion of “heuristics” is discussed in [BF81], Section II.A, and the usage of this notion in the SAT literature follows their definition of a heuristics as a method using additional information to restrict the search space size, though in this chapter we consider a restricted context, where completeness is not an issue, but the heuristical component of the search process affects only resource usage, not correctness. Furthermore we only study a specific form of search processes here, namely backtracking search. We consider the situation where we have a problem instance F where all direct (“efficient”) methods fail, and so F has to be split into subproblems. In the context of this chapter we basically assume that the method for splitting F is already given, yielding possible “branchings” F ; F1, . . . , Fm, splitting F into m “subproblems” Fi, and the task of the heuristic is to compare different branchings and to find the “best” branching among them. Let us assume that we have given three branchings to compare: