Heuristic Search

Introduction

In simple terms, heuristic search is a technique that analyzes the results of both performing and not performing operations, and select a better solution or remove the invalid solutions.

Since the concept is too abstract, we will take a few examples to explain.

Sample problem 「NOIP2005 general level」Gather herbs (original link in Chinese)

Problem: There are N items and a backpack with a capacity of W . Each item has two attributes: weight w_i and value v_i . It is required to select several items (each item can only be selected once) to put in the backpack to maximize the total value of the items while the total weight not exceeding the capacity of the backpack.

Code

We write an evaluation function f that can cut off all invalid 0 branches (that is, pruning myriad of useless branches without selecting).

The process of the evaluation function f is as follows:

When taking an item, check whether it exceeds the capacity (feasible pruning).

When not taking it, check whether the sum of the value of remaining medicine plus existing value is greater than the optimal solution found so far (optimal pruning).

Sample code

#include <algorithm>
#include <cstdio>
using namespace std;
const 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) {
  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;
  if (f(t, p) + v > ans) work(t + 1, p, v);
  if (node[t].a <= p) work(t + 1, p - node[t].a, v + node[t].b);
}

int main() {
  scanf("%d %d", &m, &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d %d", &node[i].a, &node[i].b);
    node[i].f = 1.0 * node[i].b / node[i].a;
  }
  sort(node + 1, node + n + 1);
  work(1, m, 0);
  printf("%d\n", ans);
  return 0;
}
buildLast update and/or translate time of this article，Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article OI-wiki
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.

Comments