Volume 9 Number 2 (Feb. 2014)
Home > Archive > 2014 > Volume 9 Number 2 (Feb. 2014) >
JCP 2014 Vol.9(2): 420-424 ISSN: 1796-203X
doi: 10.4304/jcp.9.2.420-424

Implementation and Analysis of Iterative MapReduce Based Heuristic Algorithm for Solving N-Puzzle

Rohit P. Kondekar, Mohit Modi, Akash Gupta, Parag S. Deshpande, Gulshan Saluja, Richa Maru, and Ankit Rokde
Visvesvaraya National Institute of Technology, Nagpur, India

Abstract—MapReduce Programming paradigm provides an elegant and efficacious platform for catering large scale parallel implementations of Heuristic Search Algorithms. We present here an implementation and analysis of Parallel Breadth First Heuristic Search (PBFHS) Algorithm for solving very large combinatorial problems. Using N-Puzzle as our application domain we found that the scalability of Breadth First Search (BFS) and Iterative Deepening A* (IDA*) is limited on a single machine due to hardware constraints. In this algorithm, we generate a remarkably restrictive, yet a large search space using combination of highly efficient admissible and non-admissible heuristics. The graphs compiled from resulting output advocates our design and implementation flow. A 7 node Hadoop cluster setup on Amazon EC2, solves the hardest 24 Puzzle in 3 hours, and 35 Puzzle in 13 hours of computing time.

Index Terms—hadoop, heuristic, n-puzzle, parallel breadth first heuristic search, mapreduce

[PDF]

Cite: Rohit P. Kondekar, Mohit Modi, Akash Gupta, Parag S. Deshpande, Gulshan Saluja, Richa Maru, and Ankit Rokde, "Implementation and Analysis of Iterative MapReduce Based Heuristic Algorithm for Solving N-Puzzle," Journal of Computers vol. 9, no. 2, pp. 420-424, 2014.

General Information

ISSN: 1796-203X
Abbreviated Title: J.Comput.
Frequency: Bimonthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat,etc
E-mail: jcp@iap.org
  • Nov 14, 2019 News!

    Vol 14, No 11 has been published with online version   [Click]

  • Mar 20, 2020 News!

    Vol 15, No 2 has been published with online version   [Click]

  • Dec 16, 2019 News!

    Vol 14, No 12 has been published with online version   [Click]

  • Sep 16, 2019 News!

    Vol 14, No 9 has been published with online version   [Click]

  • Aug 16, 2019 News!

    Vol 14, No 8 has been published with online version   [Click]

  • Read more>>