Definition
Search algorithms systematically explore state spaces to find optimal solutions or count valid configurations through exhaustive enumeration. This approach leverages understanding of state transitions to navigate possible states.
Search Algorithm Applications
When explicit enumeration becomes infeasible (e.g., permutations for n=100 or unknown graph structures), search algorithms provide a systematic approach. Unlike simple nested loops for small cases, search handles complex state transitions efficiently.
Depth-First Search (DFS)
DFS explores paths completely before backtracking, forming a last-in-first-out (LIFO) strutcure equivalent to a stack. It recursively explores the first available neighbor at each node:
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 105;
int grid[MAX][MAX], memo[MAX][MAX];
int dr[] = {-1, 0, 1, 0}, dc[] = {0, 1, 0, -1};
int rows, cols;
int explore(int r, int c) {
if (memo[r][c]) return memo[r][c];
int max_depth = 1;
for (int i = 0; i < 4; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] < grid[r][c]) {
max_depth = max(max_depth, explore(nr, nc) + 1);
}
}
return memo[r][c] = max_depth;
}
int main() {
cin >> rows >> cols;
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
cin >> grid[i][j];
int max_path = 0;
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
max_path = max(max_path, explore(i, j));
cout << max_path << endl;
return 0;
}
Breadth-First Search (BFS)
BFS explores nodes level-by-level using a first-in-first-out (FIFO) queue structure. It processes all immediate neighbors before deeper nodes:
#include <iostream>
#include <queue>
#include <iomanip>
using namespace std;
const int SIZE = 405;
int moves_r[] = {1, 2, 2, 1, -1, -2, -2, -1};
int moves_c[] = {2, 1, -1, -2, -2, -1, 1, 2};
int main() {
int n, m, sr, sc;
cin >> n >> m >> sr >> sc;
sr--; sc--;
int dist[SIZE][SIZE];
memset(dist, -1, sizeof(dist));
queue<pair<int, int>> q;
q.push({sr, sc});
dist[sr][sc] = 0;
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
for (int i = 0; i < 8; i++) {
int nr = r + moves_r[i], nc = c + moves_c[i];
if (nr >= 0 && nr < n && nc >= 0 && nc < m && dist[nr][nc] == -1) {
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
cout << left << setw(5) << dist[i][j];
cout << endl;
}
return 0;
}
Algorithm Selection
DFS is preferable when backtracking through known paths is required, while BFS excels at finding shortest paths to target states.
Optimization Techniques
Basic Pruning
- Optimality pruning: Abandon paths when current cost exceeds known solution
- Feasibility pruning: Terminate invalid state explorations
- Binary search integration: Reduce logarithmic complexity in ordered data searches
#include <bits/stdc++.h>
using namespace std;
const int MAX_STICKS = 65;
int pieces[MAX_STICKS], next_same[MAX_STICKS], n, target_length;
bool used[MAX_STICKS];
bool assemble(int idx, int remaining, int segments) {
if (remaining == 0) {
if (segments == target_length) return true;
for (int i = 0; i < n; i++) {
if (!used[i]) {
used[i] = true;
if (assemble(i, pieces[i], segments + 1)) return true;
used[i] = false;
}
}
return false;
}
int low = idx, high = n;
while (low < high) {
int mid = (low + high) / 2;
if (pieces[mid] <= remaining) high = mid;
else low = mid + 1;
}
for (int i = low; i < n; i++) {
if (!used[i] && pieces[i] <= remaining) {
used[i] = true;
if (assemble(i, remaining - pieces[i], segments)) return true;
used[i] = false;
if (remaining == pieces[i]) return false;
i = next_same[i];
}
}
return false;
}
int main() {
int total = 0, cnt = 0;
cin >> n;
for (int i = 0; i < n; i++) {
int len; cin >> len;
if (len > 50) continue;
pieces[cnt++] = len;
total += len;
}
n = cnt;
sort(pieces, pieces + n, greater<int>());
for (int len = pieces[0]; len <= total/2; len++) {
if (total % len != 0) continue;
target_length = total / len;
memset(used, 0, sizeof(used));
used[0] = true;
if (assemble(0, len - pieces[0], 1)) {
cout << len << endl;
return 0;
}
}
cout << total << endl;
return 0;
}
Meet-in-the-Middle
Divides search space into two halves, reducing O(n^m) to O(n^{m/2}) complexity:
#include <bits/stdc++.h>
using namespace std;
const int MAX_HALF = 1 << 25;
long long prices[40], left_sum[MAX_HALF];
int n, mid, cnt_left;
void first_half(long long cost, int pos) {
if (cost > n) return;
if (pos > mid) {
left_sum[cnt_left++] = cost;
return;
}
first_half(cost, pos + 1);
first_half(cost + prices[pos], pos + 1);
}
int main() {
cin >> cnt_left >> n;
mid = (cnt_left + 1) / 2;
for (int i = 0; i < cnt_left; i++) cin >> prices[i];
cnt_left = 0;
first_half(0, 0);
sort(left_sum, left_sum + cnt_left);
long long total = 0, current = 0;
function<void(int)> second_half = [&](int pos) {
if (pos >= cnt_left) {
total += upper_bound(left_sum, left_sum + cnt_left, n - current) - left_sum;
return;
}
second_half(pos + 1);
current += prices[pos];
if (current <= n) second_half(pos + 1);
current -= prices[pos];
};
second_half(mid);
cout << total << endl;
return 0;
}
Memoization
Caches state results to avoid redundant computations, often resembling dynamic programming solutions:
#include <bits/stdc++.h>
using namespace std;
const int MAX_ITEMS = 105;
int weights[MAX_ITEMS], values[MAX_ITEMS], cache[MAX_ITEMS][MAX_ITEMS];
int num_items, capacity;
int optimize(int idx, int remaining) {
if (idx == num_items) return 0;
if (cache[idx][remaining] != -1) return cache[idx][remaining];
int skip = optimize(idx + 1, remaining);
int take = (remaining >= weights[idx]) ?
values[idx] + optimize(idx + 1, remaining - weights[idx]) : 0;
return cache[idx][remaining] = max(skip, take);
}
int main() {
cin >> capacity >> num_items;
for (int i = 0; i < num_items; i++)
cin >> weights[i] >> values[i];
memset(cache, -1, sizeof(cache));
cout << optimize(0, capacity) << endl;
return 0;
}
A* Algorithm
Uses heuristic-guided best-first search with priority queues. Heuristic function h(x) must satisfy h(x) ≤ h*(x) where h*(x) is actual cost to goal:
#include <iostream>
#include <queue>
#include <set>
#include <cmath>
using namespace std;
const int DIM = 3;
struct State {
int board[DIM][DIM];
int moves;
bool operator<(const State& other) const {
for (int i = 0; i < DIM; i++)
for (int j = 0; j < DIM; j++)
if (board[i][j] != other.board[i][j])
return board[i][j] < other.board[i][j];
return false;
}
};
int estimate(const State& s) {
int diff = 0;
int target[DIM][DIM] = {{1,2,3},{8,0,4},{7,6,5}};
for (int i = 0; i < DIM; i++)
for (int j = 0; j < DIM; j++)
if (s.board[i][j] != target[i][j]) diff++;
return diff;
}
int main() {
State initial{};
for (int i = 0; i < DIM; i++)
for (int j = 0; j < DIM; j++) {
char c; cin >> c;
initial.board[i][j] = c - '0';
}
initial.moves = 0;
priority_queue<pair<int, State>> pq;
set<State> visited;
pq.push({-estimate(initial), initial});
visited.insert(initial);
const int dr[] = {-1, 0, 1, 0}, dc[] = {0, 1, 0, -1};
while (!pq.empty()) {
auto [priority, state] = pq.top();
pq.pop();
priority = -priority;
if (priority - state.moves == 0) {
cout << state.moves << endl;
return 0;
}
int r0, c0;
for (r0 = 0; r0 < DIM; r0++)
for (c0 = 0; c0 < DIM; c0++)
if (state.board[r0][c0] == 0) goto found;
found:
for (int d = 0; d < 4; d++) {
int nr = r0 + dr[d], nc = c0 + dc[d];
if (nr < 0 || nr >= DIM || nc < 0 || nc >= DIM) continue;
State next_state = state;
swap(next_state.board[r0][c0], next_state.board[nr][nc]);
next_state.moves++;
if (visited.count(next_state)) continue;
visited.insert(next_state);
int cost = next_state.moves + estimate(next_state);
pq.push({-cost, next_state});
}
}
return 0;
}