• <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>
            

    
            

            




            







												


        


            


            coreBugZJ
            

            此 blog 已棄。
            

            




            
	
					
	
            
		
            
			A* 算法求解八數(shù)碼問(wèn)題，POJ 1077 Eight
		
            
		
              1/*
              2
              3A* 算法求解八數(shù)碼問(wèn)題
              4
              5
              6----問(wèn)題描述：
              7
              8經(jīng)典八數(shù)碼問(wèn)題，
              9在3×3的方格棋盤(pán)上，分別擺放著1到8這八個(gè)數(shù)碼，剩余一個(gè)方格為空白。
             10
             11如下為一個(gè)狀態(tài)，
             12
             131  2  3 
             14
             15x  4  6 
             16
             177  5  8 
             18
             19其中 x 代表空白方格。
             20
             21
             22現(xiàn)給定初始狀態(tài)，要求對(duì)空白方格執(zhí)行
             23
             24左移（l，空白方格與其左邊方格互換），
             25右移（r，空白方格與其右邊方格互換），
             26上移（u，空白方格與其上邊方格互換），
             27下移（d，空白方格與其下邊方格互換），
             28
             29這四個(gè)操作使得棋盤(pán)變換為如下的
             30
             311  2  3 
             32
             334  5  6 
             34
             357  8  x 
             36
             37的目標(biāo)狀態(tài)。
             38
             39
             40----輸入：
             41
             42初始狀態(tài)。
             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如果無(wú)解，輸出字符串"unsolvable"；
             60如果有解，輸出變換過(guò)程，為包含字符 'l'，'r'，'u'，'d' 的字符串，各字符的含義見(jiàn)上文。
             61
             62
             63----樣例輸入：
             64
             652  3  4  1  5  x  7  6  8 
             66
             67
             68----樣例輸出：
             69
             70ullddrurdllurdruldr
             71
             72
             73----分析：
             74
             75本問(wèn)題實(shí)為 POJ 1077 Eight，前年寫(xiě)的代碼，今天加上注釋，作為對(duì) A* 的復(fù)習(xí)。
             76
             77這里只要求找出一個(gè)解即可，不必找出最優(yōu)解，且空間不大，僅 9！，因而 A* 具有優(yōu)勢(shì)。
             78
             79簡(jiǎn)單解釋幾個(gè)地方，具體見(jiàn)代碼注釋。
             80
             811.排列轉(zhuǎn)化為序數(shù)
             82        例，1 2 3 這三個(gè)數(shù)字的全排列，按字典序，依次為
             83
             84        123 -- 0
             85        132 -- 1
             86        213 -- 2
             87        231 -- 3
             88        312 -- 4
             89        321 -- 5
             90
             91        其中，左側(cè)為排列，右側(cè)為其序數(shù)。
             92        轉(zhuǎn)化算法此處不再贅述。
             93
             942.對(duì)形如 
             95
             96        1  2  3 
             97
             98        x  4  6 
             99
            100        7  5  8 
            101
            102        的狀態(tài)，表示為整數(shù) 123946758，其中 x 用數(shù)字 9 代替。
            103
            1043.將一個(gè)狀態(tài)視為數(shù)字 1-9 的一個(gè)排列，將此排列轉(zhuǎn)化為序數(shù)，作為此狀態(tài)的 HASH 值。
            105
            1064.使用數(shù)據(jù)結(jié)構(gòu) 堆 加速挑選最優(yōu)值。
            107
            1085.函數(shù) g 的計(jì)算，此狀態(tài)在搜索樹(shù)中的父結(jié)點(diǎn)的數(shù)量。
            109
            1106.函數(shù) h 的計(jì)算，見(jiàn)代碼 calcH 函數(shù)。
            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        // 排列轉(zhuǎn)化為序數(shù)
            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// 計(jì)算狀態(tài)的 h 函數(shù)
            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// 判斷是否無(wú)解
            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[] = { 0, 1, 0, -1 };
            233        static int DJ[] = { 1, 0, -1, 0 };
            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, 0, sizeof(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 閱讀(2685) 評(píng)論(4)  編輯 收藏 引用  所屬分類: ACM 、Algorithm 、課內(nèi)作業(yè) 、Intelligence 
		
            
	
            
	
	





            
	    
    


            

            Feedback
            
	
	
			
            
				# re: A* 算法求解八數(shù)碼問(wèn)題，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' };

              回復(fù)  更多評(píng)論
				  
				
			
            
		
			
            
				# re: A* 算法求解八數(shù)碼問(wèn)題，POJ 1077 Eight
					
						2012-10-23 20:57
					
				soulmachine
			
            
			
            
				這三個(gè)變量對(duì)應(yīng)關(guān)系是不是弄反了，不如向左移動(dòng)，應(yīng)該對(duì)應(yīng)的是 0,-1吧？  回復(fù)  更多評(píng)論
				  
				
			
            
		
			
            
				# re: A* 算法求解八數(shù)碼問(wèn)題，POJ 1077 Eight
					
						2012-10-23 20:58
					
				soulmachine
			
            
			
            
				這三個(gè)變量對(duì)應(yīng)關(guān)系是不是弄反了，比如向左移動(dòng)，應(yīng)該對(duì)應(yīng)的是 0,-1吧？
              回復(fù)  更多評(píng)論
				  
				
			
            
		
			
            
				# re: A* 算法求解八數(shù)碼問(wèn)題，POJ 1077 Eight
					
						2012-10-23 21:11
					
				soulmachine
			
            
			
            
				看明白了，input()函數(shù)本來(lái)就是反的，跟直覺(jué)相反，-_-|||  回復(fù)  更多評(píng)論
				  
				
			
            
		

            

            




            






            

				

            


    
    







            
	   
	



久久久精品波多野结衣|
久久亚洲精品国产亚洲老地址|
久久天天躁狠狠躁夜夜网站|
伊人久久大香线蕉综合影院首页|
亚洲国产精品高清久久久|
久久青青草原精品影院|
热久久国产欧美一区二区精品|
久久精品夜夜夜夜夜久久|
国产99久久久国产精品～～牛|
亚洲色欲久久久综合网东京热|
成人精品一区二区久久久|
亚洲精品乱码久久久久久中文字幕
|
久久人人爽人人爽人人av东京热|
久久精品国产第一区二区三区
|
欧美伊人久久大香线蕉综合|
精品无码久久久久久尤物|
无码8090精品久久一区|
国内精品久久久久久野外|
久久久久亚洲av成人网人人软件|
亚洲狠狠久久综合一区77777|
久久人人爽人人爽人人av东京热|
99久久精品国产一区二区蜜芽|
日本欧美久久久久免费播放网|
久久亚洲国产成人影院网站|
91精品日韩人妻无码久久不卡|
中文字幕久久波多野结衣av|
亚洲精品NV久久久久久久久久
|
久久精品国产亚洲7777|
久久最新精品国产|
久久91精品国产91久久小草|
亚洲精品乱码久久久久久中文字幕|
久久久久国产精品人妻|
国产欧美久久久精品影院|
久久久久亚洲精品日久生情|
色播久久人人爽人人爽人人片aV|
久久国产三级无码一区二区|
久久国产福利免费|
久久无码一区二区三区少妇|
亚洲а∨天堂久久精品|
色播久久人人爽人人爽人人片AV|
久久综合亚洲色一区二区三区|