Question

道生之，德畜之，物形之，势成之。《老子》

State

一件事物，以宏观、全知的角度望去，当前的模样称作“状态”。比方说：影片拍摄著一台行驶中的车辆，底片的一格画面，就是一个状态。

状态可以是一盘棋的局面，也可以是今天下午五点整的车辆分布情况。状态与状态之间，可以是离散的（棋盘局面），也可以是连续的（车潮）。

每一个状态都可以经过特定动作，改变现有状态、转移到下一个状态。例如象棋，我们可以移动一颗棋子到其他空地、移动一颗棋子收拾对手的棋子。例如车潮，每一辆车可以踩油门、煞车、转弯。这样的动作叫做“转移函数 Transition Function”。

所有状态依照衍生关係互相连结，形成了有向图。状态就是点，转移函数就是边，转移的成本就是边的权重。

State Space Tree（Under Construction!）

State Space Tree

选定一个状态，衍生各式各样的状态，形成一棵树，便是“状态空间树”。

状态空间树无穷无尽衍生。同一个状态很可能重複出现、重複衍生。

用途：Single Source Shortest Paths

状态空间树的主要用途是：从“起始状态”到其他状态，求得转移过程。每当转移状态，就要累加成本。

状态空间树无穷无尽衍生，无法预先建立，只好一边建立、一边搜寻。使用遍历演算法 DFS、BFS，建立暨搜寻状态空间树。

用途：Point-to-Point Shortest Path

状态空间树的另一个用途是：从“起始状态”到“目标状态”，求得成本最少的转移过程。

一般来说，是以起始状态建立状态空间树。状态空间树无穷无尽衍生，于是目标状态很可能重複出现，散布在状态空间树当中。

搜寻顺序

如何迅速找到目标状态呢？优先建立离目标状态比较近的状态。

     cost function g(x)：起始状态到当前状态 x，已知的、真正的转移成本。
heuristic function h(x)：当前状态 x 到目标状态，未知的、预估的转移成本。

admissible heuristic：h(x) 小于等于真正的转移成本（不高估）。
consistent heuristic：h(x) 满足单调性。h(x) ≤ c(x→y) + h(y)。

以 g(x) 由小到大的顺序建立状态空间树，首次遇到的目标状态，就是 g(x) 最小的目标状态。

以 h(x) 由小到大的顺序建立状态空间树，首次遇到的目标状态，不一定就是 g(x) 最小的目标状态。因为 h(x) 不准确。

UVa 260 298 314 321 429 571 589 704 985 10047 10603 10653 10682 10923 10103 10704 10067

以 g(x) + h(x) 由小到大的顺序建立状态空间树，并且 h(x) 小于等于真正的转移成本（不高估），首次遇到的目标状态，就是 g(x) 最小的目标状态。当 h(x) 估计的很精准，可以迅速走到目标状态，而不会四处閒逛、四处兜圈。时间複杂度难以分析。

以 g(x) + h(x) 由小到大的顺序建立状态空间树，并且 h(x) 满足单调性，首次遇到的每种状态，都是 g(x) 最小的状态。也就是说，每种状态只需拜访一次，等同图论的最短路径演算法。时间複杂度为 O(ndk)，其中状态种类为 n，分枝为 d，状态转移需时 O(k)。

UVa 529 851 10073 10422 10798 11163 11376 10314

搜寻演算法

Breadth-first Search（BFS）
忽视 g(x)、h(x)，优先建立离起始状态最近的状态。
适用于转移成本是固定值。

Depth-first Search（DFS）
忽视 g(x)、h(x)，优先建立离起始状态最远的状态。
适用于转移成本是固定值。

Depth-limited Search（DLS）/ 过去称作 Depth-first Branch-and-Bound（DFBnB）
DFS 的改良版本。限制建立的深度（或成本），当深度（或成本）太深就不再往下分枝衍生。

Iterative Deepening DFS（IDS）
DLS 的改良版本。反覆使用 DLS，并逐次放宽深度限制。
若每次放宽的量极少时，可达到类似于 BFS 的功能。

Uniform-cost Search（UCS）
g(x) 由小到大建立。以 BFS 实作。

Iterative Lengthening Search（ILS）
g(x) 由小到大建立。以 IDS 实作，逐次放宽 g(x) 的限制。
若每次放宽的量极少时，可达到类似 UCS 的功能。

Best-first Search
h(x) 由小到大建立。以 BFS 实作。

Recursive Best-first Search（RBFS）
h(x) 由小到大建立。以 IDS 实作，逐次放宽 h(x) 的限制。
若每次放宽的量极少时，可达到类似 Best-first Search 的功能。

A* Search（A*）
g(x)+h(x) 由小到大建立。以 BFS 实作。

Iterative Deepening A* Search（IDA*）
g(x)+h(x) 由小到大建立。以 IDS 实作，逐次放宽 g(x)+h(x) 的限制。
若每次放宽的量极少时，可达到类似 A*的功能。

