The Complexity of Solution of Supervised Pattern Recognition Problems in a Class of Inductive Resolution Algorithms
The paper considers three algorithms for solving pattern recognition problems in the case when all signs of objects have a finite quantity of values: the first algorithm bases on object resolution method, the second one is a recognition algorithm which uses a closeness function of objects, and the third one combines these two algorithms. These algorithms are called inductive resolution algorithms. The computational complexity of all three algorithms is calculated. The complexity of the object resolution and combined algorithms is shown to be directly proportional to the cube of the quantity of objects built by these algorithms. In order to reduce running time of algorithms, modifications, which are based on the idea of branch and bound method, are suggested for all three algorithms. Complexities of modified algorithms are estimated. It is shown that, due to the suggested modification, the running time of inductive resolution algorithms decreases exponentially depending on the structure of information of the object which is being considered.