• <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* 算法求解八數碼問題，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[] = { 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 閱讀(2666) 評論(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()函數本來就是反的，跟直覺相反，-_-|||  回復  更多評論
				  
				
			
            
		

            

            




            






            

				

            


    
    







            
	   
	



国内精品久久国产大陆|
精品人妻久久久久久888|
久久久久亚洲精品中文字幕|
精品久久久久久久久久久久久久久
|
久久亚洲精品成人av无码网站|
人妻精品久久无码区|
久久99精品久久久久婷婷|
夜夜亚洲天天久久|
久久影院亚洲一区|
久久亚洲精品成人AV|
久久精品中文字幕久久|
久久人人爽人人澡人人高潮AV|
亚洲AV无码成人网站久久精品大|
国内精品伊人久久久久AV影院|
国产呻吟久久久久久久92|
久久国产精品免费一区|
久久香综合精品久久伊人|
久久精品蜜芽亚洲国产AV|
久久无码国产|
国内精品久久久久久99蜜桃|
一级女性全黄久久生活片免费
|
欧美色综合久久久久久|
97超级碰碰碰久久久久|
国产精品乱码久久久久久软件|
久久久久久毛片免费播放|
亚州日韩精品专区久久久|
91精品国产高清久久久久久国产嫩草
|
久久婷婷五月综合色奶水99啪|
欧美久久亚洲精品|
成人精品一区二区久久|
久久精品国产亚洲AV高清热|
欧美成人免费观看久久|
久久久久国色AV免费观看|
91久久精品国产成人久久|
无码人妻少妇久久中文字幕蜜桃|
久久无码一区二区三区少妇|
国产精品va久久久久久久|
国产L精品国产亚洲区久久|
久久久久中文字幕|
日本精品久久久中文字幕|
久久国产精品久久国产精品|