Iterative Deepening Dynamically Improved Bounds Bidirectional Search
提出一种新的双向搜索算法，通过迭代加深和一致启发式改进路径成本下界，并采用节点过滤技术大幅降低内存需求。在煎饼问题、滑块拼图和魔方实验中，该算法比A*等现有算法更快、更省内存。
This paper presents a new bidirectional search algorithm to solve the shortest path problem. The new algorithm uses an iterative deepening technique with a consistent heuristic to improve lower bounds on path costs. The new algorithm contains a novel technique of filtering nodes to significantly reduce the memory requirements. Computational experiments on the pancake problem, sliding tile problem, and Rubik’s cube show that the new algorithm uses significantly less memory and executes faster than A* and other state-of-the-art bidirectional algorithms. Summary of Contribution: Quickly solving single-source shortest path problems on graphs is important for pathfinding applications and is a core problem in both artificial intelligence and operations research. This paper attempts to solve large problems that do not easily fit into the available memory of a desktop computer, such as finding the optimal shortest set of moves to solve a Rubik’s cube, and solve them faster than existing algorithms.