厦门建网站哪家好,手机编程网站,wordpress中能搜索到form中的文字吗,网站seo如何做好优化搜索与回溯讲解 文章目录深搜方向向量#xff1a;DFS代码#xff1a;题目讲解#xff1a;八皇后问题字符序列自然数的拆分广搜BFS代码#xff1a;题目讲解#xff1a;瓷砖关系网络bfs与dfs的用途与区别搜索剪枝可行性剪枝最优性剪枝记忆化搜索搜索顺序剪枝题目#xff1a…搜索与回溯讲解
文章目录深搜方向向量DFS代码题目讲解八皇后问题字符序列自然数的拆分广搜BFS代码题目讲解瓷砖关系网络bfs与dfs的用途与区别搜索剪枝可行性剪枝最优性剪枝记忆化搜索搜索顺序剪枝题目[NOIP2002 提高组] 字串变换状压搜索例题深搜
DFS 一股莽到底然后再找下一个如果无法拓展则退回一步到上一个状态再按照原先设定的规则顺序重新寻找一个状态拓展。 例子走迷宫不走到路的尽头不回头 得到的序列V0V1V2V6V5V3V4 代码
void dfs(int dep, 参数表 );{自定义参数 ;if( 当前是目标状态 ){输出解或者作计数、评价处理 ;}elsefor(i 1; i 状态的拓展可能数 ; i)if( 第 i 种状态拓展可行 ){维护自定义参数 ;dfs(dep1, 参数表 );}
}
回溯 “回溯法”也称“试探法”。它是从问题的某一状态出发不断“试探”着往前走一步当一条路走到“尽头”不能再前进拓展出新状态的时候再倒回一步或者若干步从另一种可能的状态出发继续搜索直到所有的“路径状态”都一一试探过。这种不断前进、不断回溯寻找解的方法称为“回溯法”。
void search(int dep){自定义参数 ;if( 当前是目标状态 ){输出解或者作计数和评价处理 ;}elsefor(i 1; i 状态的拓展可能数 ; i)if( 第 i 种状态拓展可行 ){保存现场 ( 断点 ), 维护自定义参数 ;search(dep1);恢复现场 , 回溯到上一个断点继续执行 ;}
}
深度优先搜索可以采用递归系统栈和非递归手工栈两种方法实现
方向向量
int dir[4][2] {0,1,0,-1,1,0,-1,0}; // 方向向量(x,y)周围的四个方向
-------
int dx[]{1,0,-1,0}
int dy[]{0,1,0,-1}DFS代码
/*
该DFS 框架以2D 坐标范围为例来体现DFS 算法的实现思想。
*/
#includecstdio
#includecstring
#includecstdlib
using namespace std;
const int maxn100;
bool vst[maxn][maxn]; // 访问标记
int map[maxn][maxn]; // 坐标范围
int dir[4][2] {0,1,0,-1,1,0,-1,0}; // 方向向量(x,y)周围的四个方向
bool CheckEdge(int x,int y) { // 边界条件和约束条件的判断if(!vst[x][y] ...) // 满足条件return 1;else // 与约束条件冲突return 0;
}
void dfs(int x,int y) {vst[x][y]1; // 标记该节点被访问过if(map[x][y]G) { // 出现目标态G...... // 做相应处理return;}for(int i0; i4; i) {if(CheckEdge(xdir[i][0],ydir[i][1])) // 按照规则生成下一个节点dfs(xdir[i][0],ydir[i][1]);}return; // 没有下层搜索节点回溯
}
int main() {......return 0;
}题目讲解
八皇后问题
在国际象棋棋盘上8*8放置八个皇后使得任意两个皇后之间不能在同一行同一列也不能位于同于对角线上。问共有多少种不同的方法并且按字典序从小到大指出各种不同的放法。思路 枚举1N的全排列每列举完一组然后就在该组排列中测试当前方案是否合法排列中每个元素与该排列中其他的元素不在横、竖、斜线上 代码
#include cstdio
#include cstdlibconst int MAXN 100;
int N;
bool hashTable[MAXN] {false};
int P[MAXN];
int count 0;void DFS(int index){//朴素算法if(index N 1){bool flag true;//flag为true表示当前方案合法for (int i 1; i N ; i)//遍历两个皇后{for (int j i 1; j N; j){//第四象限内P[y]为纵坐标i、j为横坐标if(abs(i - j) abs(P[j] - P[i])){//如果在一条对角线上也就是正方形相对的两个端点flag false;}}}if(flag true) {count;for (int i 1; i N; i){printf(%d, P[i]);if(i N - 1) printf( );}printf(\n);}}for (int i 1; i N; i)//全排列{if(hashTable[i] false){P[index] i;hashTable[i] true;DFS(index 1);hashTable[i] false;}}
}int main(){scanf(%d, N);DFS(1);if(count 0) printf(no solute!\n);return 0;
}
字符序列
题目描述
从三个元素的集合[ABC]中选取元素生成一个 N 个字符组成的序列使得没有两个相邻的子序列子序列长度2相同。例N 5 时 ABCBA 是合格的而序列 ABCBC 与 ABABC 是不合格的因为其中子序列 BCAB 是相同的。 对于由键盘输入的 N(1N12)求出满足条件的 N 个字符的所有序列和其总数。
思路 依旧靠模拟现在数组中的元素并且判断相邻两个 元素构成的子序列是否是满足条件的解是就进行 计数并搜索下一层
代码
#includecstdio
#define ll long long
ll a[1000005],n,sum;
bool check(int p)
{return p3a[p-3]*10a[p-2]a[p-1]*10a[p];
}
void dfs(int p)
{ll i;//要每次都重新定义i的变量不然在调用的时候会改变外层搜索的i变量 for(i1;i3;i){a[p]i;if(check(p))//只用判断相邻的字符串之前的是因为判断了所有的情况 continue;else{if(pn)sum;elsedfs(p1);}}
}
int main()
{scanf(%lld,n);dfs(1);printf(%lld,sum);
}
自然数的拆分
题目描述
任何一个大于1的自然数n总可以拆分成若干个小于n的自然数之和。
当n7共14种拆分方法
71111111
7111112
711113
711122
71114
71123
7115
71222
7124
7133
716
7223
725
734输入一个n按字典序输出具体的方案。
输入样例
7
输出样例
1111111
111112
11113
11122
1114
1123
115
1222
124
133
16
223
25
34题解 层层分解按照dfs的顺序进行
代码
#includecstdio
int a[1005]{1},n;
int print(int t)
{int i;for(i1;it-1;i)printf(%d,a[i]);if(a[t-1]!n)printf(%d\n,a[t-1]);
}
int search(int s,int t)
{int i;if(s0)print(t);for(ia[t-1];is;i){a[t]i;search(s-i,t1);}
}
int main()
{scanf(%d,n);search(n,1);
}
广搜
BFS 应用产生式规则和控制策略生成多层结点 广搜是扩散式的 例子眼镜掉在地上趴在地板上找一开始先搜最接近的地方如果没有再摸远一点的地方距离依次增加 得到的一个序列为 V0V1V2V3V4V6V5。 宽度优先搜索是一种“盲目”搜索所有结点的拓展都遵循“先进先出”的原则所以采用“队列”来存储这些状态。宽度优先搜索的算法框架如下
void BFS{while (front rear){// 当队列非空时做front 和 rear 分别表示队列的头指针和尾指针 if (找到目标状态)做相应处理(如退出循环输出解、输出当前解、比较解的优劣);else{拓展头结点 ;if( 拓展出的新结点没出现过 ){rear;将新结点插到队尾 ;}}front;// 取下一个结点}
}
BFS代码
#includecstdio
#includecstring
#includequeue
#includealgorithm
using namespace std;
const int maxn 100;
bool vst[maxn][maxn]; // 访问标记
int dir[4][2] {0,1,0,-1,1,0,-1,0}; // 方向向量
struct State { // BFS 队列中的状态数据结构int x, y; // 坐标位置int Step_Counter; // 搜索步数统计器
};
State a[maxn];
bool CheckState(State s) { // 约束条件检验if(!vst[s.x][s.y] ...) // 满足条件return 1;else // 约束条件冲突return 0;
}
void bfs(State st) {queue State q; // BFS 队列State now, next; // 定义2 个状态当前和下一个st.Step_Counter 0; // 计数器清零q.push(st); // 入队vst[st.x][st.y] 1; // 访问标记while(!q.empty()) {now q.front(); // 取队首元素进行扩展if(now G) { // 出现目标态此时为Step_Counter 的最小值可以退出即可...... // 做相关处理return;}for(int i 0; i 4; i) {next.x now.x dir[i][0]; // 按照规则生成下一个状态next.y now.y dir[i][1];next.Step_Counter now.Step_Counter1; // 计数器加1if(CheckState(next)) { // 如果状态满足约束条件则入队q.push(next);vst[next.x][next.y] 1; //访问标记}}q.pop(); // 队首元素出队}return;
}
int main() {......return 0;
}题目讲解
瓷砖 在一个 w×h 的矩形广场上每一块 1×1 的地面都铺设了红色或黑色的瓷砖。小林同学站在某一块黑色的瓷砖上他可以从此处出发移动到上、下、左、右四个相邻的且是黑色的瓷砖上。现在他想知道通过重复上述移动所能经过的黑色瓷砖数。 样例
样例输入
11 9
. # . . . . . . . . .
. # . # # # # # # # .
. # . # . . . . . # .
. # . # . # # # . # .
. # . # . . # . # .
. # . # # # # # . # .
. # . . . . . . . # .
. # # # # # # # # # .
. . . . . . . . . . .
样例输出
59题解 找到小林的初始位置“”并把坐标入队作为队头元素。宽度优先搜索检查队头元素的上、下、左、右四个位置是否是黑色瓷砖“.”是则入队……不断取出队头元素进行四个方向的拓展直到队列为空。 为了避免一个位置被多次重复走到定义一个布尔型数组 vis[i,j]用来判重位置ij为黑色瓷砖设置为 true红色的或者走过的瓷砖设置为 false 最后队列内元素数量 在本题中其实还牵扯一个应用联通块 代码
#includeiostream
#includequeue
using namespace std;const int N 25;
char map[N][N];
int n, m;
int dx[] {1, 0, -1, 0}, dy[] {0, 1, 0 , -1};
int ans;// 判断 (x, y) 是否在地图中
bool inmap(int x, int y) {return x 0 x m y 0 y n;
}void bfs(int x, int y) {queuepairint, int q;// 首先将当前位置改为 # 表示已经走过了map[x][y] #;// 将x, y加入到队列中q.push({x, y});while (!q.empty()) {// 取出队列的头结点pairint, int xy q.front();q.pop();// 向4个方向拓展for (int i 0; i 4; i) {int x1 xy.first dx[i], y1 xy.second dy[i];// 如果下一个要走的点在地图内并且为黑色砖块那么就将该点改为 # 并加入到队列中if (inmap(x1, y1) map[x1][y1] .) {q.push({x1, y1});map[x1][y1] #;ans;}}}
}int main() {// 输入 n 列 m 行cin n m;while (n ! 0 m ! 0) {for (int i 0; i m; i) {for (int j 0; j n; j) {cin map[i][j];}}queuepairint, int p;// 找到开始的地点int x, y;for (int i 0; i m; i) {for (int j 0; j n; j) {if (map[i][j] ) {x i;y j;break;}}}// bfs// 每次将 ans 初始化为 1因为出发点算一个ans 1;bfs(x, y);cout ans endl;cin n m;}return 0;
}
关系网络
描述 有N个人编号为1到N其中有一些人互相认识现在x想认识y,可以通过他所认识的人来认识更多的人 如果x认识y,y认识z,则x可以通过y来认识z,求出x最少需要通过多少人才能认识y 输入 5 1 5 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 1 0 0 0 1 0 输出 2 思路 典型的BFS直接搜就行了最后输出时记得减一因为要到达的人自己不算。 代码
#includebits/stdc.h
using namespace std;
int n,x,y;
struct node{int num;//编号 int t;//步数 node(){}node(int sum,int tt){numsum;ttt;}
};
int mp[101][101];//图
bool flag[101];//标记
queuenode q;
void bfs()
{q.push(node(x,0));flag[x]true;//打标记 while(!q.empty()){node headq.front();q.pop();if(head.numy){couthead.t-1;//一定要减一 return;}for(int i1;in;i){if(mp[head.num][i]!flag[i]){flag[i]true;q.push(node(i,head.t1));}}}}int main(){cinnxy;for(int i1;in;i){for(int j1;jn;j){cinmp[i][j];//存图 }}bfs();
}bfs与dfs的用途与区别
1.BFS是用来搜索最短径路的解是比较合适的比如求最少步数的解最少交换次数的解因为BFS搜索过程中遇到的解一定是离根最近的所以遇到一个解一定就是最优解此时搜索算法可以终止。这个时候不适宜使用DFS因为DFS搜索到的解不一定是离根最近的只有全局搜索完毕才能从所有解中找出离根的最近的解。当然这个DFS的不足可以使用迭代加深搜索ID-DFS去弥补 2.空间优劣上DFS是有优势的DFS不需要保存搜索过程中的状态而BFS在搜索过程中需要保存搜索过的状态而且一般情况需要一个队列来记录。 3.DFS适合搜索全部的解因为要搜索全部的解那么BFS搜索过程中遇到离根最近的解并没有什么用也必须遍历完整棵搜索树DFS搜索也会搜索全部但是相比DFS不用记录过多信息所以搜素全部解的问题DFS显然更加合适。
搜索剪枝
常用的搜索有Dfs和Bfs。
Bfs的剪枝通常就是判重因为一般Bfs寻找的是步数最少重复的话必定不会在之前的情况前产生最优解。
深搜它的进程近似一颗树(通常叫Dfs树)。
而剪枝就是一种生动的比喻把不会产生答案的或不必要的枝条“剪掉”。
剪枝的关键就在于剪枝的判断什么枝该剪什么枝不该剪在什么地方减。 正确性准确性高效性。
常用的剪枝有可行性剪枝、最优性剪枝、记忆化搜索、搜索顺序剪枝。
可行性剪枝
如果当前条件不合法就不再继续搜索直接return。这是非常好理解的剪枝
最优性剪枝
如果当前条件所创造出的答案必定比之前的答案大那么剩下的搜索就毫无必要甚至可以剪掉。
我们利用某个函数估计出此时条件下答案的‘下界’将它与已经推出的答案相比如果不比当前答案小就可以剪掉。
比如 在搜索取和最大值时如果后面的全部取最大仍然不比当前答案大就可以返回。 在搜和最小时同理可以预处理后缀最大/最小和进行快速查询。
long long ans987474477434487ll;
... Dfs(int x,...)
{if(x... ...){ans....;return ...;}if(check2(x)ans)return ...; //最优性剪枝 for(int i1;...;i){vis[...]1; dfs(...);vis[...]0;}
}记忆化搜索
之后dp会讲
搜索顺序剪枝
在一些迷宫题网格题或者其他搜索中可以贪心的题搜索顺序显得十分重要 其实在迷宫、网格类的题目中以左上-右下为例右下左上就明显比左上右下优秀。
题目
[NOIP2002 提高组] 字串变换
题目描述 给字符串A和B然后给出最多6个变换规则 A1 - B1 问A能否变成B
输入
abcd xyz
abc xu
ud y
y yz3题解 题目一共就6个变换规则而且问最少步数基本上就锁定是广搜不仅可以寻找解而且还能判断步数 起点为a串搜索目标为b串中间的路径是给出的变换关系 我们用一个map来记录某个串是否被搜索过 对于串str我们从第i为看是否能用第j种手段改变如果拼接出的串是合法的那么我们就把这个串继续压入队列再次搜索中间记录一下步数step和ans。 代码
#includebits/stdc.h //万能头文件
using namespace std;
string a,b; //字符串A与字符串B
string sa[8],sb[8]; //存放6种转换方式
mapstring,int map1; //用map存放已经宽搜过的字符串用来判重剪枝否则会超时
int l; //有l种转换方式
queuestring q; //存放转换出来的字符串
queueint bb; //存放当前转换出来的字符串已经使用的步数
int bfs()
{int i,j,k,m,n;string s,ss;while (q.empty()0q.front()!bbb.front()10) //当还能继续转换且没转换出字符串B且步数也没有超出10步时进行宽搜{if (map1[q.front()]1) //剪枝如果当前字符串已经宽搜过了,就弹出,进入下一次循环.{q.pop();bb.pop();continue;}map1[q.front()]1; //记录下该字符串for (i1;il;i) //循环出每一种转换方式{ sq.front(); //将S赋值为当前要操作的字符串while (1) //找出子串sa[i]的所有位置{ ms.find(sa[i]); //在S里查找子串sa[i]的第一次出现位置if (m-1) break; //如果全找出来(找不到)了,就结束循环ssq.front(); //将SS赋值为当前要操作的字符串ss.replace(m,sa[i].size(),sb[i]); //在SS中用子串sb[i]替换掉S里第一次出现的子串sa[i]q.push(ss); //将转换后的SS压入队列bb.push(bb.front()1); //将转换后的SS已经使用的步数压入队列s[m]~; //将S里子串sa[i]的第一次出现位置随便换成另一种无关的字符,//这样就可以查找到S里子串sa[i]的下一个出现位置}}q.pop(); //将操作过的字符串弹出队列bb.pop(); //操作过的字符串已经用过的步数一块弹出}if (q.empty()1||bb.front()10) return -1;//没法再进行宽搜,或者超出步数,就返回-1else return bb.front(); //否则,就是找到了,便返回最少使用步数
}
int main()
{int i,j,k,m,n;cinab; //读入字符串A与字符串Bl1;while (cinsa[l]sb[l]) l; //读入转换方式l--; //l初始值为1,所以要减1,才能表示转换方式的数量if (l0a!b) //若果没有转换方式且A也不等于B,直接输出NO ANSWER!(其实这步可以不要){coutNO ANSWER!;return 0;}q.push(a); //将字符串A压入队列bb.push(0); //将初始步数0压入队列kbfs(); //宽搜if (k-1) //返回-1说明NO ANSWER!{coutNO ANSWER!;return 0;}coutk; //输出最小步数
}状压搜索
就是在搜索过程中应用了状态压缩思想 状态压缩原状态不容易表达或者状态太多内存不够用所以用一个数的二进制表示状态可以节省很多内存空间当然也有使用的局限性 例子 一排10个座位编号从左到右分别是1到10 其中第2,46,8的位置上没人我们如何记录这个状态 有人的是1没人的是0 1101110101二进制 ---- 按位与可以将某个数的某二进制位置为0也可以用于取出某个二进制位
| ---- 按位或可以将某个数的某二进制位置为1.
~ ---- 非将一个数的所有二进制位取反
^ ---- 异或相同为0不同为1常为BFS与状态压缩结合因为用DFS不好保存状态写起来麻烦些
例题
hdu 5094 Maze
