A*アルゴリズム(八数コード問題)

14345 ワード

#include <iostream>

#include <cstring>

#include <vector>

#include <cmath>

#include <conio.h>

#include <cstdlib>

#include <algorithm>

#include <windows.h>

using namespace std;

#define DIRECTION int

const char TEST_END = '0';

const int BOARDSIZE = 3;

const int TABLESIZE = 370000;

const int DIRECTION_SIZE = 4;

const int INIT_POS_IN_HASH = -1;

const int INIT_PARENT = -1;

const int INIT_START = -1;

const int INIT_G = 1;

const int G_GROW = 1;

const char BLANK = 'X';

enum VISITESTATE{ NOTFOUND, INOPEN, INCLOSE };

const int hashArr[9] = { 7, 17, 47, 117, 217, 977, 1299, 5971, 7779 };

const int dir_x[DIRECTION_SIZE] = { -1, 1, 0, 0 };

const int dir_y[DIRECTION_SIZE] = { 0, 0, -1, 1 };      //Up Down Left Right



struct position{

    position(){}

    position(int xx, int yy):x(xx),y(yy){}

    int x;

    int y;

};



position finalPosition[BOARDSIZE * BOARDSIZE];



struct ChessBoard{

    ChessBoard(){

        visitState = NOTFOUND;

        posInHashTable = INIT_POS_IN_HASH;

    }

    ChessBoard& operator = ( const ChessBoard& cb ){

        for( int i = 0; i < BOARDSIZE; ++i ){

            for( int j = 0; j < BOARDSIZE; ++j ){

                this->ChessState[i][j] = cb.ChessState[i][j];

            }

        }

        this->blankX = cb.blankX;

        this->blankY = cb.blankY;

        this->g = cb.g;

        this->h = cb.h;

        this->direction = cb.direction;

        this->parent = cb.parent;

        this->posInHashTable = cb.posInHashTable;

        return *this;

    }

    friend bool operator < ( const ChessBoard& a, const ChessBoard& b ){

        return ( a.g + a.h ) > ( b.g + b.h );

    }

    char ChessState[BOARDSIZE][BOARDSIZE];

    VISITESTATE visitState;

    int blankX;

    int blankY;

    int g;

    int h;

    int direction;

    int posInHashTable;

    int parent;

};



ChessBoard hashTable[TABLESIZE];



class AStarAlg{

    public:

        AStarAlg(){

            finalState.ChessState =

            {

                { '1', '2', '3' },

                { '4', '5', '6' },

                { '7', '8', BLANK }

            };

            initChessBoard();

        }

        void initChessBoard();

        void AStar();

        void printPath( ChessBoard );

        void showChessBoard( const ChessBoard& ) const;

        const ChessBoard& getChessBoard( int index ){ return hashTable[index]; };

        const ChessBoard& getInitalChessBoard(){ return initState; };

    private:

        bool isSolvable( const ChessBoard& );

        bool getNextChessBoard( ChessBoard& nextState, const ChessBoard& parentState, const DIRECTION& );

        int hashCal( ChessBoard& );

        void setInOpen( ChessBoard& );

        void updateOpen( const ChessBoard& );

        bool isInOpen( const ChessBoard& ) const;

        void setInClose( ChessBoard& );

        bool isNotFound( const ChessBoard& ) const;

        bool isInClose( const ChessBoard& ) const;

        void calHeuristic( ChessBoard& );

        void calG( ChessBoard& );

        void calFun( ChessBoard& );

        bool isEqual( const ChessBoard&, const ChessBoard& );



        vector< ChessBoard >openTable;

        ChessBoard initState;

        ChessBoard finalState;

};



bool AStarAlg::isSolvable( const ChessBoard& cb ){

    char* tempArr = new char[BOARDSIZE * BOARDSIZE + 1];

    const int length = BOARDSIZE * BOARDSIZE;

    int count = 0;

    int countNum = 0;

    for( int i = 0; i < BOARDSIZE; ++i ){

        for( int j = 0; j < BOARDSIZE; ++j ){

            if( initState.ChessState[i][j] == BLANK ) tempArr[count] = '9';

            else tempArr[count] = initState.ChessState[i][j];

            count++;

        }

    }

    for( int i = 0; i < length; ++i ){

        const int base = tempArr[i] - '0';

        for( int j = 0; j < i; ++j ){

            const int cmp = tempArr[j] - '0';

            if( cmp > base ) countNum++;

        }

    }

    delete tempArr;

    if( countNum % 2 != 0 ) return false;

    return true;

}



void AStarAlg::setInOpen( ChessBoard& cb ){

    cb.visitState = INOPEN;

    hashTable[cb.posInHashTable].visitState = INOPEN;

    openTable.push_back( cb );

    push_heap( openTable.begin(), openTable.end() );

}



