CODEWITHSUNDEEP
algorithmrecursiondynamic-programmingbacktrackingrecursive-backtracking
tubby
tubby

Reputation: 2144

In programming terms, what is a backtracking solution?

I have a couple of questions, as to what a backtracking solution really means.

  1. Say, you have n options from a current state, does a backtracking solution basically mean that you try out all of those states, and do the same for the sub-problems(where you might have n-1 states for the solution), and so on, and you return the best solution from the (n-1)th frame up to the nth frame.

See problem below where : Given a rope with length n, how to cut the rope into m parts with length n[0], n[1], ..., n[m-1], in order to get the maximal product of n[0]n[1] ... *n[m-1] Soa rope of length would be cut into 2*3*3 to get a product of 18. ,

public class RopeCuttingMaxProduct
{
    public static void main(String[] args)
    {
        System.out.println(fun(8));
    }

    static int fun(int n)
    {
        if(n == 1)
            return 1;

        int totalret = 0;
        for(int i = 1;i<n;i++)
        {
            /*At every frame, two options 1.to cut 2.to not cut
             *  1.If cutting, multiple ways to cut : Remember i+(n-i) == n
             *  2.If not cutting, just return n
             */
            /* Explore all possible solutions, from all possible paths 
             * and the subpaths that these lead to,
             * and their subpaths*/
            int reti = max(fun(n-i)*i,n);

            if(reti > totalret)
                totalret = reti;
        }
        return totalret;
    }

    static int max(int a, int b)
    {
        return a>b?a:b;
    }
}
  1. So, are all backtracking solutions exponential in time complexity?
  2. This sounds so much like recursion, that I cannot imagine something like this achieved by anything other recursion. Can you give me an example of a backtracking solution achieved without recursion
  3. How is it different from brute-force. Is the brute force solution for this problem to try out all possible combinations of the ways to add up to n. I find the above backtracking solution to be doing pretty much the same.

Upvotes: 0

Views: 364

Answers (1)

trijezdci
trijezdci

Reputation: 5454

If you consider the path your algorithm takes to be the traversal of a decision tree, then the solution, if it exists, is some leaf node of the tree, or if there are multiple solutions, then there are multiple leaf nodes that represent them.

Backtracking simply means that the algorithm detects at some point that the solution is not to be found in the branch of the tree it is currently in and then move back up one or more nodes to continue with other branches.

This does not mean that all nodes need to be visited. For example, if the algorithm detects that the current branch is not worth pursuing before it actually reaches a leaf, then it would avoid visiting all the remaining nodes in that branch.

Consequently, not all backtracking algorithms are brute-force.

How much unnecessary work such an algorithm can avoid is very specific to the problem, it cannot be answered in general. The general answer is that backtracking is not necessarily based on exhaustive searches/trials.

Upvotes: 2

Related Questions