検索の概要
25896 ワード
検索概要検索アルゴリズムは、コンピュータの高性能を利用して、問題の一部またはすべての可能な状況を目的として窮屈に挙げ、問題の解を求める方法である.単純な列挙アルゴリズムに比べて一定の方向性と目標性がある.アルゴリズムは,解の空間において,一つの状態から(要求に応じて広がる)別の状態に移行し,このようにして進み,解の空間における状態を遍歴し,答え(目標の状態)を見つける.検索分類は検索という部分で主に入門するものがあります.例えば、二分、三分、BFS、DFS、その他の比較的総合的なアルゴリズムがあります.例えば、優先キュー+BFS、優先キューBFS+剪定、双方向BFS、DFS+剪定、DFS+パリティ剪定、BFS+剪定、BFS+判断テクニック、BFS+同余剪定など、とにかく複雑で種類が多すぎます.肝心なのは基礎を身につけてから異なるテーマの中で開拓することです.***1.二分探索の基本思想:単調で秩序ある集合の中で要素を探し、毎回集合を左右の2つの部分に分け、どの部分にあるかを判断し、集合の上下境界を調整し、目標要素が見つかるまで繰り返す.
2.三分探索の基本思想:二分法と同様に、ある凸性または凹形関数の極値を要求する必要があり、関数自体の表現式では容易に解くことができない場合、三分法で解に近づくことができる.注:単纯な2分、3分の検索のテーマは比较的に简単で、相応のテーマは検索のテーマの中の前のいくつかの道で、ここで回顧をしないで、相応のブログを见ることができます.
3.BFS基本思想:初期状態Sから,ルールを利用してすべての可能な状態を生成する.構成された次の層ノードは,ターゲット状態Gが出現しているかどうかをチェックし,出現していない場合は,その層のすべての状態ノードに対して,それぞれ規則を順次利用する.さらに次の層のすべての状態ノードを生成し,この層のすべての状態ノードに対してGが出現しているかどうかをチェックし,出現していない場合は,以上のようにして次の層のすべての状態ノードを生成し続け,このように1層ずつ展開する.ターゲットステータスが表示されるまで.
例題:1)Prime Path題意:2つの素数(4桁)を与えて、1番目の数が何回変換して2番目の素数を得ることができることを求めます.変換方式:変換数のいずれかの桁の数字(1位はゼロにできないが、他の変換数字は0~~9)であり、変換後の数も素数である.構想:bfs、検索は最短の経路を求めて、簡単に広さを優先して検索します;広さ優先探索のため,初めて探索したステップ数が最小のステップ数である.判断時の速度を高めるために;素数表を1つ打った.コード:
#include<iostream>
#include<cmath>
#include<queue>
using namespace std;
const int Max = 10005;
void funprime(){
for(int num = 1000; num < 10000; num ++){
prime[num] = true;
for(int i = 2; i <= sqrt(num); i ++)
if(num % i == 0){
prime[num] = false;
break;
}
}
} // 。
int izero(int num, int n){
int m[5], i; // m[5] ， ， 。
for(i = 1; i <= 4; i ++){
m[i] = num % 10;
num = num / 10;
}
m[n] = 0;
for(i = 1; i <= 4; i ++)
num += m[i] * pow(10, i - 1);
return num;
} // num n 0， num=8792,n=3， 8092。
int main(){
int n, sta, end;
bool prime[Max], visit[Max];
funprime();
cin >> n;
while(n --){
cin >> sta >> end;
if(sta == end){
cout << '0' << endl;
continue;
}
bool fine = false;
int steps = 0;
queue<int> pri;
pri.push(sta);
memset(visit, false, sizeof(visit));
visit[sta] = true;
while(!pri.empty() && !fine){
int t = pri.size();
steps ++;
while(t --){
int num = pri.front();
pri.pop();
for(int i = 1; i <= 4; i ++){
int n = izero(num, i);
for(int j = 0; j <= 9; j ++){
int now = n + j * pow(10, i - 1);
if(now == end){
fine = true; // fine == true, 。
break;
}
else if(prime[now] && !visit[now]){
pri.push(now);
visit[now] = true;
}
}
}
}
}
if(fine) cout << steps << endl;
else cout << "Impossible" << endl;
}
return 0;
}2)Pots題意:2つの容積がそれぞれaとbのpotを与え,以下の3つの操作方式により,一定ステップ数後に使者2つのpotのうちの1つの水量がcであるか否かを求める.1.FILL(i):ipotを水で満たします.2.DROP(i):ipotを空にします.3.POUR(i,j):ipotの水をjpotに注いで、ipotが空になるか、jpotが満タンになるまで.構想:bfsは最短経路を求め,各ノードのサブノード数が6個であるだけである.コード:
#include<iostream>
using namespace std;
const int Max = 101;
struct node{
int ope; int a; int b; node *pre;
}que[Max * Max]; // ，ope ，a,b pot 。
bool vis[Max][Max];
char str[6][10] = {"FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"};
// 。
int min(int a, int b){
return a < b ? a : b;
}
void print(node now){
if(now.pre != NULL){
print(*now.pre);
cout << str[now.ope] << endl;
}
}
void bfs(int a, int b, int c){
int steps = 0;
int head = 0, tail = 1;
que[0].a = que[0].b = 0;
que[0].pre = NULL;
while(tail - head > 0){
int count = tail - head;
while(count --){
node now = que[head];
if(now.a == c || now.b == c){
cout << steps << endl;
print(now);
return;
}
if(!vis[a][now.b]){
que[tail].ope = 0;
que[tail].a = a;
que[tail].b = now.b;
que[tail].pre = &que[head];
vis[a][now.b] = true;
tail ++;
}
if(!vis[now.a][b]){
que[tail].ope = 1;
que[tail].a = now.a;
que[tail].b = b;
que[tail].pre = &que[head];
vis[now.a][b] = true;
tail ++;
}
if(!vis[0][now.b]){
que[tail].ope = 2;
que[tail].a = 0;
que[tail].b = now.b;
que[tail].pre = &que[head];
vis[0][now.b] = true;
tail ++;
}
if(!vis[now.a][0]){
que[tail].ope = 3;
que[tail].a = now.a;
que[tail].b = 0;
que[tail].pre = &que[head];
vis[now.a][0] = true;
tail ++;
}
int wat1 = min(now.a, b - now.b);
if(!vis[now.a - wat1][now.b + wat1]){
que[tail].ope = 4;
que[tail].a = now.a - wat1;
que[tail].b = now.b + wat1;
que[tail].pre = &que[head];
vis[now.a - wat1][now.b + wat1] = true;
tail ++;
}
int wat2 = min(a - now.a, now.b);
if(!vis[now.a + wat2][now.b - wat2]){
que[tail].ope = 5;
que[tail].a = now.a + wat2;
que[tail].b = now.b - wat2;
que[tail].pre = &que[head];
vis[now.a + wat2][now.b - wat2] = true;
tail ++;
}
head ++;
}
steps ++;
}
cout << "impossible" << endl;
}
int main(){
int a, b, c;
cin >> a >> b >> c;
memset(vis, false, sizeof(vis));
vis[0][0] = true;
bfs(a, b, c);
return 0;
}4.DFSの基本思想:初期状態から、ルールを利用して検索ツリーの次の層のいずれかのノードを生成し、目標状態が現れていないかどうかを検査し、現れていない場合、この状態でルールを利用して次の層のいずれかのノードを生成し、再検査し、リーフノード(すなわち、新しい状態ノードを生成できない)まで繰り返し、それが目標状態でない場合、前の層の結果に遡る.検索を拡張する可能性のある別のブランチを取ります.同じ方法で目標状態が見つかるまで続けます.
例題:1)Graph Colloring:題名説明:1枚の無方向図を与えて、今図の中で白と黒を着て、隣接する2点の色が異なっていることを要求して、最も多い黒点の個数を求めます.方法:開始点dfsコードを列挙する:
#define N 105
#include<iostream>
#include<vector>
using namespace std;
vector<int>map[N];
int n,m,cnt,tmp;
int ans[N],path[N];
int color[N];
bool ok(int u,int flag)
{
for(int i=0;i<map[u].size();i++)
{
int v=map[u][i];
if(color[v]==flag)
return false;
}
return true;
}
void dfs(int u,int flag)
{
int i;
for(i=0;i<map[u].size();i++)
{
int v=map[u][i];
if(ok(v,!flag)&&color[v]==-1)
{
color[v]=!flag;
if(!flag==0)
path[tmp++]=v;
dfs(v,!flag);
}
}
}
int main()
{
int i,j,t,a,b;
cin>>t;
while(t--)
{
cin>>n>>m;
for(i=0;i<=n;i++)
map[i].clear();
while(m--)
{
scanf("%d%d",&a,&b);
map[a].push_back(b);
map[b].push_back(a);
}
cnt=0;
for(i=1;i<=n;i++)
{
memset(color,-1,sizeof(color));
path[0]=i;
tmp=1;
color[i]=0;
dfs(i,0);
if(tmp>cnt)
{
for(j=0;j<tmp;j++)
ans[j]=path[j];
cnt=tmp;
}
}
cout<<cnt<<endl;
cout<<ans[0];
for(i=1;i<cnt;i++)
cout<<" "<<ans[i];
cout<<endl;
}
return 0;
}2)Flip Gameの題意:4*4の行列で、各格は白か黒か.任意のグリッドを反対の色に変更すると、このグリッドの上、下、左、右の4つのグリッドも反対の色に変更されます(存在する場合).マトリクスのすべての格子を同じ色にするには、少なくとも何回か上の操作を実行する必要があります.構想:列挙+dfs.1つのキー:各グリッドに対して、0または1回しか反転できません(易証).したがって,列挙は2^16=4096の状態であり,最大16回の操作を実行するため可能である.コード:
#include<iostream>
using namespace std;
bool map[6][6], find = false;
int step;
int dr[5] = {-1, 0, 0, 0, 1};
int dc[5] = {0, -1, 0, 1, 0};
bool isgoal(){ // 。
for(int i = 1; i <= 4; i ++)
for(int j = 1; j <= 4; j ++)
if(map[i][j] != map[1][1])
return false;
return true;
}
void flip(int row, int col){ // (row,col) map[][] 。
for(int i = 0; i < 5; i ++){
int r = row + dr[i];
int c = col + dc[i];
map[r][c] = !map[r][c];
}
}
void dfs(int row, int col, int dep){ // (row,col) 。
if(dep == step){
find = isgoal();
return;
}
if(find || row == 5) return;
flip(row, col); // (row,col) 。
if(col < 4) dfs(row, col + 1, dep + 1);
else dfs(row + 1, 1, dep + 1);
flip(row, col); // ， (row,col) 。
if(col < 4) dfs(row, col + 1, dep);
else dfs(row + 1, 1, dep);
}
int main(){
char c;
for(int i = 1; i <= 4; i ++)
for(int j = 1; j <= 4; j ++){
cin >> c;
if(c == 'b') map[i][j] = true;
}
for(step = 0; step <= 16; step ++){ // 0 ~ 16 。
dfs(1, 1, 0);
if(find) break;
}
if(find) cout << step << endl;
else cout << "Impossible" << endl;
return 0;
}