Perimeter search

摘要

A technique for improving heuristic search efficiency is presented. This admissible technique is referred to as perimeter search since it relies on a perimeter of nodes around the goal. The perimeter search technique works as follows: First, the perimeter is generated by a breadth-first search from the goal to all nodes at a given depth d. The path back to the goal along with each perimeter node's state descriptor are stored in a table. The search then proceeds normally from the start state. During each node generation, however, the current node is compared to each node on the perimeter. If a match is found, the search can terminate with the path being formed with the path from the start to the perimeter node together with the previously stored path from the perimeter node to the goal. Both analytical and experimental results are presented to show that perimeter search is more efficient than IDA∗ and A∗ in terms of time complexity and number of nodes expanded for two problem domains.