Algorithms/Combinatorics and Heuristics

Notes

Skiena Chapter 7

This chapter covers the basic ideas of searching for solutions for combinatorial/permutation problems

Backtracking:

• Backtracking as example of combinatorial search (e.g., with N Queens problem you are searching among a space of possible configurations for a solution that satisfies the given constraints)
• Basic skeleton given for a backtracking method:

backtrack_dfs(A,k):
	if A = (a1, a2, ..., ak) is solution:
		process solution
	else:
		k = k + 1
		compute Sk
		while Sk != null set, do:
			ak = element of Sk
			Sk = Sk - ak
			backtrack_dfs(A,k)

Or, to express in a more terse way:

• Base case: found a solution
• Recursive case:
  • For each choice in a set of choices:
    • Make a choice
    • Explore the consequences
    • Unmake the choice
    • Move on to the next choice

A few notes on his program:

• new array each time, inside each method, so set of possible solutions is not passed around - copy is created so free to modify/not restore
• Stubs used fror method calls like processing solution, making move, unmaking move - this enables application of the same function to different problems

Example: Construct all possible subsets

• Each element doubles the number of subsets that can be created
• Number of subsets with 1 element in the set: 2 subsets (empty/full)
• Number of subsets with 2 elements in the set: 4 subsets
• Number of subsets with n elements in the set: 2^n subsets

When solving, the main question is, how do you represent a set?

Example:

• Checking membership of an element in a set
• Can use bit vector - an array of booleans - indicating whether an element is a member of a particular set or not
• The order in which sets are constructed depends on the set S construction procedure, called above

Constructing permutations:

• Permutations do not allow for duplicates
• If we fix a_1, we have n-1 candidates for the second position, n-2 for the third, etc. Total is:

$ n! = \prod_{j=1}^{n} j $

• utilize this to construct solution representations:
  • element i of an array can be any eleent that has not already appearedd
• complicated bit vector solution - basically, it says, who's in this permutation - then it adds items that aren't already in the solution to the new permutations

Shortest path:

• Again, a bit complicated with the logic details, but basically:
• Start at node S
• Move to next node ni if it is on the graph and not part of hte solution already
• Repeat

Sudoku puzzle solution:

• backtracking solution
• elements of the solution are the open squares, each of which has coordinates (i,j) and a set of possible digits that can go in that square 1-9
• We know the set of feasible digits are those that do not appear in row i or column j or the local 3x3 sector
• Soltion vector: one integer per position
• To store coordinate (i,j), use a separate array of point (x,y) structs
• Also have a board struct - stores a matrix of board contents as int[][], and a free count (open nuber of squares), and a move array of points
• to pick the next candidate:
  • Pick the next open square to fill
  • identify candidate solutions for that square
  • IMPORTANT: These two routines have a HUGE impact on the runtime!!!
• Then, given a coordinate x and y and a board, if possible, increase the number of andidates
• Make a move funtion
• Unmake a move function (both of these modify the move array)
• Solution check method - are there any open squares on the board?
• process solution: print board, set flag FINISHED to true

Two BIG improvements can be made here:

• Improving the selection of the next square - by carefully picking the next square to solve, we can reduce the search space and tackle the easiest problems first
• Improving the possible values that we are considering

Improving the next square selection procedure: two options

• Local count - disallows candidates that appear in row i, row j (this is the "plain vanilla" default approach)
• Look ahead - check if there are any other squares where making our choice would lead to ZERO candidates; if so, eliminate choice as a possible solution

Using the worst of both to solve a sudoku puzzle can take up to 1M function calls, while the best of both can solve with 50 or so.