Algorithms/Combinatorics and Heuristics
From charlesreid1
Notes
Skiena Chapter 7
This chapter covers the basic ideas of searching for solutions for combinatorial/permutation problems.
Three principal techniques covered:
 Random sampling (Monte Carlo method)
 Local search
 Simulated annealing
Combinatorial problems and solutions
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
 For each choice in a set of choices:
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
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
Generating Permutations
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
Constructing permutations:
 Permutations do not allow for duplicates
 If we fix a_1, we have n1 candidates for the second position, n2 for the third, etc. Total is:
 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
More Examples
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 19
 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.
Heuristic search
3 techniques covered here are:
 Random sampling (Monte Carlo method)
 Local search
 Simulated annealing
These three techniques have some common components that are required:
 Solution space representation  deciding how to represent the problem (e.g., when solving Traveling Salesperson Problem, deciding which nodes to visit, which have been visited)
 Cost function  a way to rank the quality of each solution
Random sampling
Random sampling/Monte Carlo:
 Solution space must be uniformly sampled
 This can be subtle/tricky
 See selction 14.414.7 in Skiena on generating permutations and combinations, etc.
 Basic traveling salesperson problem randomized solution:
for i in Nsamples: generate random solution calculate cost of solution if this costs less than best cost: keep this solution
When does random sampling work well?
 High proportion of acceptable solutions (e.g., prime numbers)
 No coherence to solution space (no way to gauge closeness to a solution)
This solution approach works terribly on the traveling salesperson problem, which has a sparse solution space.
Implementing Random Sampling
There are subtleties to how random sampling should be implemented  how the solution space should be sampled.
For example: suppose we have a graph with vertices, and we are selecting random pairs for vertex swaps:
For a set of vertices we are selecting randomly from the possible unordered pairs
Solution
 We cannot say,
i = rand_int(1, n1) j = rand_int(i+1,n)
This introduces bias in the random generator!
Possibility of selecting a random pair that is arbitrary, say , is given by:
The last term is the probability of getting the pair (p,q).
But now consider the random pair : in this case the probability of j being n is 100%.
which is different!
The real solution is to make both random selections unbiased, and throw out duplicate selections:
do i = random(1,n) j = random(1,n) while(i==j) swap(i,j)
Local Search
Local search methods:
 sometimes called greedy methods
 search for locally optimal solutions
 This can cause problems later, if the locally optimal solution is not a part of the globally optimal solution.
 Similar to a perturbation method, looking for small, limitedsize local steps that will lead to a better solution
 Can think of it like binary search in a convex space  a step in one direction or the other will always take you toward your solution
When to use local search, and why:
 Convex problem spaces lend themselves well to local search for solutions
 Cost of incremental changes to an existing solution can also be much cheaper relative to looking for brand new solutions
 If we have a large search space and a limited time budget, local search is the way to go
Simulated Annealing
Inspiration for simulated annealing from thermodynamics
Think about the search through solution space as a thermodynamic process, trying to reach minimum energy
The higher the temperature, the more random motions there are, the easier it is to transition to another state
Simulated annealing sets an initial temperature and a cooling schedule, and evaluates the probability of a random jump to a nearby solution as a function of the temperature and the cost difference between the two possible states.
More formally: we have a transition probability from state i to state j at some given temperature, which is given by an exponential decay function:
where is the Boltzmann constant, which is the gas constant divided by Avagadro's number:
In the case of simulated annealing, we replace the difference with the cost function C(s) associated with each of the two states, and we replace the constant k with an arbitrary constant.
Initially we start at a high temperature, where large jumps are more likely; as time goes on, we gradually decrease the temperature, allowing the solution to settle into a lowcost state.
For applying simulated annealing to combinatorial optimization, we use the cost function as the energy function.
Pseudocode:
def simulated_annealing(): create initial solution initialize temperature while solution still changing: for i in number of iterations: generate random transition s to s_j if C(s) > C(s_j): s = s_j else if exp( (C(s)C(s_j))/(k*T) ) > random(0,1): s = s_j reduce temperature return s
Cooling schedule:
 Regulates likelihood of selecting (locally) bad solutions
 Depends on a couple of parameters:
 initial temperature
 temperature decrement
 number of iterations inside T step
 acceptance criteria for state
 stopping criteria
Example problems where simulated annealing works well:
 Maximum cut (finding partitioning of graphs that cuts the most edges)
 Independent set (largest subgraphs in G with no edges containing both endpoints in S)
 Circuit board placement  minimizing aspect ratio, minimizing total wire length (rectangular modules r1, r2, ..., rn with dimensions Hi x Li and wires wij connecting the modules)
Skiena End of Chapter Questions
Skiena Chapter 7 Problem 14  String Permutations  write a function to find all permutations of the letters in a particular string. For example, "HELLO".
Examples and Applications
Project Euler provides fantastic examples of combinatoric problems that often have astronomical problem spaces that can be cleverly traversed much faster with a few tricks.
Project Euler Problem 501 is an excellent example of this.
Project Euler Problem 502 is another excellent combinatoric search question.
Related Pages
Notes from Knuth's Art of Computer Programming related to combinatorics and permutations:
Combinatorics Problems
Collected combinatorics problems across this wiki.
AOCP/Binomial Coefficients page:
 Art of Computer Programming, Section 1.2.5, Problem 36
 The Zeta Family picks a monogram
 Sum of binomial sequence
AOCP/Generating Functions page:
Flags
Algorithms Part of Computer Science Notes
Series on Algorithms
Algorithms/Sort · Algorithmic Analysis of Sort Functions · Divide and Conquer · Divide and Conquer/Master Theorem Three solid O(n log n) search algorithms: Merge Sort · Heap Sort · Quick Sort Algorithm Analysis/Merge Sort · Algorithm Analysis/Randomized Quick Sort
Algorithms/Search · Binary Search · Binary Search Modifications
Algorithms/Combinatorics · Algorithms/Combinatorics and Heuristics · Algorithms/Optimization · Divide and Conquer
Algorithms/Strings · Algorithm Analysis/Substring Pattern Matching
Algorithm complexity · Theta vs Big O Amortization · Amortization/Aggregate Method · Amortization/Accounting Method Algorithm Analysis/Matrix Multiplication
Estimation Estimation · Estimation/BitsAndBytes
Algorithm Practice and Writeups Project Euler · Five Letter Words · Letter Coverage

The Art of Computer Programming notes from reading Donald Knuth's Art of Computer Programming
Part of the 2017 CS Study Plan.
AOCP/Infinite Series · AOCP/Binomial Coefficients · AOCP/Multinomial Coefficients · AOCP/Harmonic Numbers · AOCP/Fibonacci Numbers
Volume 2: Seminumerical Algorithms
Volume 3: Sorting and Searching AOCP/Combinatorics · AOCP/Multisets · Rubiks Cube/Permutations
AOCP/Combinatorial Algorithms · AOCP/Boolean Functions · AOCP/Five Letter Words · Rubiks Cube/Tuples AOCP/Generating Permutations and Tuples

/