John Gaschnig

Performance Measurement and Analysis of Certain Search Algorithms Degree Type: Ph.D. in Computer Science
Advisor(s): Herbert Simon
Graduated: August 1979

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.