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

Volume

1

fYear

2012

Firstpage

253

Lastpage

256

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer & Information Science (ICCIS), 2012 International Conference on

Print_ISBN

978-1-4673-1937-9

Type

conf

DOI

10.1109/ICCISci.2012.6297249

Filename

6297249