An Empirical Study of Search Algorithms Applied to Reconstructability Analysis
Computer Science at Creighton University
Systems Science at Binghmaton University
Last modified: November 20, 2006
Reconstruction analysis (RA) is a problem whose search space explodes as a function of n, where n the number of variables in the base system. The total number of solutions is on the order of 2^2^n. This paper will show that exhaustive methods can search a space on the order of 2^n^2. Since this is still a computationally complex problem for reasonable values of n, heuristic methods are the only reasonable answer to practical application of RA. This paper discusses the application of both heuristic and exhaustive optimization techniques to the problem of reconstruction analysis for various values of n. Methods applied include genetic algorithms, simulated annealing, random search, bottom up search and top down search.