Abstract:
The exhaustive search can be accelerated in solution of discrete-time problems which are reducible to search for zeros of the monotone function determined on elements of a finite grid which takes on just three values, -1 , 0, and 1, and where zeros are isolated. The grid is mapped into a ranked recursive forest and the exhaustive search proceeds by staged design of the forest whereby non-promising subtrees are cut off. This cutting influences the structure of the entire forest including that of the yet undesigned part. At every stage the data on the cutting made at earlier stages is used. Ways of cost saving representation of the intermediate information are described. Learning by logical recognition algorithms of the «bark» type is shown to be reducible to this search problem.