青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

coreBugZJ

此 blog 已棄。

A* 算法求解八數碼問題,POJ 1077 Eight

  1/*
  2
  3A* 算法求解八數碼問題
  4
  5
  6----問題描述:
  7
  8經典八數碼問題,
  9在3×3的方格棋盤上,分別擺放著1到8這八個數碼,剩余一個方格為空白。
 10
 11如下為一個狀態,
 12
 131  2  3 
 14
 15x  4  6 
 16
 177  5  8 
 18
 19其中 x 代表空白方格。
 20
 21
 22現給定初始狀態,要求對空白方格執行
 23
 24左移(l,空白方格與其左邊方格互換),
 25右移(r,空白方格與其右邊方格互換),
 26上移(u,空白方格與其上邊方格互換),
 27下移(d,空白方格與其下邊方格互換),
 28
 29這四個操作使得棋盤變換為如下的
 30
 311  2  3 
 32
 334  5  6 
 34
 357  8  x 
 36
 37的目標狀態。
 38
 39
 40----輸入:
 41
 42初始狀態。
 43
 44形如
 45
 461 2 3 x 4 6 7 5 8 
 47
 48表示
 49
 501  2  3 
 51
 52x  4  6 
 53
 547  5  8 
 55
 56
 57----輸出:
 58
 59如果無解,輸出字符串"unsolvable";
 60如果有解,輸出變換過程,為包含字符 'l','r','u','d' 的字符串,各字符的含義見上文。
 61
 62
 63----樣例輸入:
 64
 652  3  4  1  5  x  7  6  8 
 66
 67
 68----樣例輸出:
 69
 70ullddrurdllurdruldr
 71
 72
 73----分析:
 74
 75本問題實為 POJ 1077 Eight,前年寫的代碼,今天加上注釋,作為對 A* 的復習。
 76
 77這里只要求找出一個解即可,不必找出最優解,且空間不大,僅 9!,因而 A* 具有優勢。
 78
 79簡單解釋幾個地方,具體見代碼注釋。
 80
 811.排列轉化為序數
 82        例,1 2 3 這三個數字的全排列,按字典序,依次為
 83
 84        123 -- 0
 85        132 -- 1
 86        213 -- 2
 87        231 -- 3
 88        312 -- 4
 89        321 -- 5
 90
 91        其中,左側為排列,右側為其序數。
 92        轉化算法此處不再贅述。
 93
 942.對形如 
 95
 96        1  2  3 
 97
 98        x  4  6 
 99
100        7  5  8 
101
102        的狀態,表示為整數 123946758,其中 x 用數字 9 代替。
103
1043.將一個狀態視為數字 1-9 的一個排列,將此排列轉化為序數,作為此狀態的 HASH 值。
105
1064.使用數據結構 堆 加速挑選最優值。
107
1085.函數 g 的計算,此狀態在搜索樹中的父結點的數量。
109
1106.函數 h 的計算,見代碼 calcH 函數。
111
112
113*/

114
115
116#include <stdio.h>
117#include <string.h>
118#include <stdlib.h>
119
120#define  L       362880
121#define  MAXMAX  2123456789
122
123typedef struct
124{
125        int arrange, preIndex, g, h, f, flag; // flag -1 closed, 0 no, 1 open
126        char choice;
127}
 State;
128
129State state[ L ];
130int start, goal, startIndex, goalIndex;
131
132        // 排列轉化為序數
133int arrangeToIndex( int arrange ) {
134        int i, j, k, index = 0, t = 0, d[ 10 ];
135        while ( arrange ) {
136                d[ ++t ] = arrange % 10;
137                arrange /= 10;
138        }

139        for ( i = t; i > 1--i ) {
140                k = 0;
141                for ( j = 1; j < i; ++j ) {
142                        if ( d[ i ] > d[ j ] ) ++k;
143                }

144                index = index * i + k;
145        }

146        return index;
147}

148
149// 堆
150int heap[ L + 4 ], heapIndex[ L + 4 ], heapN;
151
152void heapUp( int j ) {
153        int i = j / 2, x = heap[ j ];
154        while ( i > 0 ) {
155                if ( state[ heap[ i ] ].f <= state[ x ].f ) break;
156                heapIndex[ heap[ j ] = heap[ i ] ] = j;
157                j = i;
158                i = j / 2;
159        }

160        heapIndex[ heap[ j ] = x ] = j;
161}

