有关决策树对算法竞赛的应用

· · 算法·理论

概述

对于一些题目, 可以通过 做出决策 -> 导致情况 -> 做出新决策 这样的结构画出 / 建立决策树. 如博弈论中的 \alpha - \beta 剪枝较为常用.

  1. DP 可以通过对决策树的结构进行思考转移过程
  2. 贪心算法（与 DFS）可以通过对决策树的剪枝进行来达到目的
  3. 对于一些题目可以直接建出决策树并加以启发式搜索 / 随机化算法.
struct decisionTreeNode {
  T decision;
  map<T, int> child;
} decisionTree[maxn];

// 有时候也可以这样
// T decision[maxn];
// map<T, int> situations;

对于决策, 可以通过朴素随机 / 模拟退火算法（以此方法生成的决策树下文简称退火树, 遗传算法同理）/ 遗传算法等随机化算法生成.

搭建决策树例题 - [NOI 2026] 布丁

首先, 我们的节点还需要再记录一个属性, 即候选数集. 每次询问后在候选数集中进行筛选, 并进行决策树.

当决策树深度大于等于 4 时直接查询全集, 防止决策树过深.

每次的决策（查询数列）可以通过朴素的随机生成来产生, 并通过若干轮筛选得到信息熵最高的一个.

!!! 本题不建议使用退火树或遗传树, 因为函数的连续性很差

朴素随机已然可以得到大约 70pts 的分数.

对于此题的数列生成可以进行一些数论上的随机化构造, 可以得到更高的分数.

A* 算法与决策树

A* 算法是一种较为经典的启发式搜索算法.

当你有一颗决策树, 但是并不知道该如何剪枝也不方便去得到一个比较好的剪枝方式时, 可以使用 A* 算法并思考启发式函数.

A* 算法是一种类似 Dijkstra 的最短路算法, 有一个启发式函数 h(x) 表示预估当前点到终点的最短路距离, 存储已经走过的实际距离 g(x) .

注意：h(x) 必须低估, 不能高估, 且满足三角不等式, 否则第一个出现的可能不是最优解.

A* 与 Dijkstra 的堆优化版本类似, 但是比较器函数从纯粹的 g(x) 改为 f(x) = g(x) + h(x) .

Dijkstra 其实是 h(x) = 0 的 A* 算法

如 斗地主（加强版） , 本题的剪枝方式或许并不明确, 但是很显然的可以思考出启发式函数是剩余牌数与能出的最大牌型比值.

然后就可以直接对决策树进行剪枝.

梯度下降法与决策树

在构建决策树的过程中可以进行类似梯度下降法的方式构建.

可以对历史表现较好的决策加权, 对历史表现较差的决策减权重, 并结合随机化算法进行搜索.

如果性质良好, 可以改为退火树进行搜索.