论文标题
用于贪婪最佳优先和*搜索的学习启发式功能的样本复杂性
Sample Complexity of Learning Heuristic Functions for Greedy-Best-First and A* Search
论文作者
论文摘要
贪婪的最佳优点搜索（GBFS）和*搜索（A*）是在大图上进行搜索的流行算法。两者都使用所谓的启发式功能，估计顶点与目标有多近。尽管使用域知识手工制作了启发式功能，但最近的研究表明，从数据中学习启发式功能在许多应用中有效。通过这种新兴方法的启发，我们研究了GBF和A*学习启发式功能的样本复杂性。我们建立在一个名为\ textIt {数据驱动算法设计}的最新框架上，并评估了一类实用程序函数的\ textit {pseudo-dimension}，以测量参数化算法的性能。假设固定了一组尺寸$ n $的顶点，我们提出$ \ mathrm {o}（n \ lg n）$和$ \ mathrm {o}（n^2 \ lg n）$上限GBFS和A*的伪维度上的上限，分别通过heurisation函数值。如果每个顶点都具有最多的$ d $，则可以将a*的上限提高到$ \ mathrm {o}（n^2 \ lg d）$，如果每个顶点具有最多的$ d $，并且如果边缘的重量是由$ \ mathrm {poly}（poly}（n）$。我们还为GBFS和A*提供了$ω（n）$的下限，这意味着我们对GBFS的界限和整数重量条件下的a* bunds a** a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a* a**的界限都紧密缩小到$ \ lg n $ factor。最后，我们讨论了一种情况，即通过次级次数衡量A*的性能，并表明我们有时可以通过将参数依赖性的最坏情况与样品复杂性结合结合来获得更好的保证。
Greedy best-first search (GBFS) and A* search (A*) are popular algorithms for path-finding on large graphs. Both use so-called heuristic functions, which estimate how close a vertex is to the goal. While heuristic functions have been handcrafted using domain knowledge, recent studies demonstrate that learning heuristic functions from data is effective in many applications. Motivated by this emerging approach, we study the sample complexity of learning heuristic functions for GBFS and A*. We build on a recent framework called \textit{data-driven algorithm design} and evaluate the \textit{pseudo-dimension} of a class of utility functions that measure the performance of parameterized algorithms. Assuming that a vertex set of size $n$ is fixed, we present $\mathrm{O}(n\lg n)$ and $\mathrm{O}(n^2\lg n)$ upper bounds on the pseudo-dimensions for GBFS and A*, respectively, parameterized by heuristic function values. The upper bound for A* can be improved to $\mathrm{O}(n^2\lg d)$ if every vertex has a degree of at most $d$ and to $\mathrm{O}(n \lg n)$ if edge weights are integers bounded by $\mathrm{poly}(n)$. We also give $Ω(n)$ lower bounds for GBFS and A*, which imply that our bounds for GBFS and A* under the integer-weight condition are tight up to a $\lg n$ factor. Finally, we discuss a case where the performance of A* is measured by the suboptimality and show that we can sometimes obtain a better guarantee by combining a parameter-dependent worst-case bound with a sample complexity bound.
