IDA*
演算法分析
IDA* 本質上就是帶有估價函式和迭代加深優化的dfs與，A * 相似A *的本質便是帶
有估價函式的bfs,估價函式是什么呢?估價函式顧名思義，就是估計由目前狀態達
到目標狀態的總費用，這個費用可以是距離，可以是路程，估價函式用于對dfs過
程進行優化，由當前狀態借助估價函式判斷怎么搜索更優，從而去走較優的狀態，
\[f(n)=g(n)+h(n); \]\(f(n)\)就是我們的估價函式，\(n\)表示當前狀態，\(g(n)\)表示由當前狀態的費用，
\(h(n)\)當前狀態到目標狀態的費用，估價函式的設計因題而異，一道題的估價函式
也有很多種，不同設計方案對dfs起到的優化作用不同，\(h(n)\)設計的越準確，對dfs
的優化越高，但如果求h(n)太復雜也沒有什么實際意義，也就是說，\(h(n)\)不保證絕對準確
介紹完估價函式，我們再來介紹迭代加深優化，什么是迭代加深優化？其本質就是對
搜索層數進行限制，避免無意義的搜索，比如需要找到的答案在搜索樹的第四層，我
們先搜第一層，設定搜索上限深度為1 ，我們搜索搜索樹的第一層，沒找到答案，停
止搜索，搜索上限+1,繼續從起點進行搜索，直到找到答案，為什么這樣可以對dfs起
到優化？考慮一顆深度非常大，并且答案在較小層的右側的樹，如果普通進行dfs明
顯是很慢的，這時候IDA * 的優點就顯現出來了
例題
[SCOI2005]騎士精神
以此題舉例
下面是代碼
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int maxn=100;
int t;
char ca;
int x1,y1;
int map[maxn][maxn];
int cr[maxn][maxn]={
{0,0,0,0,0,0},
{0,1,1,1,1,1},
{0,0,1,1,1,1},
{0,0,0,2,1,1},
{0,0,0,0,0,1},
{0,0,0,0,0,0}
};//目標狀態
int gu(){//估價函式
int cnt=0;
for(int i=1;i<=5;i++){
for(int j=1;j<=5;j++){
if(map[i][j]!=cr[i][j]){
cnt++;
}
}
}
return cnt;
}
bool success=0;
int y2[maxn]={0,2,-2,2,-2,1,-1,1,-1};
int x2[maxn]={0,-1,-1,1,1,2,2,-2,-2};
void astar(int deep,int x,int y,int us){
if(us==deep){
if(!gu()){
success=1;
// cout<<1;
return ;
}
}
for(int i=1;i<=8;i++){
int xx=x;
int yy=y;
xx=x+x2[i];
yy=y+y2[i];
if(xx<1||xx>5||yy>5||yy<1){
continue;
}
swap(map[xx][yy],map[x][y]);
// cout<<xx<<" "<<yy<<" "<<x<<" "<<y<<endl;
if(us+gu()>deep){
swap(map[xx][yy],map[x][y]);
continue;
}
if(success){
return ;
}
astar(deep,xx,yy,us+1);
swap(map[xx][yy],map[x][y]);
}
return ;
}
int main(){
freopen("a.txt","r",stdin);
cin>>t;
while(t--){
for(int i=1;i<=5;i++){
for(int j=1;j<=5;j++){
cin>>ca;
// cout<<ca<<" ";
if(ca=='*'){
x1=i;
y1=j;
map[i][j]=2;
// cout<<map[i][j]<<" ";
}
else{
map[i][j]=ca-'0';
// cout<<map[i][j]<<" ";
}
}
// cout<<endl;
}
// cout<<gu();
if(!gu()){
cout<<-1;//所給的圖符合題意，所以直接結束，此處剪枝優化比較明顯
return 0;
}
for(int i=1;i<=15;i++){
astar(i,x1,y1,0);
if(success){
cout<<i<<endl;
break;
}
}
if(!success){
cout<<-1<<endl;
}
success=0;
}
return 0;
}
完結撒花
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/175054.html
標籤：其他
上一篇：中國程式員最容易發音錯誤的單詞