NOIWC 2020

JasonL · 2021-01-31 22:42:31 · 个人记录

NOIWC

Day1

1st 数据结构与实际应用

01 测测你的路由器

TL:30.00s ML:1.00G

题意

在线对查询地址与路由表中地址进行最长前缀匹配，返回对应地址的下一跳（nexthop）。其中地址表示为01串。

算法分析

01 朴素算法

直接存下每个地址对应的下一跳信息。

记录时空复杂度极大。查询O(1).

02 基于Trie树的算法

在Trie树每个节点保存对应的下一跳，用Trie树解决最长前缀匹配。

时间开销大大减小（32次内存访问），空间开销也较小（不超过32N个节点）。

实际性能266ms，52M。

官方记录

03 路径压缩Trie

将Trie的中间节点（只有一个子节点的节点）删去。在每一个Trie的节点记录下该节点的前缀和长度。

时间开销（最多32次内存访问查询），空间开销也减小（不超过2N-1个节点）。

然而问题在于如何实现子节点的跳跃。个人认为是将压缩路径整合的01trie记录起来进行匹配。

实际性能381ms，55M。

官方记录

04 基于Hash和二分查找的算法

在Hash表中保存所有节点，查询时二分匹配长度（节点深度）。

时间开销：6次Hash表访问/查询

空间开销：不超过32N个节点。

用<map>即可实现。

实际性能：1603ms，86M。

官方记录

05 基于二分查找的算法

考虑在网络地址范围进行二分。

首先“补全”所有节点，使每个节点要么是叶节点，要么有两个子节点。

然后取出叶节点表示的区间，合并相同下一跳的区间。

查询时在“区间列表”中二分即可。

时间开销：logN次内存访问/查询。

空间开销：不超过2N-1个区间。

实际性能：245ms,17M。

官方记录

06 基于位图的算法

对05的优化（二分查找logN）。

快速查询可以使用位图（Bitmap）。

每个地址对应一个位，区间左端点对应位为1，其余位为0。

例如100010000000表示0和4两个地址是存在的。

目的地址所在区间编号=sum[0...addr].

位图上快速计算前缀和：

每64位一组，预处理以组为单位的前缀和，用32位整数保存。查询时读取一次前缀和，再统计不满一组的64位中“1”的个数。

可用位运算快速进行64位统计。

空间开销：512M（位图）+256M（前缀和）。

时间开销：前缀和访问、位图访问、下一跳数组访问各一次。

实际性能：322ms，501M。

07 Lulea算法

简化版：

三层Trie树：

第一层:前16个bit

第二层：中间8个bit

第三层：最后8个bit

预处理：每一层使用06算法。

前两层结构指向下一层，第三层结构指向下一跳。

见Small Forwarding Tables for Fast Routing Lookups[Mikael Degermark,Andrej Brodnik,Svante Carlsson,and Stephen Pink].

查询11.08ns/次查询（60.68 Gbps)，41M。不超过3次06查询->9次内存访问。

时间效率增加：

• 空间开销小
• 内存访问次数少：缓存命中率高
• 面向数据：16-24bit的最长前缀占90%以上

08 Poptrie算法（6+6+6+6+6+2）

每层高度为6的Trie树，使用06结构。

优于Lulea算法。

总结与讨论

OI中的算法(01-06)：

• 选择不同基本算法

• 追求更好的时空复杂度

• 减少常数（可能是操作次数）

实际应用中的算法（07&08）：

• 面向指令集和缓存进行优化

• 从数据中挖掘特性来设计更优结构

这些算法均基于Trie结构。

02 路由表压缩

TL:10.00s ML:1G

题意

给定路由表，输出一个与之等价且最优压缩的路由表。

等价：每个IPv4地址在两张表中对应的下一跳分别相同。

最优：不存在表项更少的等价压缩路由表。

算法分析

01 树形DP

02 ORTC（Optimal Routing Table Constructor）

标记下传

实际应用中的需求

路由表每秒可能有上万次的更新。

• 压缩后的路由表如何快速更新？