Memory-bounded A* Search（MA*） / Simplified Memory-bounded A* Search（SMA*）
限制记忆体用量的 A*。当 queue 全满时，就从中删除 g(x)+h(x) 最大的状态。

名称天花乱坠，令人眼花撩乱。其实只是搜寻顺序的差别：Ø、g(x)、h(x)、g(x) + h(x)，以及遍历演算法的差别：BFS、IDS。

搜寻顺序，习惯採用 g(x) 或 g(x) + h(x)，以求得最佳成本。

遍历演算法，BFS 系列，效率较差；IDS 系列，效率较好。

假设状态空间树刚好是一棵二元树，而目标状态位于第 N 层的状态。BFS 搜寻的状态数目是(1+2+4+8+...+2^N)，IDS 搜寻的状态数目是 1 + (1+2) + (1+2+4) + ... + (1+2+4+8+...+2^N)，大约是前者的两倍。如果状态空间树是 K 元树，则大约是前者的 K 倍。

儘管 BFS 搜寻的状态数目比起 IDS 少了许多倍，然而 BFS 必须维护 priority queue，还得 indexing，因此 BFS 的执行速度通常比起 IDS 慢上许多，而且记忆体用量也大上许多。

IDS 逐步放宽 g(x) 或 g(x) + h(x) 的限制，不必在意每次 DFS 的遍历顺序。这使得 IDS 不需要 priority queue。

搜寻策略

forward search：正向搜寻。起始状态建立状态空间树，从中搜寻目标状态。

backward search：反向搜寻。目标状态建立状态空间树，从中搜寻起始状态。

bidirectional search：双向搜寻。起始状态、目标状态分别建立状态空间树，搜寻共同状态。

实作时，通常是轮流衍生。状态空间树轮流增加一层，直到两边出现共同状态。

perimeter search：周界搜寻。起始状态建立状态空间树，储存所有状态，直到记忆体几乎用光。然后目标状态建立状态空间树，直到出现储存过的状态。

实作时，通常起始状态採用 BFS，目标状态採用 DFS、IDS、IDA*等节省记忆体的遍历演算法。

beam search：柱状搜寻。限制状态空间树每一层的状态数目。当某一层抵达上限后，该层后来产生的状态皆捨弃。

random search：随机搜寻。随机决定衍生哪些状态。

heuristic search：启发搜寻。按照经验法则，决定衍生哪些状态。例如台湾的交通网，西部比东部密集。从基隆到屏东，首先去台北，而不是去宜兰，因为根据交通网密度，台北可能更快到达屏东。

实作时，通常是将经验法则化为 heuristic function，藉此调整搜寻顺序。

ICPC 5098

搜寻技巧

branching：由于状态空间树可以漫无止境的滋长，而电脑记忆体有限、人类时间有限，所以只好一边走访状态空间树，一边衍生分枝、建立状态空间树，走到哪，建到哪。逐渐增加成本下限，逼近正确答案；一旦超过成本上限，立即停止分枝。

pruning：参照题目给定的特殊限制，裁剪状态空间树，去掉多馀子树。好处是减少搜寻时间。

bounding：搜寻时，随时检查目前的成本。目前成本太坏，就不再往深处搜寻；目前的成本足够好，也不必往深处搜寻。好处是减少搜寻时间。

memoization：记录所有遭遇到的状态，避免状态空间树重複衍生相同状态。当记忆体不足时，也可以只记录一部分的状态。当起始状态固定不变时，可以充作 lookup table。

indexing：所有状态进行编号，以整数、二进位码等形式呈现。好处是方便 memoization。当记忆体不足时，indexing 可以改为 hashing，达到压缩功效。

tie-breaking：priority queue 于平手时，额外比较 h(x) 的大小，优先弹出 h(x) 较小的状态。某些特殊情况下，可以提早抵达目标状态，减少状态数量： http://movingai.com/astar.html 。

UVa 233 10536 10941 690 ICPC 6010

应用：3 Jugs Problem

3 Jugs Problem

手边有三个装水的容器，容量由大到小分别是 X 公升、Y 公升、Z 公升，都没有刻度。其中 X 公升的容器已经装满水了。

问题：如何在这三个容器之中，将水倒来倒去，使得其中一个容器恰有 W 公升的水？

资料结构

使用三个变数记录容器的容量。再使用三个变数记录容器中的水量。

三个容器的装水情况，视做一个状态。

起始状态：一个满容器、两个空容器

一开始只有 X 公升的容器装满水，另外两个容器没有装水。

目标状态：其中一个容器装了 W 公升的水量

转移函数：把 A 容器的水倒入到 B 容器中

两种情形：

一、A 水量不够、B 剩馀容量太多，倒不满 B，A 没有剩水。

二、A 水量太多、B 剩馀容量不够，B 被倒满，A 还有剩水。

不能只倒一些！原因是容器没有刻度，无法精准的控制水量，无法保证最终结果正是 W 公升。

成本

倒一次水，算一个步骤。成本定为 1。

空间複杂度

