Exhaustive Search

Ed

Table of contents

1. Election Simulator
2. Enumeration

Election Simulator

The President of the United States is not elected by a popular vote, but by a majority vote in the Electoral College. Each state, plus DC, gets some number of electors in the Electoral College, and whoever they vote in becomes the next President. Right before the 2016 election, NPR reported that 23% of the popular vote would be sufficient to win the election, based on the 2012 election data. They arrived at this number by looking at states with the highest ratio of electoral votes to voting population. This was a correction to their originally-reported number of 27%, which they got by looking at what it would take to win the states with the highest number of electoral votes. But the optimal strategy turns out to be neither of these and instead uses an unlikely coalition of small and large states.

How might we identify the coalition of states with the minimum possible popular votes needed to win the Electoral College? So far, all of our programming experience has focused on solving problems that have only one solution (result or output) associated with each input. Sometimes, that solution is a collection type, but even a collection of data still represents only one solution, one coalition of states out of all of the possible combinations. Even generative recursive algorithms still only produce one solution per input, though the algorithm generating them uses randomness.

Enumeration

In this lesson, we’ll explore special application of recursion to explore a solution space of many possible solutions. Consider the recursive algorithm fourAB that prints out all strings of length 4 composed only of the letters “a” and “b”.

Exhaustive search (also known as brute-force search) is a recursive problem-solving technique that works by systematically enumerating all solutions in the solution space. To enumerate the solutions to fourAB, we can plot the solutions in a table.

By arranging the solutions in an organized structure, we can identify recursive partial solutions.

• The left two columns are associated with prepending an “a” to the start of all a/b strings of length 3.
• The right two columns are associated with prepending a “b” to the start of all a/b strings of length 3.

Exhaustive search recursive algorithms differ from typical recursive algorithms. Unlike structurally-recursive algorithms that break down their inputs into subproblems, exhaustive search algorithms work backwards by starting with empty data and generating larger and larger partial solutions until a complete solution is obtained.

Outline for defining exhaustive search algorithms

1. Initiate the recursive algorithm with empty data.
2. Recursively generate larger partial solutions.
3. At each base case, report the completed solution.

public static void main(String[] args) {
    fourAB("");
}

public static void fourAB(String soFar) {
    if (soFar.length() == 4) {
        System.out.println(soFar);
    } else {
        fourAB(soFar + "a");
        fourAB(soFar + "b");
    }
}

The following (partial) recursion tree shows each decision (diamond) made during the execution of the first branch of fourAB.

1. Starting with the empty string, add an “a”.
2. From the string “a”, add another “a”.
3. From the string “aa”, add another “a”.
4. From the string “aaa”, add another “a”.
5. Since “aaaa” is length 4, print “aaaa”.
6. Return back to “aaa”, add a “b”.
7. Since “aaab” is length 4, print “aaab”.
8. …