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

            技術,瞎侃,健康,休閑……

            mahu@cppblog 人類的全部才能無非是時間和耐心的混合物
            posts - 11, comments - 13, trackbacks - 0, articles - 12
              C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

            八數(shù)碼問題——A*搜索

            Posted on 2006-06-26 22:44 mahudu@cppblog 閱讀(515) 評論(0)  編輯 收藏 引用 所屬分類: Programming

            zz from http://blog.csdn.net/tiandejian/archive/2006/06/26/837659.aspx

            先把問題簡化一下吧:

            在控制臺顯示這樣一個矩陣

            [1][2][3]
            [8]?? [4]
            [7][6][5]

            手動把它打亂,然后讓程序?qū)⑵鋸驮?/p>

            和野人傳教士問題類似,這也是一個對解空間進行搜索的問題,而且更為簡單,這次采用可以縮減擴展節(jié)點的規(guī)模的A*啟發(fā)式搜索算法。取節(jié)點深度為g(x),錯位的數(shù)字數(shù)為h(x),由于問題很簡單,所以與有序搜索算法類似,算法框圖:

            ?評價函數(shù)封裝在類里,所以沒顯示在框圖中。

            顯然的,用一個一維數(shù)組保存這九個位置的數(shù),evaluate()函數(shù)返回當前狀態(tài)的評價值。

            #include <iostream>

            #include <conio.h>

            #include <windows.h>???? // 顯示矩陣時需要延時,這里有 Sleep() 函數(shù)。

            using namespace std;

            ?

            // 接收鍵盤時使用

            const enum Input { UP = 0x048, DOWN = 0x050, LEFT = 0x04b, RIGHT = 0x04d, ENTER = 0xd };

            // 擴展時判斷方向使用

            const int U = 0;

            const int D = 1;

            const int L = 2;

            const int R = 3;

            class ElemType {

            private :

            ??? int depth;??????? // 當前節(jié)點的深度(就是距離初始節(jié)點有多遠)

            ??? int numWrong() {? // 有多少錯位的數(shù)字

            ?????? int i, value = 0;

            ?????? if (maze[0]!=1) value++;

            ?????? if (maze[1]!=2) value++;

            ?????? if (maze[2]!=3) value++;

            ?????? if (maze[3]!=8) value++;

            ?????? if (maze[5]!=4) value++;

            ?????? if (maze[6]!=7) value++;

            ??????? if (maze[7]!=6) value++;

            ?????? if (maze[8]!=5) value++;

            ?????? return value;

            ??? }

            public :

            ??? int maze[9];????? // 保存矩陣用

            ??? ElemType* flag;?? // 指向根節(jié)點

            ??? ElemType() {????? // 創(chuàng)建初始節(jié)點

            ?????? maze[0]=1; maze[1]=2; maze[2]=3;

            ?????? maze[3]=8; maze[4]=0; maze[5]=4;

            ?????? maze[6]=7; maze[7]=6; maze[8]=5;

            ?????? depth = 0;

            ?????? flag = NULL;

            ??? }

            ??? ElemType( int i0, int i1, int i2, int i3, int i4, int i5, int i6, int i7, int i8) {

            ?????? maze[0]=i0; maze[1]=i1; maze[2]=i2;

            ?????? maze[3]=i3; maze[4]=i4; maze[5]=i5;

            ?????? maze[6]=i6; maze[7]=i7; maze[8]=i8;

            ?????? depth = 0;

            ?????? flag = NULL;

            ??? }

            ??? bool operator ==(ElemType e) {

            ?????? for ( int i = 0; i < 9; i++)

            ?????????? if ( this ->maze[i]!=e.maze[i])

            ????????????? return false ;

            ?????? return true ;

            ??? }

            ??? void operator =(ElemType e) {

            ?????? for ( int i = 0; i < 9; i++)

            ?????????? this ->maze[i] = e.maze[i];

            ?????? this ->depth = e.depth;

            ?????? this ->flag = e.flag;

            ?????? this ->numWrong();

            ??? }

            ??? ElemType friendoperator >>(ElemType source, int direct) {

            // 對于 L R U D 四個方向作出的移動

            ?????? ElemType result = source;

            ?????? int i = result.locate0();

            ?????? switch (direct) {

            ?????????? case U: if(i < 6){

            result.maze[i] = result.maze[i+3];

            result.maze[i+3] = 0;

            } break;

            ?????????? case D: if(i > 2){

            result.maze[i] = result.maze[i-3];

            result.maze[i-3] = 0;

            } break;

            ?????????? case L: if(i%3 != 2) {

            result.maze[i] = result.maze[i+1];

            result.maze[i+1] = 0;

            } break;

            ?????????? case R: if(i%3 != 0) {

            result.maze[i] = result.maze[i-1];

            result.maze[i-1] = 0;

            }

            ?????? }

            ?????? result.depth++;

            ?????? return result;

            ??? }

            ?

            ?????? for ( int i = 0; i < 9; i++)

            ?????????? if (maze[i] == 0)

            ????????????? return i;

            ?????? return -1;

            ??? }

            ??? bool isSuccess() {

            ?????? return maze[0]==1 && maze[1]==2 && maze[2]==3 &&

            ?????????????? maze[3]==8 && maze[4]==0 && maze[5]==4 &&

            ?????????? ?? maze[6]==7 && maze[7]==6 && maze[8]==5;

            ??? }

            ??? // 下面是評價函數(shù)

            ??? int evaluate() { return depth + numWrong(); }

            ??? void disrupt() {????? // 打亂初始矩陣

            ??????? clrscr();

            ??????? gotoxy(7,3);

            ?? ?????cout << "Disrypt the maze as you wish, press enter to see the AMAZING thing!" ;

            ??????? this ->print();

            ??????? int input;

            ??????? while ((input=_getch()) != ENTER) {

            ??????????? switch (input) {

            ??????????????? case UP:??? * this = * this >> U; this ->print(); break ;

            ??????????????? case DOWN:? * this = * this >> D; this ->print(); break ;

            ??????????????? case LEFT:? * this = * this >> L; this ->print(); break ;

            ??????????????? case RIGHT: * this = * this >> R; this ->print();

            ??????????? }

            ??????? }

            ??? }

            ??? void print() {

            ??????? for ( int i = 0; i < 3; i++) {

            ??????????? for ( int j = 0; j < 3; j++) {

            ??????????????? gotoxy(36+j*3, 8+i);

            ??????????????? if (maze[i*3+j]!=0) cout << '[' << maze[i*3+j] << ']' ;

            ??????????????? else cout << "?? " ;

            ??????????? } cout << endl;

            ?????? }

            ??????? Sleep(200);

            ??? }

            };

            ?

            void print(ElemType &e) { e.print(); }

            ?

            ElemType null(0,0,0,0,0,0,0,0,0); // 每個位置都是 0 ,這是不存在的

            ?

            #include "dso.h" ?

            typedef ElemType Status;

            ?

            ??? int locate0() {????? // 確定 0 所在的位置,其余方法要調(diào)用


            Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=837659

            久久精品国产精品亚洲艾草网美妙| 婷婷久久久亚洲欧洲日产国码AV | 久久久久久国产精品无码超碰| 久久无码专区国产精品发布 | 国产69精品久久久久99| 国产午夜电影久久| 情人伊人久久综合亚洲| 国内精品久久久久国产盗摄| 久久露脸国产精品| 久久精品国产亚洲AV香蕉| 国产91久久精品一区二区| 思思久久99热免费精品6| 91性高湖久久久久| 国产成年无码久久久久毛片| 欧美伊人久久大香线蕉综合| 久久精品国产亚洲av麻豆小说| 国产成人无码精品久久久免费 | 97久久超碰成人精品网站| 久久93精品国产91久久综合 | 国产精品成人久久久久三级午夜电影| 久久亚洲中文字幕精品一区四 | 深夜久久AAAAA级毛片免费看| 99久久精品毛片免费播放| 囯产极品美女高潮无套久久久| 久久久久婷婷| 久久精品国产一区| 久久精品国产男包| 性做久久久久久久久| 青青草国产成人久久91网| 久久久久人妻一区二区三区| 久久99精品国产99久久6男男| 久久久久青草线蕉综合超碰 | 国产精品女同久久久久电影院| 色婷婷狠狠久久综合五月| 精品国产青草久久久久福利| 亚洲国产精品热久久| 狠狠色丁香久久综合婷婷| 国产精品久久久久久福利漫画| 狠狠人妻久久久久久综合| 国产激情久久久久影院老熟女免费| 91精品国产乱码久久久久久|