

启发式搜索

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;
}

---

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论