void AStarAlg::printPath( ChessBoard cb ){

    if( cb.parent == INIT_PARENT ){

        cout<<"Finsh."<<endl;

        return;

    }

    vector<ChessBoard>path;

    while( true ){

        path.push_back( cb );

        if( cb.parent == INIT_PARENT ) break;

        cb = hashTable[cb.parent];

    }

    for( int i = path.size() - 1; i >= 0; --i ){

        showChessBoard( path[i] );

    }

}



void AStarAlg::updateOpen( const ChessBoard& cb ){

    for( int i = 0; i < openTable.size(); ++i ){

        if( isEqual( openTable[i], cb ) ){

            openTable[i] = cb;

            break;

        }

    }

    make_heap( openTable.begin(), openTable.end() );

}



void AStarAlg::setInClose( ChessBoard& cb ){

    hashTable[cb.posInHashTable].visitState = INCLOSE;

    cb.visitState = INCLOSE;

}



bool AStarAlg::isInClose( const ChessBoard& cb ) const{

    return ( hashTable[cb.posInHashTable].visitState == INCLOSE ) ? true : false;

}



bool AStarAlg::isInOpen( const ChessBoard& cb ) const{

    return ( hashTable[cb.posInHashTable].visitState == INOPEN ) ? true : false;

}



bool AStarAlg::isNotFound( const ChessBoard& cb ) const{

    return ( hashTable[cb.posInHashTable].visitState == NOTFOUND ) ? true : false;

}



//Manhattan distance (state : AC)

void AStarAlg::calHeuristic( ChessBoard& cb ){

    int h = 0;

    for( int i = 0; i < BOARDSIZE; ++i ){

        for( int j = 0; j < BOARDSIZE; ++j ){

            int val = cb.ChessState[i][j] - '0';

            int x = finalPosition[val - 1].x;

            int y = finalPosition[val - 1].y;

            h += abs( i - x ) + abs( j - y );

        }

    }

    cb.h = h;

}



void AStarAlg::calG( ChessBoard& cb ){

    if( cb.parent == INIT_PARENT ){     // caution : == =

        cb.g = INIT_G;

    }

    else{

        cb.g = hashTable[cb.parent].g + G_GROW;

    }

}



void AStarAlg::calFun( ChessBoard& cb ){

    calHeuristic( cb );

    calG( cb );

}



void AStarAlg::initChessBoard(){

    cout<<"Enter inital State : ";

    string str;

    getline( cin, str );

    int count = 0;

    for( int i = 0; i < str.length(); ++i ){

        if( str[i] != ' ' ){

            initState.ChessState[count / BOARDSIZE][count % BOARDSIZE] = str[i];

            if( str[i] == 'x' ){

                initState.ChessState[count / BOARDSIZE][count % BOARDSIZE] = BLANK;

                initState.blankX = count / BOARDSIZE;

                initState.blankY = count % BOARDSIZE;

            }

            ++count;

        }

    }

    initState.direction = INIT_START;

    initState.parent = INIT_PARENT;

    calFun( initState );

    int pos = hashCal( initState );

    openTable.push_back( initState );

    make_heap( openTable.begin(), openTable.end() );

}



//is equal with each other ( state : AC )

bool AStarAlg::isEqual( const ChessBoard& cbA, const ChessBoard& cbB ){

    for( int i = 0; i < BOARDSIZE; ++i ){

        for( int j = 0; j < BOARDSIZE; ++j ){

            if( cbA.ChessState[i][j] != cbB.ChessState[i][j] ) return false;

        }

    }

    return true;

}



//  function: calculate the position of the state of chessboard in hashTable

//  if the state has been existing ( INOPEN , INCLOSE ) then return its position is hashTble

//  else set the state in hashTable and then return its position

// PS: must after all operation ( my drawback )

int AStarAlg::hashCal( ChessBoard& cb ){

    int pos = 0;

    for( int i = 0; i < BOARDSIZE; ++i ){

        for( int j = 0; j < BOARDSIZE; ++j ){

            //'x'

            int val = cb.ChessState[i][j] - '0';

            pos += val * hashArr[ BOARDSIZE * i + j ];

        }

    }

    pos = pos % TABLESIZE;

    while( hashTable[pos].visitState != NOTFOUND ){

        if( isEqual( hashTable[pos], cb ) ){

            cb.posInHashTable = pos;

            return pos;

        }

        pos = ( pos + 1 ) % TABLESIZE;

    }

    cb.posInHashTable = pos;

    hashTable[pos] = cb;

    return pos;

}



//Just get next chess board state from its parent state ( state : AC )

