Date of Award
12-1996
Document Type
Thesis
Degree Name
Master of Science
Department
Department of Electrical and Computer Engineering
First Advisor
Eugene Santos, PhD
Abstract
Knowing that reasoning over probabilistic networks is, in general, NP-hard, and that most reasoning environments have limited resources, we need to select algorithms that can solve a given problem as fast as possible. This thesis presents a method for predicting the relative performance of reasoning algorithms based on the domain characteristics of the target knowledge structure. Armed with this knowledge, the research shows how to choose the best algorithm to solve the problem. The effects of incompleteness of the knowledge base at the time of inference is explored, and requirements for reasoning over incompleteness are defined. Two algorithms for reasoning over incomplete knowledge are developed: a genetic algorithm and a best first search. Empirical results indicate that it is possible to predict, based on domain characteristics, which of these algorithms will have better performance on a given problem.
AFIT Designator
AFIT-GCS-ENG-96D-05
DTIC Accession Number
ADA319586
Recommended Citation
Borghetti, Brett J., "Inference Algorithm Performance and Selection under Constrained Resources" (1996). Theses and Dissertations. 5862.
https://scholar.afit.edu/etd/5862