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


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 풀이에 대한 동영상을 여기에 올립니다.








저작자 표시 비영리 변경 금지
신고