迭代加深搜索，實(shí)質(zhì)上是限定下界的深度優(yōu)先搜索。即首先允許深度優(yōu)先搜索K層，若沒有發(fā)現(xiàn)可行解，再將K+1后

重復(fù)以上步驟搜索，直到搜索到可行解。

在迭代加深搜索的算法中，連續(xù)的深度優(yōu)先搜索被引入，每一個(gè)深度約束逐次加1，直到搜索到目標(biāo)為止。這樣可以

看出重復(fù)搜索了好多。但是它的好處在于：

1.空間開銷小? ?每個(gè)深度下實(shí)際上是一個(gè)深度優(yōu)先搜索，不過深度有限制，而DFS的空間消耗小是眾所周知的。

2.利于深度剪枝

3.時(shí)間效率不低 雖然重復(fù)搜索，但是大家不難理解，前一次搜索跟后一次相不是微不足到的。

我們可以看出，迭代加深搜索算法就是仿廣度優(yōu)先搜索的深度優(yōu)先搜索。既能滿足深度優(yōu)先搜索的線性存儲(chǔ)要求，又能保證發(fā)現(xiàn)一個(gè)最小深度的目標(biāo)結(jié)點(diǎn)。

從實(shí)際應(yīng)用來看，迭代加深搜索的效果比較好，并不比廣度優(yōu)先搜索慢很多，但是空間復(fù)雜度卻與深度優(yōu)先搜索相同，比廣度優(yōu)先搜索小很多。

使用搜索算法的時(shí)候，選擇正確的搜索方式很重要。當(dāng)有一類問題需要做廣度優(yōu)先搜索，但卻沒有足夠的空間，而時(shí)間卻很充裕，碰到這類問題，我們可以選擇迭代加深搜索算法。

題目：http://acm.nefu.edu.cn/JudgeOnline/problemshow.php?problem_id=358

題意：給你個(gè)真分?jǐn)?shù)，你需要將其化簡(jiǎn)為最少的若干特殊真分?jǐn)?shù)之和，你要輸出這個(gè)序列（序列按遞增序）。如果有不同的方案，則分?jǐn)?shù)個(gè)數(shù)相同的情況下使最大的分母最小。若還相同，則使次大的分母最大……以此類推。如：2/3=1/2+1/6，但不允許2/3=1/3+1/3，因?yàn)榧訑?shù)中有相同的。對(duì)于一個(gè)分?jǐn)?shù)a/b，表示方法有很多種，但是哪種最好呢？?首先，加數(shù)少的比加數(shù)多的好，其次，加數(shù)個(gè)數(shù)相同的，最小的分?jǐn)?shù)越大越好。

#include <iostream> #include <string.h> #include <stdio.h>using namespace std; typedef long long LL; const int INF = ~0U>>1; const int N = 10;int dep,flag; int ans[N],d[N];int gcd(int a,int b) {return b ? gcd(b,a%b):a; }void dfs(int a,int b,int k) {if(k == dep + 1) return;if(b % a == 0 && b / a > d[k-1]){d[k] = b / a;if(!flag || d[k] < ans[k])memcpy(ans,d,sizeof(d));flag = 1;return;}int s = b / a;if(s <= d[k-1]) s = d[k-1] + 1;int t = (dep - k + 1) * b / a;if(t > INF / b) t = INF / b;if(flag && t >= ans[dep]) t = ans[dep] - 1;for(int i=s;i<=t;i++){d[k] = i;int m = gcd(i*a - b,b*i);dfs((i*a-b)/m,b*i/m,k+1);} }void Work(int a,int b) {d[0] = 1;flag = 0;for(dep=1;dep <= N;dep++){dfs(a,b,1);if(flag){printf("1/%d",ans[1]);for(int i=2;i<=dep;i++)printf("+1/%d",ans[i]);cout<<endl;break;}} }int main() {int a,b;while(cin>>a>>b){cout<<a<<"/"<<b<<"=";Work(a,b);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的迭代加深搜索与埃及分数求解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。