深度优先搜索
排列组合
加法原理:加步骤
乘法原理:乘步骤
排列:排列是指从给定的一组元素中,按照一定的顺序选择部分或全部元素所形成的线性排列(位置不同算不同)
公式:Pnk=n!(n−k)!P_{n}^{k} = \frac{n!}{(n-k)!}Pnk =(n−k)!n!
组合:组合是指从给定的一组元素中,选择部分或全部元素所形成的组合,不考虑元素的顺序(位置不同算同)
公式:Cnk=n!(k!∗(n−k)!)C_{n}^{k} = \frac{n!}{(k! * (n-k)!)}Cnk =(k!∗(n−k)!)n!
回溯
以下为排列输出
剪枝
可以剪掉一些状态,避免重复
减少搜索量
类型
可行性剪枝:得不到答案的去掉
最优性简直:更坏的去掉
连通性问题
走迷宫
八皇后