Performance Measurement and Analysis of Certain Search Algorithms
Abstract
This thesis applies the methodology of analysis of algorithms to study certain combinatorial problems and search algorithms originating predominantly in the All literature, and extends that methodology to include experiments in a complementary role. Chapters 2 and 3 combine experimental and analytic techniques respectively to measure and to predict the performance of the A(+ or -) best-first search algorithm, which solves path-finding problems defined in terms of finite strongly connected graphs. In this domain, we make numerous experimental performance measurements varying the heuristic function, the size of the problem, a weighting coefficient, and the performance measure; we derive general formulas in a simpler worst case analysis model that purport to predict the experimental observations when evaluated at particular argument values that correspond to the experimental parameter settings; and we test the analytic predictions against the experimental observations. The A(+ or -) experiments use as case study a randomly generated set of instances of the Eight puzzle of varying size (depth of goal). The analysis in Chapter 3 extends the worst case tree search model of Pohl and others to arbitrary heuristic functions, resulting in cost formulas whose arguments include functions.
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1979
- Accession Number
- ADA286363
Entities
People
- John Gaschig
Organizations
- Carnegie Mellon University