Prune and Search Method

The prune and search method refers to optimizing backtracking search algorithms by aggressively pruning branches that cannot lead to solutions.

It involves two phases:

Pruning - Before exploring a branch, prune it if some condition proves it cannot lead to a solution.
Search - If not pruned, explore the branch through standard backtracking search.

This pruning eliminates branches that search would have explored.

Java - N Queens prune and search:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
boolean solveNQueens(int col, boolean[] cols, boolean[] diag1, boolean[] diag2) {

  if (col == N) 
    return true; // Found solution
  
  for (int row = 0; row < N; row++) {
    if (isSafe(row, col, cols, diag1, diag2)) {
      placeQueen(row, col, cols, diag1, diag2);  
      if (solveNQueens(col+1, cols, diag1, diag2)) {
        return true;
      }
      removeQueen(row, col, cols, diag1, diag2);
    }
  }

  return false;
}

boolean isSafe(int row, int col, boolean[] cols, boolean[] diag1, boolean[] diag2) {
  // Prune if placement not safe
  return true; 
}

C++ - Sudoku solver pruning:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
bool solveSudoku(int n, int grid[9][9]) {

  for (int row = 0; row < n; row++) {
    for (int col = 0; col < n; col++) {
      if (grid[row][col] == 0) {
        
        for (int num = 1; num <= 9; num++) { 
          
          if (isValid(grid, row, col, num)) {
            grid[row][col] = num;

            if (solveSudoku(grid, n)) {
              return true;
            }
            grid[row][col] = 0;
          }
        }
        return false;
      }
    }
  }
  return true; 
}  

bool isValid(int grid[9][9], int row, int col, int num) {
  // Prune invalid placements
  return true; 
}

Python - General prune and search:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def solve(state):
  
  if is_goal(state):
    return True

  for child in expand(state):
    
    if is_viable(child):
      if solve(child):
        return True

  return False

def is_viable(state):
  # Pruning logic
  return True 

Prune and search reduces wasteful exploration by pruning provably bad branches before search.

The Prune and Search Method is an algorithmic technique used to efficiently solve problems by iteratively reducing the search space. At each step, the algorithm “prunes” away a portion of the input that is guaranteed not to contain the solution, leaving a smaller set of possibilities to search. The technique is particularly useful in optimization and search problems.

Example Code in Java

Here is an example to find the median in an unsorted array using the Prune and Search Method.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class PruneAndSearch {
    public static int findMedian(int[] arr) {
        return findMedian(arr, 0, arr.length - 1, (arr.length + 1) / 2);
    }

    private static int findMedian(int[] arr, int l, int r, int k) {
        if (l == r) {
            return arr[l];
        }
        int pivot = arr[(l + r) / 2];
        int i = l, j = r;
        while (i <= j) {
            while (arr[i] < pivot) i++;
            while (arr[j] > pivot) j--;
            if (i <= j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++; j--;
            }
        }
        if (l <= k && k <= j) return findMedian(arr, l, j, k);
        if (i <= k && k <= r) return findMedian(arr, i, r, k);
        return arr[j + 1];
    }

    public static void main(String[] args) {
        int[] arr = {3, 6, 2, 4, 7};
        System.out.println(findMedian(arr));
    }
}

Example Code in C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <vector>
using namespace std;

int findMedian(vector<int>& arr, int l, int r, int k) {
    if (l == r) {
        return arr[l];
    }
    int pivot = arr[(l + r) / 2];
    int i = l, j = r;
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            swap(arr[i], arr[j]);
            i++; j--;
        }
    }
    if (l <= k && k <= j) return findMedian(arr, l, j, k);
    if (i <= k && k <= r) return findMedian(arr, i, r, k);
    return arr[j + 1];
}

int main() {
    vector<int> arr = {3, 6, 2, 4, 7};
    cout << findMedian(arr, 0, arr.size() - 1, (arr.size() + 1) / 2) << endl;
}

Example Code in Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def find_median(arr, l, r, k):
    if l == r:
        return arr[l]
    pivot = arr[(l + r) // 2]
    i, j = l, r
    while i <= j:
        while arr[i] < pivot:
            i += 1
        while arr[j] > pivot:
            j -= 1
        if i <= j:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
            j -= 1
    if l <= k <= j:
        return find_median(arr, l, j, k)
    if i <= k <= r:
        return find_median(arr, i, r, k)
    return arr[j + 1]

arr = [3, 6, 2, 4, 7]
print(find_median(arr, 0, len(arr) - 1, (len(arr) + 1) // 2))

In each of these examples, the function findMedian employs Prune and Search to find the median of an array in (O(n)) time, where (n) is the length of the array. It does so by repeatedly partitioning the array around a pivot and discarding the section that doesn’t contain the median.

The prune and search method is a technique for solving optimization problems by iteratively dividing the search space into two parts: the promising one, which contains the optimal value and is recursively searched, and the second part without optimal value, which is pruned (thrown away).

This paradigm is very similar to well-known divide and conquer algorithms. The main difference is that in prune and search, we are not just dividing the search space in half, but we are also discarding a fraction of the input elements that we know cannot contain the optimal solution. This can lead to a significant speedup in the running time of the algorithm.

One example of a problem that can be solved using the prune and search method is the knapsack problem. In the knapsack problem, we are given a set of items, each with a weight and a value, and a capacity W. We want to find the subset of items that has the maximum total value and that fits within the knapsack.

One way to solve the knapsack problem is to use a brute-force approach. We can enumerate all possible subsets of items and then check each one to see if it fits within the knapsack. This approach has a time complexity of O(2^n), where n is the number of items.

Another way to solve the knapsack problem is to use the prune and search method. We can start by sorting the items by weight. We then consider the items in decreasing order of weight. For each item, we check to see if it fits within the knapsack. If it does, we add it to the knapsack. If it does not, we prune it (throw it away). We continue this process until we have either found a subset of items that fits within the knapsack or we have pruned all of the items. This approach has a time complexity of O(n*W), where n is the number of items and W is the capacity of the knapsack. This is significantly faster than the brute-force approach, especially when the number of items is large.