Question

手把青秧插满田，低头便见水中天，　　　　　

六根清淨方为道，退步原来是向前。《插秧诗》

Backtracking

中文称作“回溯法”，枚举多维度数值的方法。运用递迴依序穷举各个维度的数值，制作所有可能的多维度数值，并且在递迴途中避免枚举不正确的多维度数值。

当多维度数值只需要唯一一组，可以让程式提早结束。

当多维度数值可以衡量优劣，就随时剔除劣的、保留优的。

回溯法的特色是随时避免枚举不正确的数值。一旦发现不正确的数值，就不递迴至下一层，而是回溯至上一层，节省时间。

另外还可以调整维度先后顺序、一个维度裡面的枚举顺序。如果安排得宜，可以更快找到正确的多维度数值。

UVa 140 165 193 222 259 291 301 331 399 435 524 539 565 574 598 628 656 732 10186 10344 10364 10400 10419 10447 10501 10503 10513 10582 10605 10624 10637 129 10160 10802

Enumerate Tuples

© 2010 tkcn . All rights reserved.

Tuple

即是“多维度数值”。

例如数字 1、2、3 构成的三维数值是{1,1,1}、{1,1,2}、{1,1,3}、{1,2,1}、{1,2,2}、{1,2,3}、……、{3,3,2}、{3,3,3}。

范例：枚举“数字 1 到 10 选择五次”全部可能的情形

制作一个阵列，用来存放一组可能的情形。阵列中不同的格子，就是不同的维度。

例如 solution[0] = 4 表示第一个抓到的数字是 4，solution[4] = 9 表示第五个抓到的数字是 9。

Enumerate Permutations

Permutation

便是数学课本中“排列组合”的“排列”。但是这裡不是要计算排列有多少种，而是枚举所有的排列，以字典顺序枚举。

例如{1,2,3}所有的排列就是{1,2,3}、{1,3,2}、{2,1,3}、{2,3,1}、{3,1,2}、{3,2,1}。

范例：枚举{0,1,2,3,4}所有排列

依序枚举每个位置。针对每个位置，试著填入各种数字。

Enumerate Combinations

Combination（Subset）

便是数学课本中“排列组合”的“组合”；概念等于“子集合”。但是这裡不是要计算组合有多少种，而是枚举所有的组合，以字典顺序枚举。

例如{1,2,3}所有的组合就是{}、{1}、{2}、{3}、{1,2}、{1,3}、{2,3}、{1,2,3}。

范例：枚举{0,1,2,3,4}所有组合

该如何枚举呢？先观察平时我们计算组合个数的方法。

{0,1,2,3,4}所有组合个数总共 2^5 个：0 可取可不取，有两种情形、1 可取可不取，有两种情形、...、4 可取可不取，有两种情形。根据乘法原理，总共 2*2*2*2*2 = 2^5 种情形。

枚举方式可以仿照乘法原理。建立一个阵列，当作一个集合。solution[i] = true 表示这个集合拥有第 i 个元素，观念等同“ Set 资料结构: 索引储存 ”。

依序枚举每个位置。针对每个位置，试著填入取或不取。

8 Queen Problem

八皇后问题

问题：在 8x8 的西洋棋棋盘上摆放八隻皇后，让他们恰好无法互相攻击对方。皇后的攻击范围是米字。

一个非常简单的想法：每一格都有“放”和“不放”两种选择，枚举所有可能，并避免枚举皇后互相攻击的情形。建立 8x8 的 bool 阵列，代表一个 8x8 的棋盘盘面情形。例如 solution[0][0] = true 表示(0,0) 这个位置有放置皇后。

接著要避免枚举不可能出现的答案：任一直线、横线、左右斜线上面只能有一隻皇后。分别建立四个 bool 阵列，记录皇后在各条线上摆放的情形。

以及避免枚举不可能出现的答案：最终的棋盘上面不足八隻皇后。

改进

由于一条线必须刚好摆放一隻皇后，故可以以线为单位来递迴穷举。重新建立一条一维 int 阵列，solution[0] = 5 表示第零个直行上的皇后，摆在第五个位置。

缩成迴圈是一定要的啦！

0/1 Knapsack Problem

0/1 背包问题

问题：各式各样的物品，重量与价值皆异。一个背包，具有耐重限制。现在将物品儘量塞入背包，令背包裡物品总价值最高。

一个简单的想法：每个物品都有“要”和“不要”两种选择，穷举所有可能，并避免枚举背包超载的情形。建立一维 bool 阵列，solution[0] = true 表示第零个物品有放进背包。

Inclusion-Exclusion Principle

排容原理

类似于枚举所有子集合，但是每个子集合有正负号之别──奇数个集合的交集为正号、偶数个集合的交集为负号。

举例：求出 1 到 100 当中不可被 3 或 5 或 8 整除的整数有几个。3、5、8 均两两互质。

考虑数字之间不互质的一般情形：

枚举子集合（组合）有两种枚举方式，排容原理亦有两种枚举方式。

Euclidean Shortest Path

© 2010 tkcn . All rights reserved.

二维座标平面，两点之间的最短路径

在一张地图上有很多个地点，邻近的地点有笔直道路相通，我们也知道每一段道路的长度。现在要沿著道路，从一个地点走到另一个地点，请问要怎麽走距离最短呢？

一条最短的路径，肯定不会绕圈子。我们可以使用 backtracking 穷举所有排列，制造所有可能的路径。每当生成一条路径，就判断这条路径是不是历来最短的路径，并且随时记得历来最短的路径。