Research And Realization Of General Searching Algorithms Of Optimal Problems

Searching of the state space is always being one of the usual ways for solving the optimal problems. The traditional ways of finding solutions only have Backtracking, Branch-and-Bound and implicit graphs search as their theoretical introduction. The shortcoming of these tactics is that they are not special that for a certain problem we must design a certain algorithm. The work needed for designing and realizing these algorithms is very strenuous as well as the correctness and efficiency can't be well assured. So this article put forward a theory that the optimal problems can be summed up to the mathematic and computing models of state space search of optimal problems. This conclusion unifies the Dijstra algorithm used in finding shortest path of traditional explicit graphs and the optimal search of implicit graphs, the search of graph and the search of graphs' tree into a common model and algorithm. A great significance of this article is that it changes the Branch and Bound algorithm and Backtracking algorithm into application examples of the generic search algorithm of optimal problems advanced in this article. Thus, the five tactics of traditional algorithm designing can be reduced to three tactics -divide-and-conquer, greedy and dynamic programming. Thus, the designing and realizing of many complicated optimal problems can be essentially simplified.