A fast universal search by equivalent program pruning
Swarna Kamal Paul, Parama Bhaumik · 2016
Universal search is the asymptotically fastest method to solve a wide class of inversion problems. Recently this method has been used to develop several efficient optimal general problem solvers. However the huge constant slowdown factor associated with this algorithm prevents it from widespread practical application. Our endeavor is to reduce this constant slowdown factor in the non incremental version of the algorithm which can be easily extended in the incremental version. While searching the exponential program space, universal search method generates and tests several equivalent programs. Pruning equivalent programs will evidently reduce the search space and consequently the search time. Experimental analysis reveals a huge speed up of the search method. Even though pruning is applied it has also been shown theoretically that if universal search can find a solution then the proposed search method can always find a solution for a given problem.