Using Alternative Suboptimality Bounds in Heuristic Search
Using Alternative Suboptimality Bounds in Heuristic Search
复制标题
在启发式搜索中使用替代次优界限
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Nathan R Sturtevant
中科院分区：
文献类型：
--
作者：
R. Valenzano;Shahab Jabbari Arfaee;J. Thayer;Roni Stern;Nathan R Sturtevant
搜索文献中的大多数有限的次级算法已经开发出来，以使这些算法的解决方案保证不超过（1 +ε）例如，不是次优界的唯一可能的形式。 ，我们考虑开发算法的问题，以满足给定的，任意的次级优势，我们开发了一个理论框架，可用于构造大量可能的次级优势范式。开发额外有限算法的框架，并表明在实践中，这些新算法有效地权衡了运行时的副本。
Most bounded suboptimal algorithms in the search literature have been developed so as to be epsilon-admissible. This means that the solutions found by these algorithms are guaranteed to be no more than a factor of (1 + ε) greater than optimal. However, this is not the only possible form of suboptimality bounding. For example, another possible suboptimality guarantee is that of additive bounding, which requires that the cost of the solution found is no more than the cost of the optimal solution plus a constant gamma.In this work, we consider the problem of developing algorithms so as to satisfy a given, and arbitrary, suboptimality requirement. To do so, we develop a theoretical framework which can be used to construct algorithms for a large class of possible suboptimality paradigms. We then use the framework to develop additively bounded algorithms, and show that in practice these new algorithms effectively trade-off additive solution suboptimality for runtime.