• <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++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理

            八數碼問題——A*搜索

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

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

            先把問題簡化一下吧:

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

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

            手動把它打亂,然后讓程序將其復原。

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

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

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

            #include <iostream>

            #include <conio.h>

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

            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;??????? // 當前節點的深度(就是距離初始節點有多遠)

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

            ?????? 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;?? // 指向根節點

            ??? ElemType() {????? // 創建初始節點

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

            ??? }

            ??? // 下面是評價函數

            ??? 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 所在的位置,其余方法要調用


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

            欧美亚洲国产精品久久蜜芽| 日韩av无码久久精品免费| 久久夜色精品国产噜噜亚洲a| 777久久精品一区二区三区无码| 浪潮AV色综合久久天堂| 伊人久久无码中文字幕| 久久亚洲日韩看片无码| 7777久久久国产精品消防器材| 久久九九久精品国产| 色综合久久久久综合99| 久久这里的只有是精品23| 亚洲国产精品无码久久| 久久无码人妻一区二区三区| 久久99精品久久只有精品| 国内精品久久久久久野外| 91久久精品国产成人久久| 久久久久无码中| 99久久精品国产一区二区| 99久久er这里只有精品18| 一本大道加勒比久久综合| 老司机午夜网站国内精品久久久久久久久| 国产视频久久| 久久笫一福利免费导航| 久久精品国产清高在天天线| 99久久国产亚洲高清观看2024| 久久综合色之久久综合| 婷婷久久香蕉五月综合加勒比| 精品久久久久久久久中文字幕| 久久97久久97精品免视看| 亚洲精品白浆高清久久久久久| 久久久久久久综合日本亚洲| 久久久久久久久久免免费精品| 久久久精品国产免大香伊| 青青青国产成人久久111网站| 亚洲国产成人久久一区久久| 精品国产91久久久久久久| 99精品国产免费久久久久久下载 | 久久久久久a亚洲欧洲aⅴ| 国产精品美女久久福利网站| 久久国产精品-国产精品| 久久久国产打桩机|