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

            技術(shù),瞎侃,健康,休閑……

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

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

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

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

            先把問題簡化一下吧:

            在控制臺(tái)顯示這樣一個(gè)矩陣

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

            手動(dòng)把它打亂,然后讓程序?qū)⑵鋸?fù)原。

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

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

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

            #include <iostream>

            #include <conio.h>

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

            using namespace std;

            ?

            // 接收鍵盤時(shí)使用

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

            // 擴(kuò)展時(shí)判斷方向使用

            const int U = 0;

            const int D = 1;

            const int L = 2;

            const int R = 3;

            class ElemType {

            private :

            ??? int depth;??????? // 當(dāng)前節(jié)點(diǎn)的深度(就是距離初始節(jié)點(diǎn)有多遠(yuǎn))

            ??? int numWrong() {? // 有多少錯(cuò)位的數(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é)點(diǎn)

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

            ?????? 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 四個(gè)方向作出的移動(dòng)

            ?????? 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;

            ??? }

            ??? // 下面是評價(jià)函數(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); // 每個(gè)位置都是 0 ,這是不存在的

            ?

            #include "dso.h" ?

            typedef ElemType Status;

            ?

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


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

            激情综合色综合久久综合| 日本久久中文字幕| 精品久久无码中文字幕| 精品久久久久久久久久久久久久久 | 午夜精品久久影院蜜桃| 国内精品伊人久久久久妇| 久久精品www人人爽人人| 色悠久久久久久久综合网| 精产国品久久一二三产区区别| 亚洲国产精品无码久久青草 | 久久久久亚洲av成人无码电影| 久久久久亚洲AV无码麻豆| 久久精品国产精品亚洲精品| 久久影院综合精品| 久久亚洲私人国产精品| 久久婷婷五月综合色99啪ak| 久久人人爽人人爽人人片av高请| 国产精品欧美久久久久无广告 | 热99RE久久精品这里都是精品免费 | 狠狠综合久久AV一区二区三区| 国产精品久久久久久吹潮| 亚洲国产精品嫩草影院久久| 久久国产精品久久| 天天爽天天狠久久久综合麻豆| 国产亚洲美女精品久久久2020| 成人国内精品久久久久影院VR | 久久性生大片免费观看性| 精品久久久久久久久中文字幕| 中文字幕日本人妻久久久免费 | 国产精品99久久久久久猫咪| 久久久久亚洲AV无码专区体验| 亚洲精品国产第一综合99久久| 亚洲伊人久久综合中文成人网| 99久久精品毛片免费播放| 精品久久人人妻人人做精品| 久久夜色精品国产网站| 久久精品午夜一区二区福利| 久久精品国产亚洲AV香蕉| 久久亚洲精品成人无码网站| yy6080久久| 亚洲国产精品无码久久久秋霞2|