Iterative Budgeted Exponential Search
원문 초록
We tackle two long-standing problems related to re-expansions in heuristic search algorithms. For graph search, A* can require $\Omega(2^{n})$ expansions, where $n$ is the number of states within the final $f$ bound. Existing algorithms that address this problem like B and B' improve this bound to $\Omega(n^2)$. For tree search, IDA* can also require $\Omega(n^2)$ expansions. We describe a new algorithmic framework that iteratively controls an expansion budget and solution cost limit, giving rise to new graph and tree search algorithms for which the number of expansions is $O(n \log C)$, where $C$ is the optimal solution cost. Our experiments show that the new algorithms are robust in scenarios where existing algorithms fail. In the case of tree search, our new algorithms have no overhead over IDA* in scenarios to which IDA* is well suited and can therefore be recommended as a general replacement for IDA*.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
SQL-o1: Automatic Text-to-SQL Program Synthesis via Self-Reward Heuristic Search
A Survey on Mathematical Reasoning and Optimization with Large Language Models
KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
On Parallel External-Memory Bidirectional Search
LLM-Virus: Evolutionary Jailbreak Attack on Large Language Models
HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs
토론
이 논문과 연결된 포럼 글이 아직 없습니다.