Open Access Open Access  Restricted Access Subscription or Fee Access

Heuristic Search with Perspective Data Structure – Revisited & A Case Study of A*

G. P. Potdar, Dr. R. C. Thool

Abstract


Past few decades the researchers have worked a lot on heuristic search algorithms. Most of the researches have focused on the methodologies and other aspects. There are very few studies on the type of data structures used by these algorithms for implementation. This paper discusses effectiveness of various heuristic search algorithms with specific focus on the data structure employed and its effectiveness. This paper also presents the methods and their effectiveness with alternate data structures along with a case study of heuristic method with typical data structure.


Keywords


Artificial Intelligence, Data Structure, Generalized Linked List, Multi-Level Link List (MLL), Priority Queue, OPEN/CLOSE List.

Full Text:

PDF

References


Nils J Nilsson, (1980) “Principals of Artificial Intelligence”, Narosa Publishing House.

Pearl J., (1984) “Heuristics: Intelligent Search Strategies for Computer Problem Solving”, Reading, MA: Addison-Wesley.

Abdel-Elah Al-Ayyoub, Fawaz Masoud, (2000) “Heuristic Search Revisited” , Journal of Systems and software, Volume 55, No 2, pp. 103-113.

R. Korf, (1996) “Artificial Intelligence Search Algorithms”, CRC Handbook of Algorithms and Theory of Computation, M.J. Atallah (Ed.), CRC Press, Boca Raton, FL, pp. 36-1 to 36-20.

Blai Bonet and Eric A. Hansen, (2010) “Heuristic Search for Planning under Uncertainty”, Chapter in Heuristics, Probability and Causality: A Tribute to Judea Pearl College Publications. pp 3-22.

I. Pohl, (1975) “Practical and Theoretical Considerations In Heuristic Search Algorithms”, UCSC Heuristic Theory Project H-75, NATO-ASI Conference on the machine representation of knowledge, Santa Cruz, pp. 55-72.

Doran J. E. and D. Michie, (1966) “Experiments with the Graph Traverser program”, Proceedings of the Royal Society A, Volume 294, pp. 235-259.

I. Pohl, (1969) “Bi-Directional and Heuristic Search In Path Finding In A Graph”, Artificial Intelligence, Volume 1, pp. 193-204.

B. V. Cherkassy, A.V. Goldberg and T. Radzik, (1994) “Shortest path algorithms: Theory and experimental evaluation”, In-proceedings 5th ACM-SIAM symposium on discrete algorithms, pp. 516-525.

Colin R. Reeves, (1994) “Genetic algorithms and neighborhood search”, Evolutionary Computing Lecture Notes in Computer Science Volume 865, pp. 115-130.

Dorn J, (1995) “Iterative Improvement Methods for Knowledge-Based Scheduling”, AI Communications 8I, S. pp .20-34.

Breuker D., (1998) “Memory versus Search in Game”, Ph.D. paper, Department of Computer Science, Maastricht University, The Netherlands.

R. Korf, (1990) “Real time heuristic search”, Artificial Intelligence ACM Digital Library, Volume 42, pp. 189-211.

Hart T. P. and D. J. Edwards, (1963) “The Alpha-beta Heuristic”, M.I.T. Artificial Intelligence Project Memo, Massachusetts Institute of Technology, Cambridge, Mass.

Gasching J., (1979) “Performance measurement and analysis of certain search algorithms”, Ph.D. thesis, Carnegie-Mellon University. Department of Computer Science.

R. Korf, (1985) “Depth-first iterative deepening: An optimal admissible tree search”, Artificial Intelligence, Volume 27(1), pp. 97–109.

R. Korf, (1992) “Linear-Space Best-First Search”, AAAI-92 Proceedings, pp 533-538.

Eric A Hansen, Rong Zhou, (2007) “Anytime Heuristic Search”, Journal of Artificial Intelligence Research 28, pp 267-297.

Shimbo M. and Ishida T., (2003) “Controlling the learning process of real-time heuristic search”, Artificial Intelligence, Volume 146(1), pp. 1–41.

G. P. Potdar and Dr. R. C. Thool, (2013) “An Alternate Way Of Implementing Heuristic Searching Technique”, International Journal of Research in Computer and Communication Technology, Volume 2, Issue 9. pp.793-795.

D. Corne, M. Dorigo and F. Glover, (1999) “A Multiple ant Colony System For Vehicle Routing Problems With Time Windows”, New Ideas in Optimization, McGraw-Hill, London, UK, pp. 63-76.

Franz Rothlauf, (2011) “Design of Modern Heuristics: Principles and Application - Principles and Application”, Springer Press.

Girish P. Potdar and Dr. R. C. Thool, (July 2014) “Comparison of Various Heuristic Search Techniques for Finding Shortest Path”, International Journal of Artificial Intelligence & Applications (IJAIA), Volume 5, No. 4, pp. 63-74.

Andrew V. Goldberg, Chris Harrelson, (2005) “Computing the shortest path: A* search meets graph theory”, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-2005), pp. 156–165.

Ethan Burns and Wheeler Ruml, (2013) “Iterative-Deepening Search with On-line Tree Size Prediction”, Annals of Mathematics and Artificial Intelligence, pp 1-23.


Refbacks

  • There are currently no refbacks.