162
163void heapDown( int i ) {
164        int j = i + i, x = heap[ i ];
165        while ( j <= heapN ) {
166                if ( ( j < heapN ) && ( state[ heap[ j ] ].f > state[ heap[ j + 1 ] ].f ) ) ++j;
167                if ( state[ x ].f <= state[ heap[ j ] ].f ) break;
168                heapIndex[ heap[ i ] = heap[ j ] ] = i;
169                i = j;
170                j = i + i;
171        }

172        heapIndex[ heap[ i ] = x ] = i;
173}

174
175int heapPop() {
176        int x = heap[ 1 ];
177        heapIndex[ heap[ 1 ] = heap[ heapN-- ] ] = 1;
178        if ( heapN > 1 ) {
179                heapDown( 1 );
180        }

181        return x;
182}

183
184void heapAdd( int x ) {
185        ++heapN;
186        heapIndex[ heap[ heapN ] = x ] = heapN;
187        heapUp( heapN );
188}

189
190// 計算狀態的 h 函數
191int calcH( int arrange ) {
192        int p, i, h = 0;
193        for ( i = 8; i >= 0--i ) {
194                p = arrange % 10 - 1;
195                arrange /= 10;
196                h += abs( p % 3 - i % 3 ) + abs( p / 3 - i / 3 );
197        }

198        return h;
199}

200
201int input() {
202        int ch, i;
203        start = goal = 0;
204        for ( i = 0; i < 9++i ) {
205                do {
206                        ch = getchar();
207                }
 while ( ( ch != EOF ) && ( ( ch < '1' ) || ( ch > '8' ) ) && ( ch != 'x' ) );
208                if ( ch == EOF ) return 0;
209                if ( ch == 'x' ) start = start * 10 + 9;
210                else             start = start * 10 + ch - '0';
211                goal = goal * 10 + i + 1;
212        }

213        return 1;
214}

215
216// 判斷是否無解
217int noAns() {
218        int a = start, d[ 10 ], t = 0, sum = 0, i, j;
219        while ( a ) {
220                d[ t++ ] = a % 10;
221                a /= 10;
222        }

223        for ( i = 1; i < t; ++i )
224        for ( j = 0; j < i; ++j )
225                if ( ( d[ i ] > d[ j ] ) && ( d[ i ] != 9 ) ) ++sum;
226        return sum % 2;
227}

228
229char choice[ 4 ];
230int nextIndex[ 4 ];
231void next( int arrange ) {
232        static int DI[] = 010-1 };
233        static int DJ[] = 10-10 };
234        static char DC[] = 'l''u''r''d' };
235        static int p[ 3 ][ 3 ];
236        int i, j, i0, j0, x, y, k;
237        for ( i = 0; i < 3++i )
238        for ( j = 0; j < 3++j ) {
239                p[ i ][ j ] = arrange % 10;
240                arrange /= 10;
241                if ( p[ i ][ j ] == 9 ) {
242                        i0 = i;
243                        j0 = j;
244                }

245        }

246        for ( k = 0; k < 4++k ) {
247                i = i0 + DI[ k ];
248                j = j0 + DJ[ k ];
249                if ( ( i >= 0 ) && ( i < 3 ) && ( j >= 0 ) && ( j < 3 ) ) {
250                        p[ i0 ][ j0 ] = p[ i ][ j ];
251                        p[ i ][ j ] = 9;
252                        arrange = 0;
253                        for ( x = 2; x >= 0--x )
254                        for ( y = 2; y >= 0--y )
255                                arrange = arrange * 10 + p[ x ][ y ];
256                        p[ i ][ j ] = p[ i0 ][ j0 ];
257                        x = nextIndex[ k ] = arrangeToIndex( arrange );
258                        choice[ k ] = DC[ k ];
259                        if ( state[ x ].arrange == 0 ) {
260                                state[ x ].arrange = arrange;
261                                state[ x ].h = calcH( arrange );
262                        }

263                }

264                else {
265                        nextIndex[ k ] = -1;
266                }

267        }

268}