bool AStarAlg::getNextChessBoard( ChessBoard& tempNextState,

                                                const ChessBoard& parentState,

                                                const DIRECTION& dir ){

    //Get temp next chess board blank_x and blank_y

    int tempNextBlankX = parentState.blankX + dir_x[dir];

    int tempNextBlankY = parentState.blankY + dir_y[dir];

    if( tempNextBlankX < 0 || tempNextBlankX > BOARDSIZE - 1

        || tempNextBlankY < 0 || tempNextBlankY > BOARDSIZE - 1 ) return false;



    tempNextState.blankX = tempNextBlankX;

    tempNextState.blankY = tempNextBlankY;

    tempNextState.direction = dir;

    //Get temp next chess board state

    for( int i = 0; i < BOARDSIZE; ++i ){

        for( int j = 0; j < BOARDSIZE; ++j ){

            tempNextState.ChessState[i][j] = parentState.ChessState[i][j];

        }

    }

    char change = tempNextState.ChessState[tempNextState.blankX][tempNextState.blankY];

    tempNextState.ChessState[parentState.blankX][parentState.blankY] = change;

    tempNextState.ChessState[tempNextState.blankX][tempNextState.blankY] = BLANK;

    //Get temp next chess board parent position

    tempNextState.parent = parentState.posInHashTable;

    //Get temp next chess board g and h, its parent state has got

    calFun( tempNextState );

    //Hash Cal

    hashCal( tempNextState );

    return true;

}



void AStarAlg::AStar(){

    char c;

    while( !openTable.empty() ){

        pop_heap( openTable.begin(), openTable.end() );

        ChessBoard parent = openTable.back();

        if( !isSolvable( parent ) ){

            cout<<"unsolvable"<<endl;

            return;

        }

        openTable.erase( openTable.end() - 1 );

        setInClose( parent );

       // showChessBoard( parent );

        //c = getch();

        if( isEqual( parent, finalState ) ){

            printPath( parent );

            return;

        }

        for( int i = 0; i < DIRECTION_SIZE; ++i ){

            ChessBoard tempNextState;

            if( !getNextChessBoard( tempNextState, parent, i ) ) continue;

            if( isNotFound( tempNextState ) ){

                setInOpen( tempNextState );

                continue;

            }

            if( isInOpen( tempNextState ) ){

                int f = tempNextState.g + tempNextState.h;

                if( f < hashTable[tempNextState.posInHashTable].g + hashTable[tempNextState.posInHashTable].h ){

                    hashTable[tempNextState.posInHashTable] = tempNextState;

                    updateOpen( tempNextState );

                    continue;

                }

            }

            if( isInClose( tempNextState ) ){

                int f = tempNextState.g + tempNextState.h;

                if( f < hashTable[tempNextState.posInHashTable].g + hashTable[tempNextState.posInHashTable].h ){

                    hashTable[tempNextState.posInHashTable] = tempNextState;

                    setInOpen( tempNextState );

                    continue;

                }

            }

        }

    }

    cout<<"unsolveable"<<endl;

}



//Show information of chess board ( State : AC )

void AStarAlg::showChessBoard( const ChessBoard& cb ) const{

    cout<<endl;

    cout<<"<<<<<<<<<<<<<<<<<<<<<< Pandora >>>>>>>>>>>>>>>>>>>>>"<<endl;

    cout<<"ChessBoard State : "<<endl;

    for( int i = 0; i < BOARDSIZE; ++i ){

        for( int j = 0; j < BOARDSIZE; ++j ){

            cout<<cb.ChessState[i][j]<<"  ";

        }

        cout<<endl;

    }

    cout<<"Blank_X : "<<cb.blankX<<"    "<<"Blank_Y : "<<cb.blankY<<endl;

    cout<<"Position is HashTable : "<<cb.posInHashTable<<endl;

    cout<<"Parent : "<<cb.parent<<endl;

    cout<<"G : "<<cb.g<<"   "<<"H : "<<cb.h<<"   "<<"F : "<<cb.h + cb.g<<endl;

    switch( cb.visitState ){

        case NOTFOUND:{

            cout<<"Now my state : Not be found."<<endl;

            break;

        }

        case INOPEN:{

            cout<<"Now my state : In open table."<<endl;

            break;

        }

        case INCLOSE:{

            cout<<"Now my state : In close"<<endl;

            break;

        }

        default:{

            cout<<"Error state!"<<endl;

            break;

        }

    }

    cout<<"<<<<<<<<<<<<<<<<<<<<<< Pandora >>>>>>>>>>>>>>>>>>>>>"<<endl;

    cout<<endl;

}



//Get the fianl chess board state ( State : AC )

void preWork(){

    int count = 0;

    for( int i = 0; i < BOARDSIZE; ++i ){

        for( int j = 0; j < BOARDSIZE; ++j ){

            position temp;

            temp.x = i;

            temp.y = j;

            finalPosition[count] = temp;

            count++;

        }

    }

}



int main(){

    preWork();

    AStarAlg a;

    a.AStar();

    return 0;

}