본문 바로가기
Programming/Algorithm

슬라이딩 퍼즐 - A* 알고리즘으로 풀기

by 작은별하나 2015. 2. 18.
반응형

이제, 최종적으로 구현을 한 프로그램입니다.

 

A* 알고리즘을 적용하기 위해서 A* 용 자료구조를 설계했습니다.

 

A* 알고리즘에서는 기본적으로 힙 구조를 사용하며, 검색을 빨리 하기 위해서 해시테이블을 이용합니다.  그래서 두 가지 모두를 결합한 형태의 자료구조를 만들었습니다.

 

[PuzzleNode 자료구조]

class PuzzleNode : public PQueue::Node
{
public:
    PuzzleNode(char *csquares, int cEmptySquare, int cvalue) : value(cvalue), visited(false)
    {
        squares = csquares;
        emptySquare = cEmptySquare;
        est = 0;
        for( int i = 0 ; i < numSquares ; i++ )
        {
            if( squares[i] == 0 ) continue;
            int row = (squares[i]-1)/numCols;
            int col = (squares[i]-1)%numCols;
            est += abs(col - i%numCols) + abs(row - i/numCols);
        }
    }

    virtual ~PuzzleNode()
    {
        if( squares ) delete[] squares;
    }

    virtual bool Compare(const Node *node)
    {
        const PuzzleNode *cnode = (const PuzzleNode *)node;
        return( value+est <= cnode->value+cnode->est );
    }

    static void SetDimension(int rows, int cols)
    {
        numRows = rows;
        numCols = cols;
        numSquares = rows*cols;
    }

public:
    static int numRows, numCols, numSquares;
    char *squares;
    int emptySquare;
    int value, est;
    PuzzleNode *from;
    int cmd;
    bool visited;
    PuzzleNode *next;
};

이 자료구조는 우선순위 큐에도 들어가고 해시테이블에도 들어갑니다.  우선순위 큐에서는 value와 est 값의 합을 가지고 가장 작은 값이 큐에서 나올 수 있게 설계를 하였습니다.

 

[A* 알고리즘 풀이]

void SolvePuzzle(void *param)
{
    PuzzleParams *pp = (PuzzleParams *)param;

    PQueue queue;
    PuzzleNode *hash[HASHSIZE];

    PuzzleNode::SetDimension(pp->rows, pp->cols);

    memset(hash, 0, sizeof(hash));

    char *csquares = new char[pp->rows*pp->cols];
    memcpy(csquares, pp->squares, pp->rows*pp->cols*sizeof(char));

    PuzzleNode *node = new PuzzleNode(csquares, pp->emptySquare, 0);
    queue.Add(node);
    AddHash(hash, node);
    node->from = (PuzzleNode *)0;
    pp->numNodes = 1;

    while( queue.IsEmpty() == false )
    {
        node = (PuzzleNode *)queue.GetTop();
        node->visited = true;

        if( node->est == 0 ) break;

        for( int i = 0 ; i < 4 ; i++ )
        {
            char *newSquares = new char[PuzzleNode::numSquares];
            memcpy(newSquares, node->squares, PuzzleNode::numSquares*sizeof(char));
            int newEmptySquare = Move(newSquares, PuzzleNode::numRows, PuzzleNode::numCols, node->emptySquare, (eMove)i);
            if( node->emptySquare == newEmptySquare )
            {
                delete[] newSquares;
                continue;
            }
            PuzzleNode *t = FindHash(hash, newSquares);
            if( !t )
            {
                t = new PuzzleNode(newSquares, newEmptySquare, node->value+1);
                queue.Add(t);
                AddHash(hash, t);
                t->cmd = i;
                t->from = node;
                pp->numNodes++;
            }
            else if( t->visited == false && node->value + 1 < t->value )
            {
                delete[] newSquares;
                t->value = node->value+1;
                queue.Add(t);
                t->cmd = i;
                t->from = node;
            }
        }
    }

    int resultNum = 0;
    if( pp->result ) delete[] pp->result;
    pp->result = new char[node->value];
    for( PuzzleNode *t = node ; t->from ; t = t->from, resultNum++ )
    {
        pp->result[resultNum] = t->cmd;
    }
    pp->numResult = resultNum;

    for( int i = 0 ; i < HASHSIZE ; i++ )
    {
        while( hash[i] )
        {
            PuzzleNode *t = hash[i];
            hash[i] = t->next;
            delete t;
        }
    }
}

 

풀이과정은 일반적인 A* 알고리즘과 동일합니다.

 

이 프로그램을 실행하면, 가장 최적의 해를 찾아서 퍼즐을 풀어줍니다.  그런데 안타깝게도 퍼즐의 크기가 늘어나면, 계산량도 그에 따라서 엄청나게 늘어납니다.  너무나도 당연하겠지만, 4x4와 5x5의 경우의 수는 엄청난 차이입니다.  5x5 경우의 수는 4x4 경우의 수의 천억배나 되니까요.  4x4를 1초 만에 풀었다고 해도, 5x5는 3,000년이 걸리니까요.  5x5를 해보시더라도, 아주 잘 마무리될 수도 있지만, 아닐 수도 있습니다.

 

4x4 풀이에 대한 동영상을 여기에 올립니다.

 

 

 

 

 

 

 

 

댓글