Parallel multithreaded IDA* heuristic search: algorithm design and performance evaluation

References

• Al-Ayyoub , A. 2005 . Distributed bidirectional and unidirectional heuristic search: Algorithm design and empirical assessment . J. Super Comput. , 32 : 231 – 250 .
   Web of Science ®Google Scholar
• Al-Ayyoub , A. 2005 . Performance evaluation of parallel iterative deepening A* on clusters of workstations . J. Perform. Eval. , 60 ( 1–6 ) : 223 – 236 .
   Web of Science ®Google Scholar
• Applegate , D.L. , Bixby , R.E. , Chvatal , V. and Cook , W.J. 2006 . The Traveling Salesman Problem – A Computational Study , Princeton Series in Applied Mathematics Princeton, NJ : Princeton University Press .
   Google Scholar
• Cook , D. and Varnell , R. 1998 . Adaptive parallel iterative deepening search . J. Artif. Intell. Res. , 9 : 139 – 166 .
   Web of Science ®Google Scholar
• Cormen , T. , Leiserson , C. , Rivest , R. and Stein , C. 2001 . Introduction to Algorithms , 2nd ed. , Cambridge : MIT Press .
   Google Scholar
• Curt , P. and Richard , E.K. 1991 . Single – agent parallel window search . IEEE Trans Pattern Anal. Mach. Intell. , 13 ( 5 ) : 466 – 477 .
   Web of Science ®Google Scholar
• Datta , A. and Sen , R. 2000 . Improved parallel algorithm for maximal matching based on depth-first-search . Int. J. Parallel, Emergent Distrib. Syst. , 14 ( 4 ) : 321 – 327 .
   Google Scholar
• Duwairi , R. , Mahafzah , B. and Al-Ayyoub , A. 2002 . A framework for performance assessment of parallel bi-directional heuristic search , Proceedings of the International Conference on Artificial Intelligence (IC-AI'02) 1053 – 1059 . Las Vegas, NV, 24–27 June
   Google Scholar
• Felner , A. , Korf , R. and Hanan , S. 2004 . Additive pattern database heuristics . J. Artif. Intell. Res. , 22 : 279 – 318 .
   Web of Science ®Google Scholar
• Grama , A. , Gupta , A. , Karypis , G. and Kumar , V. 2003 . Introduction to Parallel Computing , 2nd ed. , Reading, MA : Addison Wesley .
   Google Scholar
• Hafidi , Z. , Talbi , E.-G. and Concalves , G. 1995 . Load balancing and parallel tree search: The MPIDA^* algorithm , Fifth International Conference on Parallel Computing ParCo'95, Gent, Belgium, 12–22 September
   Google Scholar
• Hans , J.B. (2005) . Threads cannot be implemented as a library , Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation PLDI'05 261 – 268 . Chicago, IL, 12–15 June, 40(6)
   Google Scholar
• Hart , P.E. , Nelson , N.J. and Raphael , B. 1968 . A formal basis for the heuristic determination of the minimum cost paths . IEEE Trans. Sys. Sci., Cybern. , 4 ( 2 ) : 100 – 107 .
   Web of Science ®Google Scholar
• Hayes , R. June 2001 . The sam loyd 15-puzzle Available at http://www.cs.tcd.ie/publications/tech-reports/reports.01/TCD-CS-2001-24.pdf
   Google Scholar
• Hennesy , J. and Patterson , D. 2006 . Computer Architecture: A Quantitative Approach , 4th ed. , Santa Monica, CA : Morgan Kaufmann .
   Google Scholar
• Korf , R. 1985 . Depth-first iterative deepening: An optimal admissible tree search . J. Artif. Intell. , 27 : 97 – 109 .
   Web of Science ®Google Scholar
• Korf , R. and Felner , A. 2002 . Disjoint pattern database heuristics . J. Artif. Intell. , 134 ( 1–2 ) : 9 – 22 .
   Web of Science ®Google Scholar
• Kumar , V. , Ramesh , K. and Rao , V. 1992 . Parallel best-first search of state-space graphs: A summary of results , Proceedings of the 10th National Conference on Artificial Intelligence, AAAI St Paul, MN
   Google Scholar
• Lagoudakis , M. February 1999 . An IDA^* Algorithm for optimal spare allocation , Proceedings of the ACM Symposium on Applied Computing (SAC '99) 486 – 488 . San Antonio, TX : ACM Press .
   Google Scholar
• Li , X. , Wu , J. and Zhong , S. 2008 . ISRL: Intelligent search by reinforcement learning in unstructured peer-to-peer networks . Int. J. Parallel, Emergent Distrib. Syst. , 23 ( 1 ) : 17 – 44 .
   Google Scholar
• Lin , R. and Olariu , S. 1995 . A cost-optimal EREW breadth-fist algorithm for ordered trees, with applications . Int. J. Parallel, Emergent Distrib. Syst. , 5 ( 3–4 ) : 187 – 197 .
   Google Scholar
• Mahanti , A. , Ghosh , S. , Nau , D.S. , Pal , A.K. and Kanal , L.N. 1997 . On the asymptotic performance of IDA* . Ann. Math. Artif. Intell. , 20 : 161 – 193 .
   Web of Science ®Google Scholar
• Manzini , G. 1995 . BIDA*: An improved perimeter search algorithm . Artif. Intell. , 75 : 347 – 360 .
   Web of Science ®Google Scholar
• Melab , N. , Devesa , N. , Lecouffe , M.P. and Toursel , B. 1996 . Adaptive Load Balancing of Irregular Applications a Case Study: IDA^* Applied to the 15-puzzle Problem , Lecture Notes in Computer Science 327 – 338 . Berlin/Heidelberg : Springer . Volume 1117/1996, Parallel Algorithms for Irregularly Structured Problems
   Google Scholar
• Pacheco , P.S. 1998 . A User's Guide to MPI , CA : Department of Mathematics, University of San Francisco .
   Google Scholar
• Quinn , M.J. 2004 . Parallel Programming in C with MPI and OpenMP , Boston, MA : McGraw-Hill .
   Google Scholar
• Rao , V. and Kumar , V. 1987 . Parallel depth-first search, part I: Implementation . Int. J. Parallel Program. , 16 ( 6 ) : 479 – 499 .
   Web of Science ®Google Scholar
• G. Reinelt, TSPLIB 95 is a library of sample instances for the TSP, Research Group Discrete Optimization, University of Heidelberg. Available at http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
   Google Scholar
• Russell , S. and Norvig , P. 2003 . Artificial Intelligence: A Modern Approach , 2nd ed. , Upper Saddle River, NJ : Prentice-Hall .
   Google Scholar
• Wah , B. and Shang , W. 1994 . A comparative study of IDA^*-style searches , Proceedings of the 6th International Conference on Tools with Artificial Intelligence ICTAI-94 290 – 296 . New Orleans, LA
   Google Scholar
• Wilkenson , B. 1996 . Computer Architecture Design and Performance , 2nd ed. , Europe : Prentice-Hall .
   Google Scholar
• Zabatta , F. 1999 . Multithreaded constraint programming and applications , New York, NY : University of New York . Ph.D. diss.
   Google Scholar
• Zhang , Y. and Hansen , E. 2006 . Parallel Breadth-first Heuristic Search on a Shared-memory Architecture , The Association for the Advancement of Artificial Intelligence (AAAI-06) Workshop on Heuristic Search, Memory-Based Heuristics and Their Applications Boston, MA
   Google Scholar