Search Space Reduction

Search space reduction refers to techniques for pruning unnecessary branches in search algorithms like backtracking, branch and bound, A*, etc. This improves efficiency by narrowing the options explored.

Some common strategies are:

Domain propagation
Identifying inevitable failure
Memoization
Heuristics and bounds

Java - N queens search space pruning:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
void solveNQueens(int col, int[] queens) {

  if (col == N) {
    printSolution(queens);
  }

  for (int row = 0; row < N; row++) {
    if (isValid(row, col, queens)) {
      placeQueen(row, col, queens);
      solveNQueens(col+1, queens);
      removeQueen(row, col, queens); 
    }
  }
}

boolean isValid(int row, int col, int[] queens) {
  // Prune search if placement not valid
  return true; 
}

C++ - Branch and bound with cost lower bound:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
int optimize(Node node) {
  
  if (node.bound() >= bestCost) {
    return; // Prune  
  }

  if (node.isGoal()) {
    bestCost = node.cost(); 
  } else {
  
    for (Node child : node.expand()) {
      optimize(child);
    }
  }
} 

Python - Memoization in DP:

1
2
3
4
5
6
7
@cache
def fib(n):
  
  if n == 0 or n == 1:
    return n
  
  return fib(n-1) + fib(n-2) 

Pruning invalid branches and avoiding repeated work reduces the search space. This improves efficiency.

Search Space Reduction is a vital concept in computer algorithms where the goal is to minimize the area of search to find a specific element or fulfill a particular condition. This is done by employing a strategy that systematically eliminates a portion of the search space that is guaranteed not to contain the solution. By focusing only on the promising part of the search space, the algorithm can achieve significant efficiency gains. Search Space Reduction is commonly used in algorithms like Binary Search, Bisection Methods, and some optimization techniques.

Solution

Java

Using Binary Search as an example for Search Space Reduction:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1; // Reducing the search space to the right half
        else right = mid - 1; // Reducing the search space to the left half
    }

    return -1; // Target not found
}

C++

Binary Search in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1; // Reducing the search space to the right half
        else right = mid - 1; // Reducing the search space to the left half
    }

    return -1; // Target not found
}

Python

Binary Search in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1 # Reducing the search space to the right half
        else:
            right = mid - 1 # Reducing the search space to the left half

    return -1 # Target not found

In each of these implementations, the concept of Search Space Reduction is applied by focusing the search on either the left or the right half of the array, depending on the comparison of the target value with the middle element. This systematic reduction of the search space leads to a more efficient search process.