黄岛开发区做网站网络公司,h5手机网站制作,常用网站建设软件,wordpress如何设置关键词迭代加深搜索 迭代加深算法是一在DFS的基础上添加搜索深度限制的搜索方法#xff1b; 其核心思想是从深度为0的地方开始搜索#xff0c;然后逐步加深搜索深度#xff0c;重新搜索一遍#xff1b;这对于那些已知答案在浅层#xff0c;但整个树或图存在极多分支的情况#… 迭代加深搜索 迭代加深算法是一在DFS的基础上添加搜索深度限制的搜索方法 其核心思想是从深度为0的地方开始搜索然后逐步加深搜索深度重新搜索一遍这对于那些已知答案在浅层但整个树或图存在极多分支的情况我们可以使用迭代加深搜索进而迅速找到目标节点或者遍历整张图限制深度下 除了图搜索问题外迭代加深搜索还可用于求解以下问题 组合优化问题在给定的搜索空间中找到满足特定条件的最优解 规划和调度问题在给定的资源约束下找到最优的计划或调度方案 参数优化问题在给定的参数空间中找到最优的参数设置以最大化或最小化特定的目标函数。
总的来说迭代优先搜索一般适用于解决那些带限制要求且无法确定查找深度的问题 板子
int deepth;//搜索深度bool dfs(int deep(, .....))
{if(deep deepth) return ; //当前深度超过则返回.........
}while(!dfs()) deepth;一般来说使用该算法还需视题目具体情况进行剪枝 L - DNA sequence 题目分析 1.每次搜索时有四个方向操作即四种DNA序列 2.组合优化问题 3.可以使用数组记录当前生成的字符串与所给字符串字母匹配的数目进而确定当前的最大查找深度 4.在搜索时如果当前深度最大未匹配长度 最大深度剪枝 5.多组输入注意数据初始化 Code
#include bits/stdc.h
using namespace std;
using ll long long;
using ull unsigned long long;
const int N 15;
//....
int deepth;
int ans;
int k;
char dna[5] {A,C,T,G};
char str[N][N];bool dfs(int deep, int len[])
{if(ans) return 1;if(deep deepth) return 0;int maxx 0; //预计还要匹配的最大深度for(int i 1; i k; i){int temp strlen(str[i]) - len[i];maxx max(temp, maxx);}if(deep maxx deepth) return 0; //若当前深度最大未匹配长度 最大深度直接放弃if(maxx 0) //全部匹配成功{ans deep;return 1;}for(int i 0; i 4; i){int flag 0;int pos[N];for(int j 1; j k; j){if(str[j][len[j]] dna[i]){flag 1; //标明该分支暂时正确可以继续往下搜索pos[j] len[j] 1; //新建数组避免该大分支下的其他分支调用错误数据回溯}else pos[j] len[j];}if(flag) dfs(deep 1, pos);}return 0;
}int main()
{ios::sync_with_stdio(0), cin.tie(0),cout.tie(0);int t; cin t;while(t--){cin k;ans 0;memset(str, 0, sizeof str);int maxn 0;for(int i 1; i k; i){cin str[i];int temp strlen(str[i]);maxn max(maxn, temp);}deepth maxn; //更新最大深度最长的DNA序列的长度int pos[N] {0};while(!dfs(0, pos)) deepth;cout ans \n;}return 0;
}多态 Java 引用变量有两个类型: 一个是编译时类型 一个是运行时类型。 编译时类型由声明该变量时使 用的类型决定运行时类型由实际赋给该变量的对象决定。 如果编译时类型和运行时类型不一致就可 能出现所谓的多态 (Polymorphism).
优势
允许不同类的对象共享相同的接口更为轻松地添加新的类和对象而不需要修改现有的代码。
