啓發式搜索

本頁面將簡要介紹啓發式搜索及其用法。

定義

啓發式搜索（英文：heuristic search）是一種在普通搜索算法的基礎上引入了啓發式函數的搜索算法。

啓發式函數的作用是基於已有的信息對搜索的每一個分支選擇都做估價，進而選擇分支。簡單來説，啓發式搜索就是對取和不取都做分析，從中選取更優解或刪去無效解。

例題

由於概念過於抽象，這裏使用例題講解。

「NOIP2005 普及組」採藥

題目大意：有 \(N\) 種物品和一個容量為 \(W\) 的揹包，每種物品有重量 \(w_i\) 和價值 \(v_i\) 兩種屬性，要求選若干個物品（每種物品只能選一次）放入揹包，使揹包中物品的總價值最大，且揹包中物品的總重量不超過揹包的容量。

解題思路

我們寫一個估價函數 \(f\)，可以剪掉所有無效的 \(0\) 枝條（就是剪去大量無用不選枝條）。

估價函數 \(f\) 的運行過程如下：

我們在取的時候判斷一下是不是超過了規定體積（可行性剪枝）；在不取的時候判斷一下不取這個時，剩下的藥所有的價值 + 現有的價值是否大於目前找到的最優解（最優性剪枝）。

示例代碼

#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 105;
int n, m, ans;

struct Node {
  int a, b;  // a 代表时间，b 代表价值
  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;                         // 边界条件：只有n种物品
  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;  // f为性价比
  }
  sort(node + 1, node + n + 1);  // 根据性价比排序
  work(1, m, 0);
  printf("%d\n", ans);
  return 0;
}

---

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