Backtracking with Pruning
What is pruning?
If you look up "pruning" on Google Images, there is what you get:
It literally means cutting branches off a tree.
In our case, we want to cut branches off our state-space tree. The fewer branches, the faster the algorithm.
When do we want to prune a branch?
When it's clear that going into that branch would not yield a valid final state. This happens when the problem comes with one or more constraints, and the branches violates those contraints.
Here we introduce an update template.
1function dfs(start_index, path): 2if is_leaf(start_index): 3 report(path) 4 return 5for edge in get_edges(start_index): 6 # prune if needed 7 if not is_valid(edge): 8 continue 9 path.add(edge) 10 # increment start_index 11 dfs(start_index + len(edge), path) 12 path.pop()
The differences are
- we added a pruning step that checks if a branch is valid using
- we increment
start_indexby a variable size instead of always 1
Got a question? Ask the Teaching Assistant anything you don't understand.