Peculiar optimisation problems, which arise in structural recognition, are analysed. The problems consist in optimisation of functions of large number of discrete arguments. Peculiarity of the problems consists in that the functions under optimisation are presented as a sum of large number of terms, each of them depending only on small number of variables, e.g. only on two arguments. The problems of such type are known as -labelling problems. Though the set of all possible problems of such type forms an NP-complete class, several tractable subclasses of this class are known. Two of them are most popular in pattern recognition. They are so called acyclic and supermodular problem classes.
A concept of equivalent transformations of -problems is defined in the paper. On the base of such transformations an approach to solution to -problems is described. It is shown that the set of problems, which can be solved with their equivalent transformations, includes all acyclic and supermodular -problems.
Copyright. All Rights Reserved.