为了避免同样的状态重複出现、重複衍生，只好记录所有遭遇过的状态。三个容器的水量范围是 0~X 公升、0~Y 公升、0~Z 公升，所有状态总共(X+1)*(Y+1)*(Z+1) 个。空间複杂度是 O(XYZ)。

时间複杂度

倒水方式总共 3*2 种。也就是说，一个状态衍生 O(3*2) 个状态。时间複杂度是 O(XYZ * 3*2) = O(XYZ)。

遍历演算法：BFS

判断起始状态是否能够转移到目标状态。

应用：8 Puzzle Problem

8 Puzzle Problem

3×3 方块拼图，缺了一格。上下左右推动方块，让它排列整齐。

处理这个问题时，每块方块标上数字编号，会更清楚一些。

4×4 叫做 15 Puzzle。N×M 叫做 Sliding Puzzle。

检查不合理的盘面：Permutation Inversion

http://mathworld.wolfram.com/PermutationInversion.html

当一个盘面的 inversion 的个数是偶数的时候，表示该盘面可以从排列整齐的状态，经过一连串推动而得；如果个数是奇数，则表示该盘面不合理、不可能存在。另外还要考虑空格位于哪一列。

应用：Rat in a Maze

老鼠走迷宫

老鼠很聪明，进入死胡同就会马上回头，不会傻傻的一直进入同一个死胡同。老鼠每一次重跑，都会越来越快。老鼠也会选择看起来离乳酪比较近的路线。

一开始就已经背熟地图，随意找出一条路线。

由于原本的线条牆壁迷宫难以实作，不太适合初学者，所以这裡採用方块牆壁迷宫，走一格当作是一步。

                  #########
                          #
_________         # ### ###
   __  __|        # #     #
| |____  |  --->  # ##### #
|  __  |_|        #     # #
|____|____        # ### ###
                  #   #    
                  #########

应用：Pathfinding

Pathfinding

即时战略游戏，用滑鼠点选角色的目的地，角色自动绕过障碍物，找到最短路径。

http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

Game Tree（Under Construction!）

Game Tree

两人对阵，轮流动作。

所有的状态形成二分图。不过这不是我们要讨论的重点。

两人对阵，轮流动作。这样的状态空间树，称作“游戏树”。

游戏树的主要用途是：从“起始状态”到“胜负已分状态”，求得转移过程。

通常我们想求最佳转移过程。先手尝试胜利；就算先手不能胜利，也要尽量拖延、让后手难以胜利。相对地，后手也是这样想。

max 层是从下层各个数字中取最大值所算出来的层
min 层是从下层各个数字中取最小值所算出来的层
也有颠倒定义的。两种都有人用。

游戏树比状态空间树所算的东西还多。状态空间树每个节点的成本，是由树根往树叶方向慢慢推导出来的。游戏树除了要算状态空间树的成本之外，另外在回溯时还要再算 min 值（或 max 值）的结果──更详细的说，遍历到树叶（胜负已定）并得到树叶的成本之后，回溯时还要利用树叶的成本算出树上各个节点的 min 值（或 max 值）。

求最少步数的状况下
先手赢了当然取 min 较好　先手在 min 层
可是要是先手输了...先手得尽量拖步数...此时没办法取 min...反而要取 max
解决方法是
输的时候的把步数设定成由很大的数字开始减少
例如 N 步是零步　N-1 步是一步
取 min 时会先取到赢的步数，取不到赢的才会取到输的步数

搜寻技巧：α-β Pruning

使用条件是遍历时必须採用 DFS。

有两部分　两部分可独立 coding

1. 相邻的两层： (alpha pruning)

　若这层是 max，上层是 min
　-> max 层数字大于 min 层数字就没意义　砍

　coding 时传一个参数是上层的数字　一般称 alpha

2. 隔一层的两层：  (beta pruning)

　若这层是 max，上上层是 max
　搜这层时　其数字底限可由上上层目前之数字决定
　大于上上层才会有机会更新上上层的数字
  (同理上上...上上层也一样，不过只要作到上上层就有连锁效果了)
　实际上没砍到啥东西...但是配合 alpha 后就可以砍到东西

　coding 时传一个参数是上上层的数字  一般称 beta

一层 min 一层 max  不好 coding　变成要写两个 function
可以改成都是 max  然后在算 min 层的的时候数字都先加负号　取 min 后再用负号还原
如此只要写一个 function

假设这层是 max
此时 alpha 的意义是成本上限，beta 的意义是成本下限。

alpha-beta pruning 的精髓，就是求得每个节点的成本上下限。
每当遭遇树叶（胜负已分），回溯，求得成本，顺手更新节点的成本上下限。

如果从叶子开始回溯时累加步数  就没办法用 beta  而且也很难 coding
从根往下走时就开始计步  世界就变得简单些了

可以逐步增加成本，把 alpha 和 beta 设定为相同，
达到类似 IDS 的效果。

甚至可以二分搜寻成本，
并且配合 memoization。

UVa 682 10111 10838 ICPC 4451

搜寻演算法：Monte-Carlo Tree Search

随机搜寻，设定为胜率。

应用：Tic-tac-toe

Tic-tac-toe