Оценки сложности решения задач распознавания с обучением в классе алгоритмов индуктивной резолюции

Abstract

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. = Рассматриваются три алгоритма решения задач распознавания образов, называемые алгоритмами индуктивной резолюции, для случая, когда все признаки объектов принимают конечное количество значений: алгоритм, основанный на методе объектных резолюций, алгоритм распознавания, использующий функцию близости объектов, и комбинированный алгоритм. Подсчитана вычислительная сложность этих алгоритмов и показано, что сложность алгоритма объектных резолюций и комбинированного алгоритма прямо пропорциональна третьей степени количества объектов, построенных этими алгоритмами. Для уменьшения времени работы алгоритмов предложены модификации всех трех алгоритмов, использующие идею метода ветвей и границ. Приведены оценки сложности модифицированных алгоритмов. Показано, что с помощью предлагаемой модификации время работы алгоритмов индуктивной резолюции уменьшается в экспоненциальной зависимости от структуры информации о рассматриваемом объекте.