WikiGalaxy
Brute Force Technique
Introduction
The brute force technique is a straightforward approach to solving problems by trying all possible solutions and selecting the best one. Despite its simplicity, it can be inefficient for large datasets due to its exhaustive search nature.
Example 1: String Matching
String Matching Problem
Given a text and a pattern, the brute force method checks for the pattern at each position in the text, one by one.
public class BruteForceStringMatch {
public static int search(String text, String pattern) {
int n = text.length();
int m = pattern.length();
for (int i = 0; i <= n - m; i++) {
int j;
for (j = 0; j < m; j++) {
if (text.charAt(i + j) != pattern.charAt(j)) break;
}
if (j == m) return i; // Pattern found
}
return -1; // Pattern not found
}
}
Explanation
This algorithm iterates through the text, checking each position to see if the pattern matches. It has a time complexity of O(n*m), where n is the length of the text and m is the length of the pattern.
Example 2: Traveling Salesman Problem
Traveling Salesman Problem (TSP)
The brute force approach to TSP involves calculating the cost of every possible tour and selecting the minimum cost tour.
import java.util.*;
public class BruteForceTSP {
private static int calculateCost(int[][] graph, int[] path) {
int cost = 0;
for (int i = 0; i < path.length - 1; i++) {
cost += graph[path[i]][path[i + 1]];
}
cost += graph[path[path.length - 1]][path[0]];
return cost;
}
public static int findShortestPath(int[][] graph) {
int n = graph.length;
int[] path = new int[n];
for (int i = 0; i < n; i++) path[i] = i;
int minCost = Integer.MAX_VALUE;
do {
int cost = calculateCost(graph, path);
if (cost < minCost) minCost = cost;
} while (nextPermutation(path));
return minCost;
}
private static boolean nextPermutation(int[] path) {
int i = path.length - 2;
while (i >= 0 && path[i] >= path[i + 1]) i--;
if (i < 0) return false;
int j = path.length - 1;
while (path[j] <= path[i]) j--;
swap(path, i, j);
reverse(path, i + 1, path.length - 1);
return true;
}
private static void swap(int[] path, int i, int j) {
int temp = path[i];
path[i] = path[j];
path[j] = temp;
}
private static void reverse(int[] path, int start, int end) {
while (start < end) {
swap(path, start++, end--);
}
}
}
Explanation
This solution generates all permutations of the cities and calculates the cost of each tour. The minimum cost tour is selected. The time complexity is O(n!), making it impractical for large numbers of cities.
Example 3: Subset Sum Problem
Subset Sum Problem
The brute force method for the subset sum problem checks all subsets to see if any of them sum to a given target value.
public class BruteForceSubsetSum {
public static boolean isSubsetSum(int[] set, int n, int sum) {
if (sum == 0) return true;
if (n == 0) return false;
if (set[n - 1] > sum) return isSubsetSum(set, n - 1, sum);
return isSubsetSum(set, n - 1, sum) || isSubsetSum(set, n - 1, sum - set[n - 1]);
}
}
Explanation
This recursive solution checks each subset of the array to see if the sum equals the target. The time complexity is O(2^n), where n is the number of elements in the set.
Example 4: Knapsack Problem
0/1 Knapsack Problem
The brute force approach for the knapsack problem evaluates all combinations of items to maximize the total value without exceeding the weight capacity.
public class BruteForceKnapsack {
public static int knapSack(int W, int[] wt, int[] val, int n) {
if (n == 0 || W == 0) return 0;
if (wt[n - 1] > W) return knapSack(W, wt, val, n - 1);
else return Math.max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1),
knapSack(W, wt, val, n - 1));
}
}
Explanation
This recursive solution considers each item, deciding to include it or not, and computes the maximum value achievable. The time complexity is O(2^n).
Example 5: Permutation Generation
Generating All Permutations
The brute force method for permutation generation involves recursively generating all possible permutations of a given list of items.
import java.util.*;
public class BruteForcePermutations {
public static void permute(int[] arr, int l, int r) {
if (l == r) {
System.out.println(Arrays.toString(arr));
} else {
for (int i = l; i <= r; i++) {
swap(arr, l, i);
permute(arr, l + 1, r);
swap(arr, l, i);
}
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
Explanation
This recursive solution swaps elements to generate all permutations of the array. The time complexity is O(n!), where n is the number of elements in the array.
