Inconsistency and Accuracy of Heuristics with A* Search
원문 초록
Many studies in heuristic search suggest that the accuracy of the heuristic used has a positive impact on improving the performance of the search. In another direction, historical research perceives that the performance of heuristic search algorithms, such as A* and IDA*, can be improved by requiring the heuristics to be consistent -- a property satisfied by any perfect heuristic. However, a few recent studies show that inconsistent heuristics can also be used to achieve a large improvement in these heuristic search algorithms. These results leave us a natural question: which property of heuristics, accuracy or consistency/inconsistency, should we focus on when building heuristics? While there are studies on the heuristic accuracy with the assumption of consistency, no studies on both the inconsistency and the accuracy of heuristics are known to our knowledge. In this study, we investigate the relationship between the inconsistency and the accuracy of heuristics with A* search. Our analytical result reveals a correlation between these two properties. We then run experiments on the domain for the Knapsack problem with a family of practical heuristics. Our empirical results show that in many cases, the more accurate heuristics also have higher level of inconsistency and result in fewer node expansions by A*.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
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
토론
이 논문과 연결된 포럼 글이 아직 없습니다.