N.R. Mahapatra and S.K. Namilikonda (USA)
Available-memory search, best-first search, branch-and-bound, cost-bounded search, depth-first search, iterative search, limited-memory search.
Branch-and-bound (B&B) best-first search (BFS) is a widely applicable method that requires the least number of node expansions to obtain optimal solutions to combinatorial optimization problems (COPs). However, for many problems of inter est, its memory requirements are enormous and can far exceed the available memory capacity on most systems. To circumvent this problem, two types of limited-memory search (LMS) methods have been proposed. Methods belonging to the first type are based purely on depth-first search (DFS) and require very little memory compared to that available on current systems, but they may perform significant node re-expansions, and hence generally require appreciable amounts of time; these are called minimal-memory search (MMS) methods. Examples of such methods are DFBB, IDA*, DFS*, IDA* CR, MIDA*, RIDA*, IE, RBFS, and IES*. The second type of methods are called available-memory search (AMS) methods, since they attempt to exploit the available memory to reduce node reexpansions. Sample methods in this category are ITS, MA*, RA*, SMA*, MREC, SNC, and MRBFS. In this paper, we survey and compare previous limited-memory search methods and present a performance evaluation of three important LMS methods: IDA*, IE, and SMA*.
Important Links:
Go Back
