DFS
实现
void dfs(int step) //步长或图的一个顶点
{
//访问标记
if(/*跳出循环的条件*/) return; //return十分关键，否则循环将会无法跳出
/*函数主体，对功能进行实现*/
for(/*对现有条件进行罗列*/){//该顶点的相邻节点
if(/*判断是否合理*/){
//将条件修改
dfs(/*新的step*/)
/*！重中之重，当跳出那层循环后将数据全部归位，即回溯*/
}
}
}
优化
- 可行性剪枝
- 最优性剪枝
- 重复性剪枝
- 优化搜索顺序
- 记忆化搜索
应用
- 遍历图，小规模枚举搜索
回溯法
-
return回溯时恢复所有改变 -
遇到边界条件
-
多次遍历
BFS
实现
void bfs(s) {
q = new queue()
q.push(s), visited[s] = true//1把起点放入到队列当中
while (!q.empty()) {//4搜索到终点，算法结束(队列为空)
u = q.pop()//3取出队列中的队首元素，重复步骤2
for each edge(u, v) {
if (!visited[v]) {
q.push(v)//2从起点开始按照一定的规则走到其他的点，并放入队尾
visited[v] = true
}
}
}
}
优化
- 剪枝同BFS
- 记忆化搜索
- 优先队列迭代思想
应用
- 遍历图
- 最短路问题
- BFS 通过最短路径到达一个点
双向同时搜索&折半搜索
实现
折半搜索将数据和搜索过程分成两半搜索，然后再合并两半搜索的答案
双向同时搜索如下
将开始结点和目标结点加入队列 q
标记开始结点为 1
标记目标结点为 2
while (队列 q 不为空)
{
从 q.front() 扩展出新的 s 个结点
如果 新扩展出的结点已经被其他数字标记过
那么 表示搜索的两端碰撞 循环结束
如果 新的 s 个结点是从开始结点扩展来的
那么 将这个 s 个结点标记为 1 并且入队 q
如果 新的 s 个结点是从目标结点扩展来的
那么 将这个 s 个结点标记为 2 并且入队 q
}
优化
- 折半搜索排序后二分、双指针、哈希表
应用
- 寻找可行解且起终点确定用双向同时搜索
- 搜索各项互不干扰且搜索状态可逆用折半搜索
启发式搜索
实现
- 引入估价函数，估价函数代表完美估价，即实际下限
应用
- 易构造估价函数
A*BFS
实现
-
先记录当前成本g，加上估价函数h计算总成本f=g+h(完美估价，是花费代价的下限，最优解的代价)
-
然后从优先队列openlist取出总成本最小的状态更新相邻状态，优先使用新得到的方格(访问标记closelist)
-
添加父节点记录，到达终点后通过父节点返回得到最优路径
应用
- 对多节点路径求出最低通过成本的图遍历、最佳优先搜索、最短路，估价函数易构造
迭代加深搜索IDDFS
实现
-
每次DFS加上深度限制，近似BFS，寻找最优解
-
回溯过程中记录最优路径
应用
- 一定限制条件，输出所有解中的任意一组解
IDA*DFS
实现
-
迭代加深进行最优性剪枝
-
估价函数进行可行性剪枝
-
第一个解即最优解，估价函数是每次状态改变过程中的不变量
应用
- 题目限制条件，输出任意解，估价函数易求
DLX
实现
- X算法
- 对现有矩阵 M 选择并标记一行 r ，将 r 添加至集合 S 中
- 尝试所有 r 无解，算法结束
- 标记与 r 相关的行和列，得到新矩阵 M1
- 若 M1 空且 r 中全为1，则算法结束，解为删除的 r 组成的集合；若 M1 空且 r 中不全为1，恢复与 r 相关的行和列，跳转步骤1；若 M1 不为空，跳转步骤1
- 优化数据结构Dancing Link
- 每次优先选择列元素个数最少的一列进行删除，这样能保证程序具有一定的启发性，使搜索树分支最少
应用
- 将总集S中的所有数离散化，得到一个0-1矩阵模型M，每一行表示一个子集
- 将问题转化为在二值矩阵中寻找一组行，这组行中每列有且只有一个1的问题
- 精确覆盖问题和重复覆盖问题，建模时行表示决策、列表示状态条件，寻找一组决策，满足所有条件
#define IT(i, A, x) for(i=A[x]; i!=x; i=A[i])
const int M=1e5+5;
int ans, stk[M];
int n, m, idx, first[M], siz[M];//每行头节点、每列有几个元素
int L[M], R[M], U[M], D[M];//记录有效元素，左右上下
int col[M], row[M];//列行
void remove(const int &c)//通过标记假删除法删除第c列及相关行列
{
//不改变c列和相关元素的自身的指向，而是改变相邻元素的指向
int i, j;
L[R[c]]=L[c];R[L[c]]=R[c];//删除第0行的辅助列数组
IT(i, D, c)//删除c列有效元素有关行和列
IT(j, R, i)
U[D[j]]=U[j], D[U[j]]=D[j], --siz[col[j]];
}
void recover(const int &c)//恢复第c列及相关行列
{
int i, j;
IT(i, U, c)
IT(j, L, i)
U[D[j]]=D[U[j]]=j,++siz[col[j]];
L[R[c]]=R[L[c]]=c;
}
void build(const int &r, const int &c)//建立n行m列的十字链表(无元素)
{
n=r, m=c;
for(int i=0; i<=c; ++i)
{
L[i]=i-1, R[i]=i+1;
U[i]=D[i]=i;
}
L[0]=c, R[c]=0, idx=c;
memset(first, 0, sizeof(first));
memset(siz, 0, sizeof(siz));
}
void insert(const int &r, const int &c)//在第r行第c列插入元素(为“1”的元素)
{
row[++idx]=r, col[idx]=c, ++siz[c];
U[idx]=c, D[idx]=D[c], U[D[c]]=idx, D[c]=idx;
if(!first[r])
first[r]=L[idx]=R[idx]=idx;
else
{
L[idx]=first[r], R[idx]=R[first[r]];
L[R[first[r]]]=idx, R[first[r]]=idx;
}
}
bool dance(int dep)//递归地删除和还原各个行列的过程
{
int i, j, c=R[0];
if(!R[0]){
ans=dep;
return 1;
}
IT(i, R, 0)
if(siz[i]<siz[c]) c=i;//启发式删除
remove(c);
IT(i, D, c)
{
stk[dep]=row[i];//记录答案
IT(j, R, i)remove(col[j]);
if(dance(dep+1))return 1;
IT(j, L, i)recover(col[j]);
}
recover(c);
return 0;
}
