Please enable JavaScript.

Coggle requires JavaScript to display documents.

Backtracking - Coggle Diagram

- - - - The idea is to place queens one by one in different columns, starting from the leftmost column. When we place a queen in a column, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes then we backtrack and return false.
  - - - 1- Start with an empty set
        2 - Add the next element from the list to the set
        3 - If the subset is having sum M, then stop with that subset as solution.
        4 - If the subset is not feasible or if we have reached the end of the set, then backtrack through the subset until we find the most suitable value.
        5 - If the subset is feasible (sum of seubset < M) then go to step 2.
        6 - If we have visited all the elements without finding a suitable subset and if no backtracking is possible then stop without solution.
- - - - Assignment Problem
        
        Assign n people to n jobs so that the total cost of assignment is as small as possible
        
        The search for an optimal solution can often be speeded by using an “intelligent” ranking function, also called an approximate cost function to avoid searching in sub-trees that do not contain an optimal solution. It is similar to BFS-like search but with one major optimization. Instead of following FIFO order, we choose a live node with least cost. We may not get optimal solution by following node with least promising cost, but it will provide very good chance of getting the search to an answer node quickly.
      - Knapsack Problem
        
        Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.
        
        We can use Backtracking to optimize the Brute Force solution. In the tree representation, we can do DFS of tree. If we reach a point where a solution no longer is feasible, there is no need to continue exploring. In the given example, backtracking would be much more effective if we had even more items or a smaller knapsack capacity.
      - Traveling Salesman Problem
        
        Find the shortest Hamiltonian circuit for a graph G
        
        for current node in tree, we compute a bound on best possible solution that we can get if we down this node. If the bound on best possible solution itself is worse than current best (best computed so far), then we ignore the subtree rooted with the node.