TREE-SEARCHING METHODS WITH AN APPLICATION TO A NETWORK DESIGN PROBLEM

SEARCH TREES We will talk about problems with the following characteristics: (i) We could recognise a solution to the problem if given one. Let us call the set of objects which is known to contain the solutions the'candidates'. We include cases where there is more than one solution or where an optimal solution is required. Some examples are: (i) In playing chess there are only a finite number of possible strategies (candidates) but the number is far too large to enumerate. Any assignment is a candidate and there are a finite, but usually large, number of assignments. The candidates are the (n -- I)! permutations of the points omitting the starting point. In this section we will describe in an abstract way two approaches to problems of this type. We will give examples of their use, first in'Some problems about sets' (p. Although both the approaches have often been used before, the discussion may help to clarify those features common to the different applications. Our two approaches are both search techniques (partial enumeration techniques).