1 保持最优压缩率：更新最劣O(n)

2 不进行压缩/调整（压缩率不可控）

3 局部次优压缩（时间、压缩率如何控制？）

考虑动态DP？（临时更新）

• 多次更新后，路由表可能需要重压缩（空间过大）

如何权衡时空复杂度？亦或是避免重压缩？

考虑替罪羊树？（类比推理）

• 如何快速判定压缩算法正确？->快速找出两个路由表中不等价的区间

03 路由表等价问题

题意

给定路由表A和B，判断它们是否等价

（每个IPv4地址在两张表中对应的下一跳分别相同）

如果不等价，找出下一跳不相同的区间。

算法分析

两遍扫描

第一遍：将路由表转换成区间列表。

第二遍：检查两个区间列表是否相同。

EX03 增量更新

题意

03题面变为多次询问，带修改操作。Q=10^5

算法分析

数据结构维护

每个子树的路由信息是独立的（除去祖先下传的标记影响）

子树信息由根节点、左右子树组成（自下而上统计）

在Trie树上可以将标记下传影响到的、不受标记下传影响的信息分开统计。

用多项式Hash来表示字数范围内的下一跳信息（树Hash）

每次更新时间复杂度为O（Trie树深度）。

路由压缩算法的总结和讨论

静态路由压缩问题：存在最优算法（树形DP，ORTC）

路由表等价性判断问题：存在简单算法（两遍扫描，Hash）

->优化目标单一，容易彻底解决

实际应用：动态路由压缩算法（见“实际应用中的需求”）

不存在最优解，存在多个次优解；指标难以衡量

从竞赛中的“复杂度”“最优解”到实际应用中的“软硬件与数据优化”“多种评价标准”

2nd 数据驱动的算法

摘要

高维向量空间的常用算法

大数据应用的常用算法

优化算法与机器学习

高性能计算相关知识

Data Science vs. Computer Science

《Foundations of Data Science》(John HopCroft)

从离散数据（序列、树、图）到连续数据（向量、函数）、高维空间

从精确的时间复杂度到基于实际数据的复杂度

从组合优化算法到概率、线性代数、连续优化

US Berkeley CS 270 Graduate level algorithms and data structures

高维向量

高维向量是数据处理里面最常见的基本数据结构，广泛应用于机器学习、搜索引擎、图像处理等行业。可以代表图片、文档、音频、用户信息，往往具有低维子结构。

• 实际问题 vs. worst case?

二维向量最近邻（求向量最小夹角）

三维向量最近邻-》随机选择多个平面，将向量投影到二维。

线段树与KD-Tree

两个算法可以分别解决一维和二维的Locality-Sensitive Hashing（局部敏感度哈希）问题。

OI中多见线段树，而KD-Tree则少见。

[APIO2018]Circle selection

可以用KD-Tree。暴力O(n^2)，需要剪枝。

据说可以用可持久化线段树，复杂度O(n\log^2n)。但是运行速度慢。

大数据算法

• 线性时间复杂度、内存受限
• 自然数据往往服从Power Law
• 并行计算、分布式计算
• 搜索引擎、推荐系统

集合大小估计

题意

你需要从数据流中不断读取数据d_i，但只有常量级别的内存用以存取中间结果，询问在任意时刻，估算当前已读取的数据里，不同的元素的个数。也就是集合\{d_i\}的元素个数。

Minhash算法

假设数据在某个Hash空间里均匀分布。那么集合越大，hash值的平均间距越小，这导致所有hash值的最小值也越小。

因而可以用hash值的最小值来预估数据间隔，进而预估集合大小。

交集、并集只需要三次该算法（A,B,AB）即可。（交集+并集=|A|+|B|）

搜索引擎

• 海量候选集（数据规模极大）
• 检索词出现在任意位置

算法实现

OI算法

KMP的复杂度与数据无关，恒定为O（n+m）。

后缀自动机也同样可以考虑。

倒排索引

• 以单词、词组为粒度，构建单词->文档列表的索引链。

