backtracking-algorithms

课 Progress

0% Complete

Backtracking Algorithms

What is Backtracking?

Backtracking is a technique that is used when you don’t have enough information to find a solution to a problem or if you have many possible ways of solving a problem
It will therefore explore all possible paths in the search space to determine if these come to dead ends
It will build up partial solutions to a large problem incrementally and then if the solution fails at some point, the partial solutions are abandoned and the search begins again at the last potentially successful point
Backtracking is ideal if you are trying to solve logic problems, however, is not ideal for solving strategic problems
For example, backtracking can be used to navigate around a maze to move forward until a wall is hit (dead end), then backtrack to try another route

Example use

Backtracking can be particularly useful when traversing data structures such as trees or graphs as these have multiple paths that can lead to the desired solution
In a binary search tree, backtracking helps to return from leaf nodes (dead ends) so that other subtrees can be explored

Using backtracking to solve problems

Benefits	Drawbacks
It is guaranteed to find a solution if one exists.	Is not ideal for solving strategic problems.
It is easy to implement and use.	Depending on the problem that you are trying to solve, it can have a high time complexity.
It can be be applied to a variety of logic problems.	If there are lots of different solutions to a problem, it is not always the most efficient method.
It will comprehensively explore all possible paths to the desired solution.	It can consume a lot of memory.
	Although it may find a solution to the problem, the solution may not always be the best solution available.
	It will often require a complete search of the entire solution space.

Worked Example

You are developing a maze-solving application where a user-controlled character needs to navigate from the start point to the end point. The maze contains several dead ends and multiple pathways to reach the destination.

Describe how backtracking can be used to solve this problem. You should include the steps involved and any advantages or limitations of using backtracking for this scenario.

How to answer this question:

Introduction: Explain what is meant by the term ‘backtracking’ and why it’s suitable for solving maze problems
Algorithm Steps: Give the steps the backtracking algorithm would follow to solve the maze problem
Advantages: Give the advantages of using backtracking
Limitations: Give any limitations of using backtracking

Answer:

Backtracking is an algorithmic approach that builds a solution incrementally. It’s ideal for solving maze problems because it explores each path until it reaches a dead end and then retreats (backtracks) to another pathway to explore. The backtracking algorithm would start at the maze entrance and move step-by-step towards the exit, marking visited areas of the maze. Upon reaching a dead end, the algorithm would backtrack to the last unvisited branch.

The primary advantage of backtracking is that it guarantees a solution if one exists. It’s efficient and can be easily implemented. However, backtracking can be slow for complex or large maze problems and it may not always find the best solution available. Backtracking offers a reliable, straightforward way to solve maze problems despite its limitations.

Acceptable answer you could have given instead:

Backtracking is good for solving maze problems as it can find a path from start to finish. The algorithm starts at the entrance and moves through the maze, backtracking when it hits a wall (dead end) until it finds the exit. This method will find a solution if one is available, however, it may take longer for bigger mazes. Backtracking is a suitable method for solving mazes, although it may have some downsides, like speed and poor time complexities.

Computer-Science-A-level-Ocr

backtracking-algorithms