269
270int astar() {
271        int i, j, k, ng, nf;
272        if ( noAns() ) return 0;
273        startIndex = arrangeToIndex( start );
274        goalIndex  = arrangeToIndex( goal );
275        if ( start == goal ) return 1;
276
277        memset( state, 0sizeof(state) );
278        state[ startIndex ].arrange = start;
279        state[ startIndex ].flag    = 1;
280        state[ startIndex ].g       = 0;
281        state[ startIndex ].h       = state[ startIndex ].f = calcH( start );
282        heapN = 0;
283        heapAdd( startIndex );
284        while ( heapN > 0 ) {
285                i = heapPop();
286                if ( i == goalIndex ) return 1;
287                state[ i ].flag = -1;
288                ng = state[ i ].g + 1;
289                next( state[ i ].arrange );
290                for ( k = 0; k < 4++k ) {
291                        j = nextIndex[ k ];
292                        if ( j < 0 ) continue;
293                        nf = ng + state[ j ].h;
294                        if ( ( state[ j ].flag == 0 ) || ( ( state[ j ].flag == 1 ) && ( nf < state[ j ].f ) ) ) {
295                                state[ j ].preIndex = i;
296                                state[ j ].choice = choice[ k ];
297                                state[ j ].g    = ng;
298                                state[ j ].f    = nf;
299                                if ( state[ j ].flag > 0 ) {
300                                        heapUp( heapIndex[ j ] );
301                                        heapDown( heapIndex[ j ] );
302                                }

303                                else {
304                                        heapAdd( j );
305                                        state[ j ].flag = 1;
306                                }

307                        }

308                }

309        }

310        return 0;
311}

312
313void output() {
314        int i, top = -1;
315        char stack[ 1000 ];
316        for ( i = goalIndex; i != startIndex; i = state[ i ].preIndex ) {
317                stack[ ++top ] = state[ i ].choice;
318        }

319        for ( i = top; i >= 0--i ) {
320                printf( "%c", stack[ i ] );
321        }

322        printf( "\n" );
323}

324
325int main() {
326        while ( input() ) {
327                if ( astar() ) output();
328                else printf( "unsolvable\n" );
329        }

330        return 0;
331}

332

posted on 2012-06-05 15:06 coreBugZJ 閱讀(2688) 評論(4)  編輯 收藏 引用 所屬分類: ACM 、Algorithm課內作業 、Intelligence

Feedback

# re: A* 算法求解八數碼問題,POJ 1077 Eight 2012-10-23 20:56 soulmachine

static int DI[] = { 0, 1, 0, -1 };
static int DJ[] = { 1, 0, -1, 0 };
static char DC[] = { 'l', 'u', 'r', 'd' };

  回復  更多評論   

# re: A* 算法求解八數碼問題,POJ 1077 Eight 2012-10-23 20:57 soulmachine

這三個變量對應關系是不是弄反了,不如向左移動,應該對應的是 0,-1吧?  回復  更多評論   

# re: A* 算法求解八數碼問題,POJ 1077 Eight 2012-10-23 20:58 soulmachine

這三個變量對應關系是不是弄反了,比如向左移動,應該對應的是 0,-1吧?
  回復  更多評論   

# re: A* 算法求解八數碼問題,POJ 1077 Eight 2012-10-23 21:11 soulmachine

看明白了,input()函數本來就是反的,跟直覺相反,-_-|||  回復  更多評論   