• 将查询拆分成w_1,w_2,w_3,\dots，将单词对应的文档列表求交集。

  • 每个“单词”可以看做对候选文本集合的一个划分或一个hash编码（可参考《数学之美》）
  • 多用于图片检索、基于用户画像的商品检索、新闻检索

• 利用机器学习算法对候选集进行个性化排序。

对比：OI算法与实际应用

为什么倒排索引算法不会出现在OI里？

• 自然数据具有规律性（Power Law），词组个数有限
• 搜索数据并非100%命中。

为什么KMP在实际应用中没有被选择？

• 面对少量的随机数据性能比高，但面对海量数据难以解决。
• *数据流性质：无法保存
• 不需要精确匹配

随机化思想

《浅谈随机化思想在几何问题中的应用》《骗分导论》“模拟退火”

旅行商问题

题意

给定N个点的无向图，找到里面的一条全遍历路径，使得经过的边权值最小。N<30。

随机化算法

• random_shuffle

• 每次随机选择排列里的两个点的位置，如果交换后路径总代价变小，则交换

• until 找不到两个点

N皇后问题

题意

求N皇后的可行解。N\le 10^6

随机化算法

• random_shuffle
• 计算该排列下各条对角线“皇后冲突数”的平方和（统计i+j和i-j的重叠数量）
  • （平方和相比于和更容易区分方案的优劣，从而让程序进行期望更多可行的调整操作）
• 随机选择两个皇后位置交换，如果交换后冲突数平方减小，则交换。
• until 找不到这样的两个皇后

发现估价函数在随机化算法中依然占有重要地位。

结构型可行解转化为优化问题（适用随机化算法）。可以通过Loss Function度量当前解与目标解的距离。

随机调整与梯度下降

• 模拟退火：随机调整的一种

• 随机调整等价于随机寻找离散函数在局部梯度的下降方向

• 梯度下降：机器学习的核心算法之一

• 凸优化与非凸优化：是否能使用三分？——局部最优并不一定是全局最优（非凸函数）

实际情况：

Gradient-descent works surprisingly well in deep learning

模拟退火、加噪音都可以帮助算法逃出次优解。

随机种子的选择：

难以生成真随机数；需要根据实际情况进行调整。

与之相比，通过调整步长、检验方法更容易增大命中率。

数据拟合问题

最小二乘法

给定二维平面的N个点，寻找直线y=ax+b使得\sum(y_i-\top y_i)^2最小。其中\top y_i=ax_i+b.

解法：展开函数式，优化目标是关于a,b的二次凸函数，求得导数为0的点。

一些重要的概念：

已有数据（数据库）、待优化参数（如a,b），优化目标

核心假设：

优化得到的参数对新的(x,y)同样适用。->机器学习的泛化性

分析

注意到val_a\ge \frac{s}{2}||val_b\ge \frac{s}{2}。

对每条边，当每次val_u\ge \frac{s}{2}时，检验是否能加入这条边。不能，s将当前点权和删去，新的s至多变为原来的一半。

利用启发式合并可以做到O(n\log^2n\dots)

06 Honorable Mention

Source:...,Problem H

题意

给定长度为n的序列，q次询问某区间的k-最大子段和.

其中odd(H)表示H中大小为奇数的连通块个数。

由于原图中最大匹配为n-1，有\min\limits_{U\in V}(|U|-odd(G-U))=-2.考虑对于这样的一个点集U，如果U中某个节点度数不为|V|-1，则添加一条连接U到不满的边，值仍然不变，不合法。同理可得其他点的情况。

设有k个度数为|V|-1的点，删去它们后应有k+2个奇数大小的团，显然这样的图也满足加一条边后就有完美匹配的条件。对于每个团，令其点数加上1变成偶数，同时不管那些度数为|V|-1的点（这样的点数由团的个数唯一确定），则现在总的点数为2n+2。

变成1的拆分问题。时间复杂度O(n\log n).

14 Hall's Theorem

Source:...,Problem H

题意

构造一个两边各n个点的二分图，记N(A)表示与A中的点有直接连边的点集。需要使|N(A)|<|A|的点数恰好为k.

