Dynamic Programming Algorithms ::

Backtracking ::

The idea of backtracking is to search for the solution step by step. We therefore travers through a set of partial solutions, extend it with a new possibility, check its validity and repeat the process. If at any point we find an invalid choice, we step back until we hav e a valid solution and start searching for the next valid entry again.

As pseudo code it might look like ::


Start with some problem P 0  
Let S = {P 0 }, the set of active subproblems  
Repeat while S is nonempty:  
	choose a subproblem P ∈ S and remove it from S  
	expand it into smaller subproblems P 1 , P2 , . . . , P k  
	For each P i :  
		If test(P i ) succeeds: halt and announce this solution  
		If test(P i ) fails: discard P i  
		Otherwise: add P i to S  
Announce that there is no solution

the routine Test(Pi) has three possible outcomes:

  1. the current subproblem is a valid solution, we don’t need to search any further
  2. The current subproblem cannot lead to a valid solution, prune it
  3. we cannot say anything and need to continue –> until validity is able to be checked.

Depending on the data structure we use to store the subproblems, we have different strategies to move through the whole tree. It could be a stack, queue or similar.

Backtracking Summary ::

Backtracking is a systematic way to look at the whole search space :: We are organizing the search space as a tree. We are able to prune ==whole branches== -> whenever we are sure that the solution of that branch is not correct at all and thus all preceeding answer will not be either.

In the worst case, we still have to look at each leaf, so the worst case running time is often very bad. But hopefully, the empirical running time on many instances is better –>> worst cases are rare anyway!

We are guaranteed to find a correct solution at the end.

Backtracking with Eight queens problem ::

Looking at [[111.99_algo_DevelopingDynamicProgamming#Eight queens problem|EIght queens problem]] again ::

Our previous implementation was to simply place 8 Queens at once, checking whether the placement is valid or not. To improve the solution and decrease the amount of computation we could instead place them step by step, checking validity at each step and advance further from there or take another step and check this one - goes on and on.

This principle of taking a path until we either found a solution or flaw and reverting back to the previous valid solution to start fro again, is called ==backtracking==

We can observe the problem of Eight queens as a tree structure ::

  • our root is an empty solution.
  • inner vertices = placements of some queens
  • leafs = placement of all quens.

An exhaustive search would look at all leafs of the tree The idea here now is, that we can prune many of the branches much earlier already, because we know they are not possible.

![[Pasted image 20230113133630.png]]

Now the idea for backtracking would be ::

  • Perform a systematic depth first search on the solution tree
  • Whenever a partial solution is invalid, don’t proceed deeper into that branch - we prune it / cut it off

the key ingredient here :: a fast “testing component” checking whether partial solution is valid or not.

Backtracking for SAT ::

Branch and Bound

Branch and bound defines a variant of backracking that can be used for optimization problems.

read [[111.99_algo_branchNBound|here]]