青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲经典一区| 亚洲一区二区三区四区中文| 久久久91精品国产| 亚洲欧美日韩另类精品一区二区三区 | 亚洲欧美国产精品桃花| 正在播放欧美视频| 亚洲欧美99| 久久久福利视频| 欧美福利一区| 国产精品日韩高清| 永久免费视频成人| 一本色道久久综合一区| 午夜精品久久久久久久久久久| 欧美在线影院在线视频| 免费在线日韩av| 亚洲国产成人av| 亚洲视频网在线直播| 欧美一级片久久久久久久| 美脚丝袜一区二区三区在线观看| 欧美日韩成人精品| 国产又爽又黄的激情精品视频| 亚洲国产日日夜夜| 亚洲欧美综合| 亚洲国产精品va在线观看黑人| 一本色道久久综合亚洲91| 欧美一级一区| 老司机午夜精品视频| 亚洲日韩第九十九页| 亚洲欧美999| 欧美精品一区二区精品网 | 欧美电影免费观看大全| 亚洲精品网址在线观看| 欧美一区二区三区喷汁尤物| 欧美护士18xxxxhd| 国内精品久久久久久久97牛牛| 夜夜精品视频| 欧美大片一区二区| 亚洲欧美综合精品久久成人 | 日韩视频在线一区二区| 久久精品亚洲精品国产欧美kt∨| 欧美日韩国产限制| 亚洲国产经典视频| 久久久久九九九| 亚洲天堂av高清| 欧美日本国产| 最近看过的日韩成人| 久久男女视频| 亚洲欧美国内爽妇网| 欧美日韩精品欧美日韩精品一| 亚洲电影免费在线| 久久尤物电影视频在线观看| 亚洲欧美日本国产专区一区| 欧美韩日亚洲| 亚洲精品日韩在线| 女主播福利一区| 久久久女女女女999久久| 国产片一区二区| 欧美在线观看视频| 亚洲一区二区三区四区中文| 欧美日产在线观看| 亚洲欧洲一区二区在线观看| 欧美国产精品一区| 免费观看不卡av| 亚洲国产精品123| 欧美成人精品1314www| 久久精品五月婷婷| 激情久久影院| 欧美大片在线观看一区二区| 久久国产精品亚洲va麻豆| 国产午夜精品久久| 久久久久国产一区二区| 久久精品一区二区| 亚洲国产一区二区三区青草影视 | 亚洲一区二区三区色| 国产精品久久久久久久一区探花 | 模特精品在线| 亚洲人久久久| av成人免费| 国产精品美女www爽爽爽| 午夜精品福利视频| 久久国产精品99久久久久久老狼| 在线看不卡av| 亚洲欧洲美洲综合色网| 欧美人与性禽动交情品| 亚洲欧美中文另类| 久久久99久久精品女同性| 亚洲国语精品自产拍在线观看| 亚洲福利视频网| 国产精品乱码| 欧美成人免费大片| 国产精品www994| 久久最新视频| 欧美日韩国产大片| 久久久久国产精品午夜一区| 女人香蕉久久**毛片精品| 亚洲一区二区在线| 久久黄金**| 亚洲一区二区三区精品视频| 欧美一区二区三区四区在线观看地址 | 亚洲欧美区自拍先锋| 欧美在线一二三四区| 99精品黄色片免费大全| 亚洲综合日韩| 亚洲第一毛片| 亚洲欧美日韩精品久久久久| 在线精品在线| 欧美一级专区免费大片| 夜夜嗨av一区二区三区网页| 午夜精品国产| 一区二区三区视频在线观看| 久久精品72免费观看| 亚洲视频一二区| 噜噜噜91成人网| 久久精品人人| 国产精品久久久久久久久久免费| 欧美福利一区二区三区| 国产视频欧美视频| 在线视频欧美一区| aa国产精品| 免费毛片一区二区三区久久久| 欧美在线地址| 国产精品捆绑调教| 妖精成人www高清在线观看| 在线日韩电影| 久久久久久久久久看片| 久久精品中文| 国产一区导航| 欧美影院精品一区| 久久精品国产免费观看| 国产精品中文字幕欧美| 亚洲尤物视频网| 亚洲欧美国产制服动漫| 欧美午夜不卡影院在线观看完整版免费 | 欧美亚洲在线观看| 亚洲欧美日韩直播| 欧美特黄a级高清免费大片a级| 亚洲高清不卡在线观看| 伊人久久大香线蕉av超碰演员| 亚洲午夜未删减在线观看| 亚洲一区二区三区四区在线观看| 欧美噜噜久久久xxx| 最新国产成人在线观看| 亚洲韩国精品一区| 免费视频一区| 亚洲人成啪啪网站| 这里只有精品在线播放| 欧美日韩亚洲高清一区二区| 日韩一区二区精品| 亚洲一本大道在线| 国产精品久久久免费| 亚洲主播在线观看| 久久精品国产v日韩v亚洲| 韩国在线视频一区| 久久综合999| 亚洲黄色成人| 亚洲午夜在线视频| 国产精品自拍网站| 久久精品视频网| 亚洲国产精品悠悠久久琪琪| 一区二区国产日产| 国产欧美精品日韩| 久久久欧美一区二区| 亚洲人成在线播放网站岛国| 亚洲一区二区三区精品视频| 国产人妖伪娘一区91| 久热精品在线| 亚洲午夜小视频| 免费av成人在线| 在线一区视频| 国产亚洲成精品久久| 久久亚洲国产精品一区二区| 亚洲国内欧美| 欧美一区二区精品在线| 精品999在线播放| 欧美不卡一区| 亚洲欧美视频在线| 欧美激情片在线观看| 中文在线不卡视频| 激情视频亚洲| 欧美午夜一区二区福利视频| 欧美在线播放一区| 亚洲免费高清| 欧美成年人网| 久久激情视频久久| 亚洲线精品一区二区三区八戒| 国内成人精品视频| 欧美精品久久久久久久| 亚洲在线1234| 亚洲国产精品成人综合色在线婷婷| 午夜宅男欧美| aa级大片欧美三级| 亚洲高清影视| 国产真实乱偷精品视频免| 欧美日韩国产综合网| 久久久亚洲成人| 欧美一区二区三区视频在线观看| 日韩午夜免费视频| 亚洲黄色在线看| 久久亚洲精品中文字幕冲田杏梨| 亚洲性图久久|