Please enable JavaScript.

Coggle requires JavaScript to display documents.

Coping with the limitations of algorithm power - Coggle Diagram

- - - - The state-space tree is usually developed
        depth-first (i.e., similar to DFS)
        
        It can be used to solve problems that grows exponentially fast with the size of the input (i.e. 2^n)
        
        The main idea of backtracking a is to construct solutions one component at a time and evaluate such partially
        constructed candidates
        
        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
        
        Examples: n-queens problem, Hamiltonian circuit problem and the subset-sum problem
  - - - It can generate nodes according to several rules: the most natural one is the so-called best-first rule
- - - - //Gives a template of a generic backtracking algorithm
      - //Input: X[1..i] specifies first i promising components of a solution
      - //Output: All the tuples representing the problem’s solutions
      - if X[1..i] is a solution write X[1..i]
      - else for each element x ∈ Si+1 consistent with X[1..i] and the constraints do
      - X[i + 1]← x
      - Backtrack(X[1..i + 1])
      - In the worst case, it may have to generate all possible
        candidates in an exponentially (or faster) growing state space of the problem
        
        The hope is that a backtracking algorithm will be able to prune
        enough branches of its state-space tree before running out of time or memory
        
        There are several tricks that might help reduce the size of a state-space tree. One is to exploit the symmetry often present in combinatorial problems. Some solutions can be obtained from others by reflection or rotation
- - - - An optimal solution n is a feasible solution with the best value of the
        objective function
        
        Compared to backtracking, branch-and-bound requires two additional items:
        
        A way to provide, for every node of a state-space tree, a bound on the best
        value of the objective function on any solution that can be obtained by adding further components to the partially constructed solution represented by the node
        
        The value of the best solution seen so far
        
        It is posssible to compare a node’s bound
        value with
        the value of the best solution seen so far. If the bound value is not better than the value of the best solution seen so far, —the node is nonpromising and can be terminated
        
        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 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
        pointt (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
        
        The value of the node’s bound is not better than the value of the best solution seen so far