Proceedings

Characterizing Search Spaces

Download BibTeX Cite

Proceedings of the Eighth International Joint Conference on Artificial Intelligence. Planning and Search. Pages 780-781.

© 1983 International Joint Conferences on Artificial Intelligence

Abstract

A heuristic is good on a search space to the extent that it allows the prediction of which states are near to the goal. In this paper heuristics are investigated on several different search spaces. A measure is proposed for assessing the predictive accuracy of a given heuri stic on a given search space. Themeasure sheds light on characteristics of the Traveling Salesman Problem that make it computationally mor e difficult to solve than the Minimum Spanning-Tree Problem.

  1. Banerji, R B (1982) "Theory of Problem Solving: A Branch of Artificial Intelligence" Proc IEEE, 70: 12 p 1428-1448.
  2. Garey, M and Johnson, D (1979) Computers and Intractability Freeman & Co : San Francisco. Handbook of Artificial Intelligence, Vol/ (1981) ed A Barr and E Feigenbaum, William Kaufmann, Inc : Los Altos, Calif.
  3. Knuth, D E (1973) The Art of Computer Programming, Vol 3, Sorting and Searching, Addison-Wesley: Reading, Mass.
  4. Lenat, Douglas (1982) "The Nature of Heuristics " Artificial Intelligence, 19 189-249.
  5. Minsky, Marvin and Papert, Seymour (1972) Perceptrons , MIT Press: Massachusetts.
  6. Pearl, Judea (1983) "On the Discovery and Generation of Certain Heuristics" The AI Magazine, 4: I p 23-33.
  7. Nilsson, Nils (1980) Principles of Artificial Intelligence Tioga : Palo Alto, Calif.
  8. Rada, Roy (1981) "Searching and Gradualness " BioSystems, 14 p 219-226.
  9. Reingold, E, Nievergelt, J, and Deo, N (1977) Combinatorial Algorithms Prentice-Hall: Englewood Cliffs, New Jersey .

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards