Facebook Pixel

You are on level: Student

0%
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section
Expand section

Backtracking with Pruning

What is pruning?

If you look up "pruning" on Google Images, this 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 runs.

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.

Template v1.1

Here we introduce an updated template.

function dfs(start_index, path):
if is_leaf(start_index):
   report(path)
   return
for edge in get_edges(start_index):
  # prune if needed
  if not is_valid(edge):
    continue
  path.add(edge)
  # increment start_index
  dfs(start_index + len(edge), path)
  path.pop()

The differences are

  • we added a pruning step that checks if a branch is valid using is_valid
  • we increment start_index by a variable size instead of always 1
Invest in Yourself
Your new job is waiting. 83% of people that complete the program get a job offer. Unlock unlimited access to all content and features.
Go Pro