Title :
Iterative mapreduce based heuristic algorithm for solving N Puzzle
Author :
Kondekar, R. ; Gupta, Arpan ; Saluja, G. ; Maru, R. ; Rokde, A. ; Deshpande, Paru
Author_Institution :
Dept. of Comput. Sci. & Eng., Visvesvaraya Nat. Inst. of Technol., Nagpur, India
Abstract :
Mapreduce Programming paradigm provides an elegant and efficacious parallel implementation of Heuristic Search Algorithm. We present here a Parallel Breadth First Heuristic Search (PBFHS) Algorithm for solving very large combinatorial problems. Using N Puzzle as our application domain we found that scalability of Breadth First Search (BFS) and Iterative Deepening A* (IDA*) is limited on a single machine due to hardware constraints. We generated a highly restrictive, large search space using combination of three efficient and admissible heuristics namely Manhattan Distance, N-Max Swaps and Tile out of row and column. A Hadoop cluster comprising of 12 processors, solves the hardest 15 Puzzle in 2 hours, and 24 Puzzle in 6 hours of computing time.
Keywords :
combinatorial mathematics; iterative methods; parallel algorithms; parallel programming; tree searching; BFS; Hadoop cluster; IDA*; Manhattan distance; N puzzle; N-max swaps; PBFHS algorithm; admissible heuristics; hardware constraints; ierative mapreduce based heuristic algorithm; iterative deepening A*; mapreduce pogramming paradigm; parallel breadth first heuristic search algorithm; parallel implementation; search space; single machine; tile out of column; tile out of row; very large combinatorial problems; Hadoop; N-Puzzle; Parallel Breadth First Heuristic Search; cluster; heuristics;
Conference_Titel :
Computer & Information Science (ICCIS), 2012 International Conference on
Print_ISBN :
978-1-4673-1937-9
DOI :
10.1109/ICCISci.2012.6297249
