THE CONCEPT OF BACKTRACKING

Let’s imagine you are trapped in a complex maze and trying to solve it by choosing different paths leading to dead ends and then forcing you to backtrack and try again. This trial and error method is similar to backtracking algorithm use in computer science.

The backtracking can be define as the problem solving algorithm technique that involves finding a solution by incrementing and trying different paths and undoing them if they lead to dead end. Backtracking name itself suggests that we are going back and coming forward; if it satisfies the condition, then return success, else we go back again. It is used to solve a problem in which a sequence of objects is chosen from a specified set so that the sequence satisfies some criteria.

Use of Backtracking:

 It is commonly used in situations where you need to explore multiple possibilities to solve a problem, like:-

• Solving Puzzles:

Backtracking is used in solving puzzles such as sudoku, crossword or word search. A backtracking algorithm can solve by trying different options for each element, checking if they are valid, and moving on to the next element. If an options leads to a dead end, then algorithm can backtrack to previous element and try another option, until it finds solution.

 

• Generating permutations and combinations:

Backtracking Algorithms is use in generating all possible permutations and combinations of a given set of items.

 

• Finding Paths and cycles:

Backtracking Algorithms can also be used to find paths and cycles in graphs, which are structures that consist of nodes and edges.

 

• Optimizing resources and costs:

Another use case for backtracking algorithms is optimizing the allocation of resources or the minimization of costs in various scenarios, such as scheduling, assignment, or packing problems.

 

• Searching for patterns and matches:

Backtracking algorithms can also be used to be search for patterns and matches in strings, which are sequences of characters.

Types of Backtracking

Backtracking is categorized into three types are as follows:-

• Decision Problems

In this we search for feasible solution.

• Optimization Problems

In this we search for best solution.

• Enumeration Problems

In this we find set of all possible feasible solutions to the problems of this type.

 It How Does Works? 

This is a graphic representation of the Backtracking algorithm. The representation is a tree, its first node represents the initial state of the algorithm. The first node has tree child nodes, each one of them with two nodes.

Keep in mind that the Backtracking algorithm always starts from the top, and goes from the left first.

 

 

In this representation we can see the algorithm working, supposing that we want to find the string "123", the scanner will advance to the next node (C1 or Checkpoint 1) if the character found is equal to 1, and back off to try with another node if it is not. This process will be recursively repeated many times, until the algorithm match the string "123".

 

Application of Backtracking:

 Here are five different fields in which backtracking can be used to solve problems:

Computer Science: Backtracking is commonly used in computer science to solve a wide range of problems, including search algorithms, constraint satisfaction problems, and combinatorial optimization problems.

Mathematics: Backtracking can be used in mathematics to solve a variety of problems, including those related to graph theory, number theory.

Artificial Intelligence: Backtracking is a key technique used in artificial intelligence to solve problems related to planning, decision-making, and optimization. Examples include path finding, route planning, and constraint satisfaction problems in robotics and other AI applications.

Natural Language Processing: Backtracking can be used in natural language processing to solve problems related to parsing and semantic analysis.

 

Name: Ritika S. Govindwar

Branch: SY-CSE(AI)

Roll no: 34