2019/06/07 by Laurent Orseau, Levi H. S. Lelis, Orseau, Laurent +3
Computer Science · #AI-based Problem Solving and Planning #Artificial Intelligence (cs.AI) #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #Metaheuristic Optimization Algorithms Research
paper · pdf · doi:10.48550/arxiv.1906.03242
openalex publication_date 2019/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce and analyze two parameter-free linear-memory tree search\nalgorithms. Under mild assumptions we prove our algorithms are guaranteed to\nperform only a logarithmic factor more node expansions than A* when the search\nspace is a tree. Previously, the best guarantee for a linear-memory algorithm\nunder similar assumptions was achieved by IDA*, which in the worst case expands\nquadratically more nodes than in its last iteration. Empirical results support\nthe theory and demonstrate the practicality and robustness of our algorithms.\nFurthermore, they are fast and easy to implement.\n