Please enable JavaScript.

Coggle requires JavaScript to display documents.

M15 - Coggle Diagram

- - - - Backtracking is a more intelligent variation of this approach. The principal
        idea is to construct solutions one component at a time and evaluate such partially
        constructed candidates as follows. If a partially constructed solution can be de-
        veloped further without violating the problem’s constraints, it is done by taking
        the first remaining legitimate option for the next component. If there is no legiti-
        mate option for the next component, no alternatives for any remaining component
        need to be considered. In this case, the algorithm backtracks to replace the last
        component of the partially constructed solution with its next option.
        
        It is convenient to implement this kind of processing by constructing a tree
        of choices being made, called the state-space tree. Its root represents an initial
        state before the search for a solution begins. The nodes of the first level in the
        tree represent the choices made for the first component of a solution, the nodes
        of the second level represent the choices for the second component, and so
        on. A node in a state-space tree is said to be promising if it corresponds to a
        partially constructed solution that may still lead to a complete solution; otherwise,it is called nonpromising.
        
        Leaves represent either nonpromising dead ends or
        complete solutions found by the algorithm. In the majority of cases, a state-
        space tree for a backtracking algorithm is constructed in the manner of depth-
        first search. If the current node is promising, its child is generated by adding the
        first remaining legitimate option for the next component of a solution, and the
        processing moves to this child. If the current node turns out to be nonpromising,
        the algorithm backtracks to the node’s parent to consider the next possible option
        for its last component; if there is no such option, it backtracks one more level up
        the tree, and so on. Finally, if the algorithm reaches a complete solution to the
        problem, it either stops (if just one solution is required) or continues searching
        for other possible solutions.
- - - - Hamiltonian Circuit problem
        Without loss of generality, we can assume that if a Hamiltonian circuit exists,
        it starts at vertex a. Accordingly, we make vertex a the root of the state-space
        The first component of our future solution, if it exists, is a
        first intermediate vertex of a Hamiltonian circuit to be constructed. Using the
        alphabet order to break the three-way tie among the vertices adjacent to a, we
        select vertex b. From b, the algorithm proceeds to c, then to d, then to e, and
        finally to f, which proves to be a dead end. So the algorithm backtracks from f
        to e, then to d, and then to c, which provides the first alternative for the algorithm
        to pursue. Going from c to e eventually proves useless, and the algorithm has to
        backtrack from e to c and then to b. From there, it goes to the vertices f , e, c, and
        d, from which it can legitimately return to a, yielding the Hamiltonian circuit a, b,
        f , e, c, d, a. If we wanted to find another Hamiltonian circuit, we could continue
        this process by backtracking from the leaf of the solution found.
        
        Subset-Sum
        As our last example, we consider the subset-sum problem: find a subset of a given
        set A = {a1,...,an} of n positive integers whose sum is equal to a given positive
        integer d. For example, for A = {1, 2, 5, 6, 8} and d = 9, there are two solutions:
        {1, 2, 6} and {1, 8}. Of course, some instances of this problem may have no
        solutions.
        It is convenient to sort the set’s elements in increasing order. So, we will
        assume that
        a1 < a2 < ... < an.
        The state-space tree can be constructed as a binary tree like that in Figure 12.4 for
        the instance A = {3, 5, 6, 7} and d = 15. The root of the tree represents the starting
        point, with no decisions about the given elements made as yet. Its left and right
        children represent, respectively, inclusion and exclusion of a1 in a set being sought.
        Similarly, going to the left from a node of the first level corresponds to inclusion
        of a2 while going to the right corresponds to its exclusion, and so on. Thus, a path
        from the root to a node on the ith level of the tree indicates which of the first i
        numbers have been included in the subsets represented by that node.
        We record the value of s, the sum of these numbers, in the node. If s is equal
        to d, we have a solution to the problem. We can either report this result and stop
        or, if all the solutions need to be found, continue by backtracking to the node’s
        parent. If s is not equal to d, we can terminate the node as nonpromising if either
        of the following two inequalities holds:
- - - - In general, we terminate a search path at the current node in a state-space
        tree of a branch-and-bound algorithm for any one of the following three reasons:
        The value of the node’s bound is not better than the value of the best solution
        seen so far.
        The node represents no feasible solutions because the constraints of the
        problem are already violated.
        The subset of feasible solutions represented by the node consists of a single
        point (and hence no further choices can be made)—in this case, we compare
        the value of the objective function for this feasible solution with that of the
        best solution seen so far and update the latter with the former if the new
        solution is better.
      - Let us illustrate the branch-and-bound approach by applying it to the problem of
        assigning n people to n jobs so that the total cost of the assignment is as small
        as possible.
        Recall that an instance of the assignment problem is specified
        by an n × n cost matrix C so that we can state the problem as follows: select one
        element in each row of the matrix so that no two selected elements are in the
        same column and their sum is the smallest possible.
      - How can we find a lower bound on the cost of an optimal selection without
        actually solving the problem? We can do this by several methods. For example, it
        is clear that the cost of any solution, including an optimal one, cannot be smaller
        than the sum of the smallest elements in each of the matrix’s rows. For the instance
        here, this sum is 2 + 3 + 1 + 4 = 10. It is important to stress that this is not the cost
        of any legitimate selection (3 and 1 came from the same column of the matrix);
        it is just a lower bound on the cost of any legitimate selection. We can and will
        apply the same thinking to partially constructed solutions. For example, for any
        legitimate selection that selects 9 from the first row, the lower bound will be
        9 + 3 + 1 + 4 = 17.
        
        One more comment is in order before we embark on constructing the prob-
        lem’s state-space tree. It deals with the order in which the tree nodes will be
        generated. Rather than generating a single child of the last promising node as
        we did in backtracking, we will generate all the children of the most promising
        node among nonterminated leaves in the current tree. (Nonterminated, i.e., still
        promising, leaves are also called live.) How can we tell which of the nodes is most
        promising? We can do this by comparing the lower bounds of the live nodes. It
        is sensible to consider a node with the best bound as most promising, although
        this does not, of course, preclude the possibility that an optimal solution will ul-
        timately belong to a different branch of the state-space tree. This variation of the
        strategy is called the best-first branch-and-bound.