Scribd Logo
Upload

Welcome to Scribd!

  • 61 views

    Backtracking Concept

    Uploaded by

    Romel O. Reyes
    Backtracking is a general algorithm for solving problems by exploring all possible solutions in a step-by-step manner from an initial state (point A) until reaching a desired end state (point B). It involves recursively trying possibilities and abandoning ("backtracking") a partial potential solution when it is determined not to satisfy constraints or lead to the desired solution. The key steps are to define cases for rejecting an invalid path, accepting a valid solution, and continuing exploration of the next step. The algorithm is implemented recursively by trying all options, backtracking when a path fails, and returning true when a solution is found.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Backtracking Concept

    Uploaded by

    Romel O. Reyes
    61 views3 pages
    Backtracking is a general algorithm for solving problems by exploring all possible solutions in a step-by-step manner from an initial state (point A) until reaching a desired end state (point B). It involves recursively trying possibilities and abandoning ("backtracking") a partial potential solution when it is determined not to satisfy constraints or lead to the desired solution. The key steps are to define cases for rejecting an invalid path, accepting a valid solution, and continuing exploration of the next step. The algorithm is implemented recursively by trying all options, backtracking when a path fails, and returning true when a solution is found.

    Original Description:

    Backtracking Algorithm Concept for programmers

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Backtracking is a general algorithm for solving problems by exploring all possible solutions in a step-by-step manner from an initial state (point A) until reaching a desired end state (point B). It involves recursively trying possibilities and abandoning ("backtracking") a partial potential solution when it is determined not to satisfy constraints or lead to the desired solution. The key steps are to define cases for rejecting an invalid path, accepting a valid solution, and continuing exploration of the next step. The algorithm is implemented recursively by trying all options, backtracking when a path fails, and returning true when a solution is found.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    61 views3 pages

    Backtracking Concept

    Uploaded by

    Romel O. Reyes
    Backtracking is a general algorithm for solving problems by exploring all possible solutions in a step-by-step manner from an initial state (point A) until reaching a desired end state (point B). It involves recursively trying possibilities and abandoning ("backtracking") a partial potential solution when it is determined not to satisfy constraints or lead to the desired solution. The key steps are to define cases for rejecting an invalid path, accepting a valid solution, and continuing exploration of the next step. The algorithm is implemented recursively by trying all options, backtracking when a path fails, and returning true when a solution is found.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 3

    BACKTRACKING

    In simple words Backtracking is a general way to solve a problem by using a computer. The
    algorithm is considered general since it doesnt describe how to solve a specific problem (like
    sorting numbers or searching for an element in a list), but it gives some high-level principles to
    solve many different problems.
    The main idea of Backtracking is to solve a problem by starting from point A and going through
    all the possible options/paths until reaching point B. When we find a path from A to B it means
    we found a solution and solved the problem!
    The general form of a Backtracking algorithm:
    The easiest way to implement a backtracking algorithm is by using recursion.
    First, We need to define three cases:
    Reject: We are in the wrong way this path cant lead us to the solution.
    Accept: We find a solution for the problem.
    Step: We are at some point between A to B, continue to the next step.

    Second, we just put our cases in this template (pseudo code):
    function backtracking (input_list, output_list):

    # Reject this path doesn't lead to any solution
    if reject case = true:
    return false

    # Accept We find a solution!
    if accept case = true:
    print output_list # Our solution
    return true

    # Step go over all the possible options in the input
    for each (n in input_list):
    test = backtracking(input_list.remove(n), outputlist.push(n)) #
    Recursion
    if test = true:
    return true

    # We didn't find any solution
    return false

    # First call
    call backtracking({some_input}, {})
    Example:
    Lets take this list of numbers: {3,4,1}, and try to sort them using Backtracking.
    First, our cases:
    Reject if at the end of the output we have two unsorted numbers.
    Accept the input list is empty! (= we sorted all the numbers)
    Continue each time take a number from the input and try to put it at the end of the output.
    Running the algorithm:
    First call: original list {3,4,1}, output {}
    1. pick 3 original list {4,1}, output {3} Continue
    2. pick 4 original list {1}, output {3,4} Continue
    3. pick 1 original list {}, output {3,4,1} Reject! no more options, go backward
    4. pick 1 original list {4}, output {3,1} Reject! no more options, go backward
    5. pick 4 original list {3,1}, output {4} Continue
    6. pick 3 original list {1}, output {4,3} Reject! try the next option
    7. pick 1 original list {3}, output {4,1} Reject! no more options, go backward
    8. pick 1 original list {3,4}, output {1} Continue
    9. pick 3 original list {4}, output {1,3} Continue
    10. pick 4 original list {}, output {1,3,4} Accept! This is our solution!

    Putting it all together Java Implementation for sorting with backtracking:
    import java.util.ArrayList;
    public class BacktrackingSort {

    public static int counter = 0;

    public static boolean sortBacktracking
    (ArrayList input_list, ArrayList output_list, int level) {

    // Trace
    counter++;
    System.out.println(counter + "# Level " + level
    + ": " + input_list + " " + output_list);

    // Reject this path doesn't lead to any solution
    if (output_list.size() > 1 &&
    (output_list.get(output_list.size() - 2)
    > output_list.get(output_list.size() - 1))){
    return false;
    }

    // Accept We find a solution!
    if (input_list.size() == 0) {
    System.out.println("Solution: " + output_list);
    return true;
    }

    // Step go over all the possible options in the input
    for (Integer n : input_list) {
    ArrayList clone_input_list
    = (ArrayList) input_list.clone();
    clone_input_list.remove(n);
    ArrayList clone_output_list
    = (ArrayList) output_list.clone();
    clone_output_list.add(n);
    boolean test = sortBacktracking(clone_input_list,
    clone_output_list, level + 1);
    if (test){
    return true;
    }
    }

    // We didn't find any solution
    return false;
    }

    public static void main(String[] args) {
    ArrayList input_list = new ArrayList();
    input_list.add(3);
    input_list.add(4);
    input_list.add(1);
    ArrayList output_list = new ArrayList();

    // First call
    sortBacktracking(input_list, output_list, 0);
    }
    }

    You might also like