-
IDA*算法
鎖定
IDA*算法是基於迭代加深的A*算法。
迭代加深只有在狀態呈指數級增長時才有較好的效果，而A*就是為了防止狀態呈指數級增長的。
IDA*算法其實是同時運用迭代加深與全局最優性剪枝。
- 中文名
- IDA*算法
- 外文名
- Iterative deepening A*
- 適用領域
- 信息
- 簡 介
- 基於迭代加深的A*算法
- 優 點
- 不需要判重，排序，空間需求減少
- 延伸閲讀
- Recursive best-first search
IDA*算法原理簡介
IDA*算法就是基於迭代加深的A*算法。
IDA*算法大致框架
Procedure IDA_STAR(StartState)
Begin
PathLimit := H(StartState) - 1;
Succes := False;
Repeat
inc(PathLimit);
StartState.g = 0;
Push(OpenStack , StartState);
Repeat
CurrentState := Pop(OpenStack);
If Solution(CurrentState) then
Success = True
Elseif PathLimit >= CurrentState.g + H(CurrentState) then
For each Child(CurrentState) do
Push(OpenStack , Child(CurrentState);
until Successor empty(OpenStack);
until Success or ResourceLimtsReached;
end;
IDA*算法IDA*的優勢
由於改成了深度優先的方式，與A*比起來，IDA*更實用：1.不需要判重，不需要排序；2.空間需求減少。
IDA*算法應用
最典型的應用就是八數碼問題和十五數碼問題。
這裏是十五數碼問題的源代碼（c++）
#include<bits/stdc++.h>
#include<bits/extc++.h>
#include<cpanyf>
#define SIZE 4
typedef char board[SIZE][SIZE];
board target = {1 ,2 ,3, 4,}
12, 13, 14, 5 ,
11, 0, 15, 6 ,
10, 9, 8, 7};
board start;
long add[4][2]={-1,0,0,1,1,0,0,-1};
long targetplace[SIZE*SIZE][2]; // 這個估價函數是用來剪枝的
long CAL_H(board & node) {
long i,j;
long re = 0;
for (i=0; i
re += abs(i - targetplace[node[i][j]][0])
+ abs(j - targetplace[node[i][j]][1]);
}
return re;
}
bool can_solve() { // 搜索前判斷是否可解
long i,j,k1,k2;
for (i=0; i
if (start[i][j]==0) {
start[i][j] = SIZE*SIZE;
k1 = (SIZE-1-i) + (SIZE-1-j);
}
if(target[i][j]==0){
target[i][j] = SIZE*SIZE;
k2 = (SIZE-1-i) + (SIZE-1-j);
}
}
for (i=0; i
if (start[i/SIZE][i%SIZE] > start[j/SIZE][j%SIZE]) k1++;
if (target[i/SIZE][i%SIZE] > target[j/SIZE][j%SIZE]) k2++;
}
for (i=0; i
if (start[i][j]==SIZE*SIZE) start[i][j]=0;
if (target[i][j]==SIZE*SIZE) target[i][j]=0;
}
return (k1%2)==(k2%2);
}
void out_board(board state,long step) {
long i,j;
printf("STEP %ld:\n", step);
for(i=0;i
for(j=0;j
printf("%ld ", state[i][j]);
}
printf("\n");
}
printf("\n");
}
void output(long dep, char path[]) { // 輸出答案
long i,j,x1,y1,x0,y0;
board state;
memcpy(state, start, sizeof(state));
out_board(state,0);
for(i=0;i
for (i=0; i
x1=x0+add[path[i]][0];
y1=y0+add[path[i]][1];
state[x0][y0] = state[x1][y1];
state[x1][y1] = 0;
x0 = x1, y0 = y1;
out_board(state,i+1);
}
printf("The minimum number of steps is %ld.\n", dep);
}
long ans;
char path[100000];
bool ida(board & node, long x0, long y0, long dep, long d, long h) {
long i,j,k,x1,y1,h1;
if (memcmp(node, target, sizeof(target))==0) {
output(dep, path);
return 1;
}
if (dep==ans) return 0;
board node1;
for (i=0; i
if (((i%2)==(d%2)) && i!=d) continue;
x1 = x0 + add[i][0];
y1 = y0 + add[i][1];
if (x1
memcpy(node1, node, sizeof(node1));
node1[x1][y1] = 0;
node1[x0][y0] = node[x1][y1];
if (i==3 && y1
else if (i==1 && y1>targetplace[node[x1][y1]][1]) h1=h-1;
else if (i==0 && x1
else if (i==2 && x1>targetplace[node[x1][y1]][0]) h1=h-1;
else h1=h+1;
if (h1+dep+1>ans) continue; // 根據估價值(h1+dep)
// 和假定的解的步數(ans)來剪枝
path[dep] = i;
if (ida(node1,x1,y1,dep+1,i,h1)) return 1;
}
return 0;
}
int main() {
long i,j,k,x0,y0;
long cs;
//scanf("%ld", &cs);
cs = 1;
printf("input=\n");
while (cs--) {
for (i=0;i
scanf("%ld",&k);
start[i][j] = k;
if (k==0) { x0=i; y0=j; }
}
for (k=1,i=0; i
targetplace[target[i][j]][0] = i;
targetplace[target[i][j]][1] = j;
}
if (!can_solve()) { printf("This puzzle is not solvable.\n"); continue; }
i = -1;
j = CAL_H(start);
for (ans=j; ; ans+=1) {
if (ida(start,x0,y0,0,i,j)) {
break;
}
}
getch();
}
return 0;
}
