广搜——最优方案-白红宇

广搜——最优方案

阅读量：5232 次

发布时间：2019-06-14

本文共 10534 字，大约阅读时间需要 35 分钟。

Wikioi 1225 八数码难题

题目描述

Description

Yours和zero在研究A*启发式算法.拿到一道经典的A*问题,但是他们不会做,请你帮他们.

问题描述

在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入描述

Input Description

输入初试状态，一行九个数字，空格用0表示

输出描述

Output Description

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)

样例输入

Sample Input

283104765

样例输出

Sample Output

数据范围及提示

Data Size & Hint

详见试题

思路：

（康托展开+双向广搜） or ida*

代码：

①双向广搜：

1 #include
        
           2 #include
         
            3 #include
          
             4 #include
           
              5 #include
            
               6 #include
             
               7 #include
               8 #include
               
                 9 #define mx 4000000 10 using namespace std; 11 12 struct chess{ 13 int node[9]; 14 int step; 15 int pos; 16 bool cla; 17 }; 18 int chart = 0,step[2][10000]; 19 map
                
                  trans[2]; 20 chess start,end; 21 bool jud[2][mx]; 22 int m_jud[9][4] = { 1,3,-1,-1, 23 0,4,2,-1, 24 1,5,-1,-1, 25 0,4,6,-1, 26 1,3,5,7, 27 2,4,8,-1, 28 3,7,-1,-1, 29 4,6,8,-1, 30 5,7,-1,-1}; 31 32 int getval(chess x){ 33 int res = 1,val = 0; 34 for(int i = 1;i <= 9;i++){ 35 val += res * x.node[i-1]; 36 res *= (i+1); 37 } 38 return val; 39 } 40 void putout(chess pt){ 41 cout<<"the class:"<
                 
                  <
                  
                   <= 3;i++){ 43 for(int j = 1;j <= 3;j++){ 44 cout<
                   
                    >co; 53 for(int i = 8;i >= 0;i--){ 54 start.node[i] = (co / md)% 10; 55 md *= 10; 56 if(start.node[i] == 0) start.pos = i; 57 58 } 59 start.cla = 0; 60 end.node[0] = 1; 61 end.node[1] = 2; 62 end.node[2] = 3; 63 end.node[3] = 8; 64 end.node[4] = 0; 65 end.node[5] = 4; 66 end.node[6] = 7; 67 end.node[7] = 6; 68 end.node[8] = 5; 69 end.step = start.step = 0; 70 end.pos = 4; 71 end.cla = 1; 72 } 73 void bfs(){ 74 queue
                    
                      now,then; 75 now.push(start); 76 now.push(end); 77 chess test,h; 78 int p,code; 79 while(!now.empty()){ 80 h = now.front(); 81 p = h.pos; 82 code = getval(h); 83 trans[h.cla][code] = chart; 84 step[h.cla][chart] = h.step; 85 chart++; 86 jud[h.cla][code] = 1; 87 for(int i = 0,j = m_jud[p][i];j != -1 && i <= 3;i++,j = m_jud[p][i]){ 88 test = h; 89 test.step++; 90 swap(test.node[p],test.node[j]); 91 code = getval(test); 92 //if(jud[test.cla][code]) continue; 93 test.pos = j; 94 trans[test.cla][code] = chart; 95 step[test.cla][chart] = test.step; 96 chart++; 97 if(jud[!test.cla][code]){ 98 cout<

View Code

②IDA*：

1 #include 
        
           2 #include 
         
            3 #include 
          
             4 #include 
           
              5 #include 
            
               6 using namespace std;  7 const unsigned int M = 1001;  8 int dir[4][2] = {  9     1, 0, // Down 10     -1, 0, // Up 11     0,-1, // Left 12     0, 1 // Right 13 }; 14 typedef struct STATUS{ 15     int arr[3][3]; 16     int r,c; 17 }STATUS; 18 char dirCode[] = {
      "dulr"}; 19 char rDirCode[] = {
      "udrl"}; 20 char path[M]; // 最优解 21 STATUS begin, end = { 1,2,3,4,5,6,7,8,0,2,2 }; // 起始和终止状态 22 int maxDepth = 0; // 深度边界 23 int diff(const STATUS &cur) // 启发函数 24 { 25     int i,j,k,m,ans=0; 26     for(i=0;i<=2;i++) 27         for(j=0;j<=2;j++) 28         { 29             if(cur.arr[i][j] != 0) 30             { 31                 for(k=0;k<=2;k++) 32                     for(m=0;m<=2;m++) 33                     { 34                         if(cur.arr[i][j] == end.arr[k][m]) 35                         { 36                             ans+=abs(i-k)+abs(j-m); 37                             break; 38                         } 39                     } 40             } 41         } 42     return ans; 43 } 44 bool dfs(STATUS &cur, int depth, int h, char preDir) 45 { 46     if(memcmp(&cur, &end, sizeof(STATUS)) == 0 ) 47     { // OK找到解了:) 48         path[depth] = '/0'; 49         return true; 50     } 51     if( depth + h > maxDepth ) return false; // 剪枝 52     STATUS nxt; // 下一状态 53     for(int i=0; i<4; i++) 54     { 55         if(dirCode[i]==preDir) continue; // 回到上次状态,剪枝 56         nxt = cur; 57         nxt.r = cur.r + dir[i][0]; 58         nxt.c = cur.c + dir[i][1]; 59         if( !( nxt.r >= 0 && nxt.r < 3 && nxt.c >= 0 && nxt.c < 3 ) ) 60             continue; 61         int nxth = h; 62         int preLen,Len,desNum=cur.arr[nxt.r][nxt.c],desR=(desNum-1)/3,desC=(desNum-1)%3; 63         preLen=abs(nxt.r-desR)+abs(nxt.c-desC); 64         Len=abs(cur.r-desR)+abs(cur.c-desC); 65         nxth = h - preLen + Len; 66         swap(nxt.arr[cur.r][cur.c], nxt.arr[nxt.r][nxt.c]); 67         path[depth] = dirCode[i]; 68         if(dfs(nxt, depth + 1, nxth, rDirCode[i])) 69             return true; 70     } 71     return false; 72 } 73 int IDAstar() 74 { 75     int nh = diff(begin); 76     maxDepth = nh; 77     while (!dfs(begin, 0, nh, '/0')) 78         maxDepth++; 79     return maxDepth; 80 } 81 void Input() 82 { 83     char ch; 84     int i, j; 85     for(i=0; i < 3; i++){ 86         for(j=0; j < 3; j++){ 87             do{ 88                 scanf("%c", &ch); 89             } 90             while( !( ( ch >= '1' && ch <= '8' ) || ( ch == 'x' ) ) )  91                 ; 92             if( ch == 'x' ) { 93                 begin.arr[i][j] = 0; 94                 begin.r = i; 95                 begin.c = j; 96             } 97             else 98                 begin.arr[i][j] = ch - '0'; 99         }100     }101 }102 bool IsSolvable(const STATUS &cur)103 {104     int i, j, k=0, s = 0;105     int a[8];106     for(i=0; i < 3; i++){107         for(j=0; j < 3; j++){108             if(cur.arr[i][j]==0) continue;109             a[k++] = cur.arr[i][j];110         }111     }112     for(i=0; i < 8; i++){113         for(j=i+1; j < 8; j++){114             if(a[j] < a[i])115                 s++;116         }117     }118     return (s%2 == 0);119 }120 int main()121 {122     Input();123     if(IsSolvable(begin)){124         IDAstar();125         printf("%s/n", path);126     }127     else128         printf("unsolvable/n");129     return 0;130 }

View Code

Wikioi 2449 骑士精神

题目描述

Description

在一个5×5的棋盘上有12个白色的骑士和12个黑色的骑士，且有一个空位。在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐标相差为1，纵坐标相差为2或者横坐标相差为2，纵坐标相差为1的格子）移动到空位上。

给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘：

为了体现出骑士精神，他们必须以最少的步数完成任务。

输入描述

Input Description

第一行有一个正整数T(T<=10)，表示一共有N组数据。接下来有T个5×5的矩阵，0表示白色骑士，1表示黑色骑士，*表示空位。两组数据之间没有空行。

输出描述

Output Description

对于每组数据都输出一行。如果能在15步以内（包括15步）到达目标状态，则输出步数，否则输出－1。

样例输入

Sample Input

01*11

110*1

样例输出

Sample Output

-1

数据范围及提示

Data Size & Hint

见题面

思路：

IDA*

代码：

1 #include
        
          2 #include
         
           3 #include
          
            4 #include
           
             5 #include
            
              6 #include
             
               7 #define mx 5 8 using namespace std; 9 struct Board{10 int board[mx][mx];11 int bx,by;12 13 };14 int ans[mx][mx] = { { 1,1,1,1,1},15 { 2,1,1,1,1},16 { 2,2,0,1,1},17 { 2,2,2,2,1},18 { 2,2,2,2,2}};19 int dx[8] = { 1,2,2,1,-1,-2,-2,-1};20 int dy[8] = { 2,1,-1,-2,-2,-1,1,2};21 int d,id,bx,by;22 Board start;23 void input(){24 char tmp;25 for(int i = 0;i < 5;i++){26 for(int j = 0;j < 5;j++){27 cin>>tmp;28 if(tmp == '*'){29 start.board[i][j] = 0;30 by = i;31 bx = j;32 }33 if(tmp == '1') start.board[i][j] = 1;34 if(tmp == '0') start.board[i][j] = 2;35 }36 }37 }38 int h(Board a){39 int ret = 0;40 for(int i = 0;i < 5;i++){41 for(int j = 0;j < 5;j++){42 ret += (ans[i][j] != a.board[i][j]);43 }44 }45 return ret;46 }47 bool idastar(int step,int maxdeep){48 if(step > maxdeep) return false;49 int g = h(start),bx,by;50 if(!g) return true;51 if(g + step - 1> maxdeep) return false;52 for(int i = 0;i < 5;i++){53 for(int j = 0;j < 5;j++){54 if(start.board[i][j] == 0){55 bx = j;56 by = i;57 }58 }59 }60 for(int i = 0;i < 8;i++){61 if(bx + dx[i] < 0 || bx + dx[i] >= mx || by + dy[i] < 0 || by + dy[i] >= mx) continue;62 swap(start.board[by + dy[i]][bx + dx[i]],start.board[by][bx]);63 if(idastar(step+1,maxdeep))return true;64 swap(start.board[by + dy[i]][bx + dx[i]],start.board[by][bx]);65 }66 return false;67 }68 int main(){69 int T;70 cin>>T;71 while(T--){72 input();73 for(id = 0;id <= 15;id++){74 if(idastar(0,id)){75 cout<
              
               <
               
                 15) cout<<-1<

View Code

Wikioi 1226 倒水问题

题目描述

Description

有两个无刻度标志的水壶，分别可装 x 升和 y 升（ x,y 为整数且均不大于 100 ）的水。设另有一水缸，可用来向水壶灌水或接从水壶中倒出的水，两水壶间，水也可以相互倾倒。已知 x 升壶为空壶， y 升壶为空壶。问如何通过倒水或灌水操作，用最少步数能在x或y升的壶中量出 z （ z ≤ 100 ）升的水来。

输入描述

Input Description

一行，三个数据，分别表示 x,y 和 z;

输出描述

Output Description

一行，输出最小步数 ,如果无法达到目标，则输出"impossible"

样例输入

Sample Input

3 22 1

样例输出

Sample Output

思路：

普通广搜

代码：

1 #include
        
          2 #include
         
           3 #include
          
            4 #include
           
             5 #include
            
              6 #define maxn 100000 7 using namespace std; 8 struct sta{ 9     int x;10     int y; 11     int step;12     int frm;13 };14 int mx,my,z,j[101][101],solved = 0;15 sta temp;16 void input(){17     cin>>mx>>my>>z;18     temp.x = temp.y = temp.step = 0;19     temp.frm = -1;20 }21 sta expand(sta a,int sign){22     if(sign == 0) a.x = 0;23     if(sign == 1) a.y = 0;24     if(sign == 2) a.x = mx;25     if(sign == 3) a.y = my;26     if(sign == 4){27         int d;28         if(mx - a.x < a.y) d = mx - a.x;29         else d = a.y;30         a.y -= d;31         a.x += d;32     }33     if(sign == 5){34         int d;35         if(my - a.y < a.x) d = my - a.y;36         else d = a.x;37         a.y += d;38         a.x -= d;39     }40     a.frm = sign;41     a.step++;42     if(j[a.x][a.y]) a.step = -1;43     j[a.x][a.y] = 1;44     return a;45 }46 void bfs(){47     sta q[maxn];48     int h = 0,t = 1;49     q[h] = temp;50     while(h != t){51         if(q[h%maxn].x == z || q[h%maxn].y == z) {52             cout<
             
              <
              
               <= 5;i++){57 if(i == 0 && (q[h%maxn].x == 0 ||q[h%maxn].frm == 2)) continue;58 if(i == 1 && (q[h%maxn].y == 0 ||q[h%maxn].frm == 3)) continue;59 if(i == 2 && (q[h%maxn].x == mx ||q[h%maxn].frm == 0)) continue;60 if(i == 3 && (q[h%maxn].y == my ||q[h%maxn].frm == 1)) continue;61 if(i == 4 && (q[h%maxn].y <= 0 || q[h%maxn].x >= mx || q[h%maxn].frm == 5)) continue;62 if(i == 5 && (q[h%maxn].x <= 0 || q[h%maxn].y >= my || q[h%maxn].frm == 4)) continue;63 temp = expand(q[h%maxn],i);64 65 if(temp.step != -1) {66 t++;67 q[t%maxn] = temp;68 69 }70 }71 h++;72 }73 }74 int main(){75 input();76 if(z > mx || z > my || !mx || !my || (mx == my && mx != z)){77 cout<<"impossible"<