Informatica

This work is a continuation of our previous papers devoted to exploration of the regular search procedures efficiency in binary search spaces. Here we formulate the problem in a rather general form as a problem of optimization of an unimodal pseudoboolean function given implicitly and obtain analitical estimates of the expected time of a minimum point search for procedures of direct local search. These estimates are polinomial for the case of weakly nonmonotone functions and exponential for the general case of arbitrary unimodal functions. We hope that the proposed result will be usefull first of all for practical applications.

The local optimization techniques is the basis of majority of regular (exact) algorithms for the non-monoton pseudoboolean functions optimization as the most simple and, accordingly, the most universal method of the discrete optimization. However, the local optimization method does not guarantee the elimination of the total examination when the pseudoboolean optimization problem in a general state is solved. In the present paper the cutting off algorithms are suggested which guarantee the total examination elimination for any pseudoboolean optimization problem.

The characteristics of the polymodallocally strictly monotone pseudoboolean functions and ones having constancy sets are investigated in this paper; the searchal algorithms for their optimization are proposed; analytical investigation of the proposed algorithms effectiveness is carried out. The paper is a continuation of the authors' researches which were begun before.