This research is concerned with a fundamental problem solving method - heuristic search, and an important heuristic search algorithm - the best-first search. A new best-first search algorithm is developed, whose memory requirement is only linear in the search depth, at the cost of expanding some nodes more than once. The algorithm runs faster than classical best-first search due to its simple structure and reduced overhead. It removes the memory limitation of best-first search, and opens up a host of new applications: combinatorial optimization problems, optimal decisions under real-time constraints, selective search algorithms for two-player games, and difficult constraints satisfaction problems.
