~/Backtracking

Brandon Rozek

Photo of Brandon Rozek

PhD Student @ RPI studying Automated Reasoning in AI and Linux Enthusiast.

This algorithm tries to construct a solution to a problem one piece at a time. Whenever the algorithm needs to decide between multiple alternatives to the part of the solution it recursively evaluates every option and chooses the best one.

How to Win

To beat any non-random perfect information game you can define a Backtracking algorithm that only needs to know the following.

PlayAnyGame(X, player)
  if player has already won in state X
    return GOOD
  if player has lost in state X
    return BAD
  for all legal moves X -> Y
    if PlayAnyGame(y, other player) = Bad
      return GOOD
  return BAD

In practice, most problems have an enormous number of states not making it possible to traverse the entire game tree.

Subset Sum

For a given set, can you find a subset that sums to a certain value?

SubsetSum(X, T):
  if T = 0
    return True
  else if T < 0 or X is empty
    return False
  else
    x = any element of X
    with = SubsetSum(X \ {x}, T - x)
    without = SubsetSum(X \ {x}, T)
    return (with or without)

X \ {x} denotes set subtraction. It means X without x.

ConstructSubset(X, i, T):
  if T = 0
    return empty set
  if T < 0 or n = 0
    return None
  Y = ConstructSubset(X, i - 1, T)
  if Y does not equal None
    return Y
  Y = ConstructSubset(X, i - 1, T - X[i])
  if Y does not equal None
    return Y with X[i]
  return None

Big Idea

Backtracking algorithms are used to make a sequence of decisions.

When we design a new recursive backtracking algorithm, we must figure out in advance what information we will need about past decisions in the middle of the algorithm.