*搜索算法(2)
持续更新···
1.递归型枚举与回溯剪枝初识
1.
画决策树；
2.
根据决策树写递归
【题⽬描述】
今有
n
位同学，可以从中选出任意名同学参加合唱。
请输出所有可能的选择⽅案。
【输⼊描述】
仅⼀⾏，⼀个正整数
n
。
【输出描述】
若⼲⾏，每⾏表⽰⼀个选择⽅案。
每⼀种选择⽅案⽤⼀个字符串表⽰，其中第 位为
Y
则表⽰第 名同学参加合唱；为
N
则表⽰
不参加。
i i
需要以字典序输出答案。
设计递归函数：
*重复⼦问题：针对某⼀位，「选」或者「不选」这个数。因为最终结果要按照「字典序」输出，我们可以「先考虑不选」，然后「再考虑选」；
【题⽬描述】
从
1 ∼
n
这
n
个整数中随机选出
m
个，输出所有可能的选择⽅案。
【输⼊描述】
两个整数
n
,
m
，在同⼀⾏⽤空格隔开。
【输出描述】
按照从⼩到⼤的顺序输出所有⽅案，每⾏
1
个。
⾸先，同⼀⾏内的数升序排列，相邻两个数⽤⼀个空格隔开。
其次，对于两个不同的⾏，对应下标的数⼀⼀⽐较，字典序较⼩的排在前⾯（例如
1 3 5 7
排
在
1 3 6 8
前⾯）。
【题⽬描述】
今有
n
名学⽣，要从中选出
k
⼈排成⼀列拍照。
请按字典序输出所有可能的排列⽅式。
【输⼊描述】
仅⼀⾏，两个正整数
n
,
k
。
对于
100%
的数据，
1 ≤
k
≤
n
≤ 10
。
【输出描述】
若⼲⾏，每⾏
k
个正整数，表⽰⼀种可能的队伍顺序
2.DFS
3.剪枝与优化
【题⽬描述】
将整数
n
分成
k
份，且每份不能为空，任意两个⽅案不相同（不考虑顺序）。
例如：
n
= 7,
k
= 3
，下⾯三种分法被认为是相同的。
1, 1, 5
1, 5, 1
5, 1, 1
问有多少种不同的分法。
【输⼊描述】
n
,
k
（
6 <
n
≤ 200
，
2 ≤
k
≤ 6
）
【输出描述】
1
个整数，即不同的分法。
注意剪枝位置的不同，而导致搜索树的不同：
1.如果在进⼊递归之前剪枝，我们不会进入非法的递归函数中；
2.但是如果在进⼊递归之后剪枝，我们就会多进⼊很多不合法的递归函数中。
【题⽬描述】
Freda 和 rainbow 饲养了
N
(
N
≤ 18)
只⼩猫，这天，⼩猫们要去爬⼭。经历了千⾟万苦，⼩猫们
终于爬上了⼭顶，但是疲倦的它们再也不想徒步⾛下⼭了
Freda 和 rainbow 只好花钱让它们坐索道下⼭。索道上的缆⻋最⼤承重量为
W
，⽽
N
只⼩猫的重
量分别是 C1,C2,,,,,CN。当然，每辆缆⻋上的⼩猫的重量之和不能超过
W
(1 ≤
C
i
≤
W
≤ 10^8)
。每租⽤⼀辆缆⻋，Freda 和 rainbow 就要付
1
美元，所以他们想知道，最少需要付多少美元才能把这
N
只⼩猫都运送下⼭？
【输⼊描述】
第⼀⾏包含两个⽤空格隔开的整数，
N
和
W
。 接下来
N
⾏每⾏⼀个整数，其中第
i
+ 1
⾏的整
数表⽰第
i
只⼩猫的重量
C
i
。
【输出描述】
输出⼀个整数，最少需要多少美元，也就是最少需要多少辆缆⻋。
搜索策略：对于每每⼀只猫，我们都有两种处理⽅式：
*要么把这只猫放在已经租好的缆⻋上；
*要么重新租⼀个缆⻋，把这只猫放上去。
4.记忆化搜索
记忆化搜索也是⼀种剪枝策略。
通过⼀个"备忘录"，记录第⼀次搜索到的结果，当下⼀次搜索到这个状态时，直接在"备忘录"⾥⾯找结果。
记忆化搜索，有时也叫动态规划。
【题⽬描述】
斐波那契数 （通常⽤
F(n)
表⽰）形成的序列称为 斐波那契数列 。该数列由
0
和
1
开始，后
⾯的每⼀项数字都是前⾯两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定
n
，请计算
F(n)
。
【算法原理】
在搜索的过程中，如果发现特别多完全相同的⼦问题，就可以添加⼀个备忘录，将搜索的结果放在备忘录中。下⼀次在搜索到这个状态时，直接在备忘录⾥⾯拿值
5.BFS
宽度优先搜索的过程中，每次都会从当前点向外扩展⼀层，所以会具有⼀个最短路的特性。因此，宽搜不仅能搜到所有的状态，⽽且还能找出起始状态距离某个状态的最⼩步数。
但是，前提条件是每次扩展的代价都是1 ，或者都是相同的数。宽搜常常被⽤于解决边权为 1的最
短路问题。
【题⽬描述】
有⼀个 的棋盘，在某个点 上有⼀个⻢，要求你计算出⻢到达棋盘上任意⼀个点最少
要⾛⼏步。
n
×
m
(
x
,
y
)
【输⼊描述】
输⼊只有⼀⾏四个整数，分别为
n
,
m
,
x
,
y
。
【输出描述】
⼀个
n
×
m
的矩阵，代表⻢到达某个点最少要⾛⼏步（不能到达则输出
−1
）。
【题⽬描述】
FJ 丢失了他的⼀头⽜，他决定追回他的⽜。已知 FJ 和⽜在⼀条直线上，初始位置分别为x 和y ，
假定⽜在原地不动。FJ 的⾏⾛⽅式很特别：他每⼀次可以前进⼀步、后退⼀步或者直接⾛到2*x
的位置。计算他⾄少需要⼏步追上他的⽜。
【输⼊描述】
第⼀⾏为⼀个整数
t
(1 ≤
t
≤ 10)
，表⽰数据组数；
接下来每⾏包含⼀个两个正整数
x
,
y
(0 <
x
,
y
≤ 10 )
5
，分别表⽰ FJ 和⽜的坐标。
【输出描述】
对于每组数据，输出最少步数。
八数码难题
【题⽬描述】
在 的棋盘上，摆有⼋个棋⼦，每个棋⼦上标有 1⾄8 的某⼀数字。棋盘中留有⼀个空格，空格⽤ 0来表⽰。空格周围的棋⼦可以移到空格中。要求解的问题是：给出⼀种初始布局（初始状态）和⽬标布局（为了使题⽬简单,设⽬标状态为123804765 ），找到⼀种最少步骤的移动⽅法，实现从初始布局到⽬标布局的转变。
【输⼊描述】
输⼊初始状态，⼀⾏九个数字，空格⽤
0
表⽰。
【输出描述】
只有⼀⾏，该⾏只有⼀个数字，表⽰从初始状态到⽬标状态需要的最少移动次数。保证测试数据中⽆
特殊⽆法到达⽬标状态数据。
6.多源BFS
多源最短路问题的边权都为
1
时，此时就可以⽤多源 BFS 来解决。
把这些源点汇聚在⼀起，当成⼀个"超级源点"。然后从这个"超级源点"开始，处理最短路问题。落实到代码上时：
1.
初始化的时候，把所有的源点都加⼊到队列⾥⾯；
2.
然后正常执⾏ bfs 的逻辑即可。
也就是初始化的时候，⽐普通的 bfs 多加⼊⼏个起点。
题：刺杀大使
7.01BFS