这是一个类似组合数进制拆分的东西，贪心构造即可。时间复杂度O(n^2).

15 Jealous Split

Source:...,Problem J

题意

给一个长度为n的序列，将其划分为k部分，记s_i表示第i部分的和，m_i表示第i部分的最大值。需要构造一个划分使得

每个人都是绝顶聪明的。如果有一天某个人知道自己的数不是x，游戏结束。求结束天数。

问题转化为三维最长上升子序列问题，用二维数据结构或分治解决。

如果a_i-B_i和a_i-C_i都是有序的话，i也一定是有序的。于是可以优化。

2nd 组合题选讲

01 皮配

题意

详见十二省联考2019.

分析

如果先选择导师，难以解决条件限制。

注意到阵营或派系与选择导师无直接关系。我们可以先将学生分为YR派系，再将城市分为红蓝阵营。这样就可以完成限制问题。

【独立性】

直和

对I_P，若每个集与每个分治部分的交满足P，从每个分治部分中任取一个满足P的集，它们的并依然满足P，那么I_P是\{I_p\cap2^{S_i}\}，称A_i是A=(\cup A_i)在S_i上的投影。

例如图的每个连通块、线性基每个元素张成的空间。

直和问题只需要分别讨论每个部分即可。（优化即部分优化）

02 [BJ United Round #3]押韵

题意

一个长nd的序列，每个位置要染成k种颜色之一，要求每种颜色出现次数都是d的倍数。

求方案数\mod 1049874433.

分析

能不能将nd分为n组，然后组合数分配颜色？

（然而搞不定）

03 [清华集训2017]无限之环

题面

接水管游戏：一个n\times n的网格状棋盘，每格是15种水管之一。

你可以逆时针或顺时针旋转任意非直线型水管任意次。

给定初始局面，要求你旋转水管使得最终不存在断头，最小化旋转总度数。

对于任意两个不同节点x,y，若f_x=f_y，则存在一个u满足u在x到y的路径且f_u>f_x.

题目转化为求f的最大值的最小值。

以任意节点为根后，考虑子树的f对其他节点的影响。

只需要关心子树内f值到子树根路径上的最大值的节点。这些节点的f值就是子树的根x的父亲无法设置的f值的集合，记做S_x.

进一步可以用二进制数表示S_x.

按照dfs序，贪心地设置f_u使得val_u最小。

将最小化最大值转化为最小化根的二进制数val.

考虑合并子树的过程，设cnt_x为x在多少个儿子的S集合中出现过。

设根的f值为v.

若cnt_x\ge 1则v \not = x；若cnt_x\ge 2则v>x.

根的val为所有儿子val的二进制OR，将第v位设为1，第0到v-1位设为0.可以推得最小化子树的根的val。

注意到答案不会超过\log n.因而int即可、

时间复杂度O(n \log n)-O(n).

05 Fishes

06 Fibonacci Sums

题意

见链接。

分析

首先考虑两个序列合并后每个f_i对应的c_i\le 2.

首先消去2，再考虑相邻的1.

消去2时先找到最高位的2。

然后消除相邻的1。如果产生新的相邻1，继续操作。

07 Axes of symmetry

题意

给出n多边形，不自交。找到图形所有对称轴。

分析

对于一个图形，至多2n个对称轴。要么是经过点的角平分线，要么是一条边的垂直平分线。

枚举可能的对称轴，暴力判断是否对称。

如何快速判断对称？对应边长、对应角度相等。

给出边长序列与角度序列，转化为字符串问题。哈希O(1)判断即可。

注意角度的方向。

08 Ploughing

分析

判断能否删光？可以贪心。

删除最大的列/行？不满足最小操作次数。

删除合法的最长的列/行？

我们假定最后删除的方向是横向/纵向。那么枚举[l,r]区间最后删除，确定的部分就不能被另一方向删除。这时候再判断能否删光即可。

09 Circular Game

分析

将环分为若干块，其中每一块都由相同颜色的棋子组成。

由至少3个同色棋子构成的块：

若有空隙，则该颜色持有玩家不会输。

若无空隙，则该颜色持有玩家可能可以通过一步获得空隙。

这样的块可称为W.若一方有W，一方没有，则有的那方必定获胜。

玩家的首要目标是让自己获得W，让对手无法获得必杀块。若必杀块无缝隙，则堵住必杀块的棋子一定不能移动。

考虑只有1个棋子的块，一定形如WW B W B WW或WW B W BB。

对于两边同色，等效于必杀块。

对于两边不同色，等效于相邻两个的nim游戏。（WW-B，W-B，W-BB）

因而我们优先处理大小为1的块。

处理必杀块。如果能判断出结果则结束。如果不能，使用Nim游戏决出胜负。

10 Matching

题意

给定一个长度为n的序列\{a_i\},一个长度为m的序列\{b_i\}。保证序列中没有相同元素。两个序列等价是指他们离散化后的结果相同（相对大小关系相同）。求\{a_i\}中有多少个连续子序列与\{b_i\}等价。

先手策略p最优当且仅当val(G)=\min\limits_qval_G(p,q)

后手策略q最优当且仅当val(G)=\max\limits_p val_G(p,q).

现证明可以构造一个第一步取最大值的最优策略。

接下来说明存在一个第一步取了最大值的策p_2，对于任意策略p_1，满足\min\limits_{q_1}val_G(p_1,q_1)\le \min\limits_{q_2}val_G(p_2,q_2)

对于任意策略q_2，满足\min\limits_{q_1}val_G(p_1,q_1)\le val_G(p_2,q_2)

存在策略q_1满足val_G(p_1,q_1)\le val_G(p_2,q_2).

对于任意策略p_1,q_2，存在策略q_1,p_2，满足第一步取了最大值，且val_G(p_1,q_1)\le val_G(p_2,q_2) .

可以理解为同时进行两个游戏G_1,G_2，对手操作G_1的先手和G_2的后手，你操作G_1的后手和G_2的先手。

第一步，q_1,p_2取最大值M.接下来我们的策略是，模仿对手操作。

任何时候G_1和G_2局面完全相同时，我们完全模仿对手操作。这样可以一直保持局面相同。

12 Stamps I

给定一个2n\times 2n的网格图，每个格子初始染黑或染白。每次操作你可以选择一个大小为n\times n的子矩阵，并将其染黑。求将整个网格图染黑的最少操作次数。

分析

答案不会超过4.

矩形的并的限定框一定包含白格子的限定框。矩形个数小于等于3时，一定有一个矩形在矩形的并的限定框的角上。让在角上的矩形恰好顶住白格子限定框的角上。

让在角上

13 N and K

考虑所有值在1到N之间单调上升整数序列，序列要满足其中不存在两个不同的数有倍数关系。给定K，询问所有最长的满足条件的序列中第K大的值最小是多少。

01 Min-cut

给出一个无向图，求最小割。

Karger's Min-cut Algorithm

等概率选择图中两个点，删除它们之间的边，并缩为一个点。一直到只剩下两个点，统计两点之间的边。

有\frac{1}{C(n,2)}概率正确。因而跑n^2有很大概率正确。

用最小割树也可。

02 最小圆覆盖

有n个点，求最小圆覆盖所有点。

三点确定一个圆。设O_i为覆盖前i个点的最小圆。

如果点i在O_{i-1}里面，那么O_i=O_{i-1}.

否则点i必定在O_i边界上，在1\dots i-1中枚举一个点j，如果点j不在圆中，那么它一定作为圆的另一个端点。

对于区间中的点j，竞赛图中存在边(i,j)

不再区间中的点i,竞赛图中存在边(j,i).

求强连通分量。

竞赛图的性质：强连通分量形成一条链的结构。

加入节点i时，假设有k个强连通分量。\forall (i,j)\in E找到j所在强连通分量编号最小的，记为L.\forall (j,i)\in E，找到j所在强连通分量编号最大的，记为R.

如果L\le R，那么i以及L\dots R会合并为一个新的强连通分量。

如果L>R，那么L=R+1，则i插入到L,R之间形成一个新的强连通分量。

加入新节点过程中，对于所有节点维护一个权值p，使得如果节点x,y分别属于强连通分量u,v(u<v)，那么p[x]<p[y].

查询L,R变为查询区间最小值和最大值。

重量平衡树

给每个节点权值p，类似于一般的Treap中每个节点的键值，可以用于比较两个节点的排名。

在Treap中给每个节点权值区间[l,r]。

插入时候随机优先级，按照优先级旋转完后期望O(\log n)时间重构权值区间。

注意到线段树中维护的区间中最大最小值，但在加入节点i时，p[1,\dots,i-1]相对大小不会改变，所以线段树修改的时候只需要修改包含节点i的区间。

04 Max-cut

给出一个无向图，求最大割。

随机给节点分配\{0,1\}，划分为不同区间。得到割的期望大小为\frac{m}{2}，概率为\frac{1}{m+1}。

所以只需要运行程序O(m)次即可找到一个大小至少为\frac{m}{2}的割。

Eg.所有图都存在一个大小至少为\frac{m}{2}的割。

Extra

得到解与最优解比值大于\frac{1}{2}（近似比大于\frac{1}{2}）。

Max-cut是NP-hard问题。

05 Max-sat

有n个布尔变量以及m个式子。

每个式子为一些变量或一些变量的否进行或运算的结果，如x_1 or\ \lnot x_2。

令尽可能多的式子值为1.

首先问题可以放宽为可以在多项式时间内解决的线性规划问题。得到解\hat y,\hat z，表示布尔变量的解和运算式取值的一个近似解，适合处理式子较长的情况。

对于每个变量x_i令其有\hat y的概率为真，1-\hat y的概率为假。可以在其上得到一个适合处理式子长度较短的算法。

两者结合可以得到一个近似比\frac{3}{4}的算法。

近似计算

标准问题

• 一个无向图的生成树个数

• （01背包）有n个背包和一个容量为b的背包，每个物品只有一个，问将物品放到背包里的方案数。

算法FPRAS,Monto-Carlo Simulation。

蒙特卡洛模拟

通过随机采样来得到估计解。

采样：随机给出输入，通过模拟得到输出。

设|U| 为全局状态数。|G|表示采样得到的样本数。则\frac{|U|}{|G|}不能过大。否则难以得到精度范围内的估计解。

于是需要均匀抽样。我们得到当前操作转移后的所有状态的方案数|A|，以及当前状态的全局方案数|S|，那么选择该操作的概率就定为\frac{|A|}{|S|}。

对样本处理：由样本数据得到全局估计解。

Markov Chain

部分情况难以抽样。于是需要马尔科夫假设和马尔科夫链。

马尔科夫链与马尔科夫过程：

马尔科夫假设：假定当前变量的取值只与前一个变量的取值相关。即

状态空间：所有可能取值所组成的空间，记为\pi\{x_1,x_2,\dots,x_n\}

平稳分布(Stationary distribution):\pi=\pi P其中\sum_i\pi_i=1

两个随机变量之间的距离d_{TV}(X,Y)=\sup\limits_A(Pr[X\in A]-Pr[Y\in A])

对于有限马尔科夫链，定义两个分布之间的距离为d_{TV}(x,y)=\max\limits_A\sum\limits_{i\in A}(x_i-y_i)=\max\limits_A|\sum\limits_{i\in A}(x_i-y_i)|

在一些拥有较好的性质的有限马尔科夫链上，对于初始分布x，最终会收敛到某个平稳分布\pi上。

对于任意两个随机变量X,Y，有d_{TV}(X,Y)\le Pr[X\not=Y].

周期(period)

对于一个马尔科夫链，一个状态i的周期定义为m=\gcd(\{t>0|p_{ii}^t\not = 0\}).若m=1称状态i为非周期性的。

一个马尔科夫链是非周期性的，当且仅当所有状态都是非周期性的.

如果一个马尔科夫链的状态是非周期性的，则存在t_0使得t\ge t_0,p_{ii}^t\not =0。

2nd Search and Iteration Algorithm

Basic:DFS,BFS

A*(A-Star)

引入估价函数h(x)，表示当前状态到终态的代价估计。

首先由h(x)\le g(x,ed).（g(x,y)表示从状态x到状态y的实际代价）

那么f(x)=g(st,x)+h(x).f(x)表示从初态经过状态x到终态的估计总花费。

我们优先搜索f(x)较小的，即可提高效率。

在图上还需要满足h(A)-h(C)\le g(A,C).否则到达终点不会为最优解。

K短路——使用A*算法，取出第k次即为最终解。

IDA*

在A*基础上限制搜索深度，缩小空间消耗。从低到高增加限制深度，按照DFS序进行搜索。

Advertisal Algorithm

MinMax Search

最劣情况下的最优结果。

function Max-Value(state)
    v<- -INF
    for each successor of state do
        v<- max(v,Min-Value(succ))
    end for
    return v
end function

function Min-Value(state)
    v<-INF
    for each successor of state do
        v<- min(v,Max-Value(succ))
    end for
    return v
end function

必胜/必败态剪枝：

如果当前状态已经被确认为必胜/必败态，那么直接返回。

时间复杂度O(b^n)，空间复杂度O(n) .

Alpha-Beta Pruning

即Alpha-Beta剪枝。

function Max-Value(state,alpha,beta)
    v<- -INF
    for each successor of state do
        v<- max(v,Min-Value(succ))
        if v >= beta then
            return v
        end if
        alpha<- max(alpha,v)
    end for
    return v
end function

function Min-Value(state,alpha,beta)
    v<- INF
    for each successor of state do
        v<- min(v,Max-Value(succ))
        if v <= alpha then
            return v
        end if
        beta<- min(beta,v)
    end for
    return v
end function

时间复杂度\sqrt{b^m}=b^\frac{m}{2}.

Meeting in the middle

折半搜索。重点在于如何合并。

Dancing Links

精确覆盖问题。

一个n\times m的01矩阵，要求选出一个行的子集，使得在这些选出的行中，每一列都恰有一个1.

数据结构：双向十字链表。

固定一列，枚举选择使用哪一行。

把这一列所有行全部删除。

Climbing Mountains

爬山算法。其核心为

Simulated annealing

模拟退火。

Newton-Rahpson method

牛顿迭代法。

具有平方收敛性质。

Failure Analysis

错误初始点：

Graph Iteration

Intro Prob.

赌徒问题：

有一个赌徒，初始有k元，每次他有p的概率赢一元钱，有1-p的概率输一元钱，当他赢到m元时就会离开，当手上没有钱时就会破产，问赌徒一直玩下去离开的概率。

迭代做法：

随机一个函数f_0:[m]\rightarrow [0,1]

赌徒问题2：

有一个赌徒，初始有k元，每次他可以押注t元，有p的概率再赢t元钱，有1-p的概率输掉这t元钱，当他赢到\ge m元时就会离开，当手上没有钱时就会破产，问赌徒一直玩下去离开的概率。

迭代做法：

随机一个函数f_0:[m]\rightarrow [0,1]

MDP Problem

MDP问题：

• 状态集 S
• 可行动作A
• 转移系数 P(s,a,s')\rightarrow [0,1]
• 收益函数R(s)
• 衰减系数\gamma \in (0,1]
• 如果一个样本的状态序列为s_0,s_1,\dots s_n，则总收益为\sum\limits_{i=0}^nR(s_i)\gamma^i

Topological Situation

DP即可。

General Situation

迭代做法：

随机一个初始分布V_0

Memorize Search

Day 5

01 猜数游戏

算法1

暴力枚举S的所有非空子集T，然后枚举T的所有子集检查其是否可以生成T.O(3^n).

算法2

对于特殊性质B，注意到数列u^i在模p意义下很快会归零，且相互关系构成若干条链。链与链之间互不相关。

建图

02 选课

03 有根树