Skip to content

Heuristic Search

This page provides a brief introduction to heuristic search and its applications.

Definition

Heuristic search is a search algorithm that introduces a heuristic function on top of a standard search algorithm.

The role of the heuristic function is to evaluate each branch choice in the search based on existing information, thereby selecting branches. In simple terms, heuristic search analyzes both taking and not taking a branch, selecting the better solution or pruning invalid solutions.

Example Problem

Since the concept is quite abstract, we will explain it using an example problem.

「NOIP2005 Popularization Group」Herb Gathering

Problem summary: There are \(N\) types of items and a backpack with capacity \(W\). Each item has two attributes: weight \(w_i\) and value \(v_i\). The task is to select several items (each item can be chosen only once) to put into the backpack, maximizing the total value of the items in the backpack while ensuring the total weight does not exceed the backpack's capacity.

Solution Approach

We write a heuristic function \(f\) to prune all invalid \(0\) branches (i.e., remove a large number of useless "not take" branches).

The heuristic function \(f\) operates as follows:

When taking an item, we check if it exceeds the allowed volume (feasibility pruning). When not taking an item, we check whether the total value of all remaining items plus the current value is greater than the best solution found so far (optimality pruning).

Sample Code 
 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
32
33
34
35
36
37
38
39
40
41
42
43
#include <algorithm>
#include <iostream>
using namespace std;
constexpr int N = 105;
int n, m, ans;

struct Node {
  int a, b;  // a represents time, b represents value
  double f;
} node[N];

bool operator<(Node p, Node q) { return p.f > q.f; }

int f(int t, int v) {  // Calculate the maximum value of remaining items at current time
  int tot = 0;
  for (int i = 1; t + i <= n; i++)
    if (v >= node[t + i].a) {
      v -= node[t + i].a;
      tot += node[t + i].b;
    } else
      return (int)(tot + v * node[t + i].f);
  return tot;
}

void work(int t, int p, int v) {
  ans = max(ans, v);
  if (t > n) return;                         // Boundary condition: only n types of items
  if (f(t, p) + v > ans) work(t + 1, p, v);  // Optimality pruning
  if (node[t].a <= p) work(t + 1, p - node[t].a, v + node[t].b);  // Feasibility pruning
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> m >> n;
  for (int i = 1; i <= n; i++) {
    cin >> node[i].a >> node[i].b;
    node[i].f = 1.0 * node[i].b / node[i].a;  // f is the value-to-time ratio
  }
  sort(node + 1, node + n + 1);  // Sort by value-to-time ratio
  work(1, m, 0);
  cout << ans << '\n';
  return 0;
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用