[인공지능] A* 알고리즘을 이용한 8-puzzle 만들기

초보자를 위한 A* 알고리즘 (기초개념 설명 및 소스)

참고 - http://egloos.zum.com/cozycoz/v/9748811

8-puzzle에서의 F, G, H값과 열린노드, 닫힌노드 간략한 설명

1) F = G + H, 열린 노드중에서 F값이 최소인 경우를 선택하여 이동한다.
2) G = 현재까지 이동한 횟수

- H = 목표 노드와 현재노드를 비교하여 맞지 않는 노드의 개수
- 열린 노드 : 현재 빈 공간에서 상, 하, 좌, 우 중 갈 수있는 방향을 설정(이때 부모 노드의 위치도 함께저장한다.)
- 닫힌 노드 : 이동하기 전의 현재 위치를 저장( 이동한 이후에 월래자리로 돌아가지 않게하기 위함이다.)

8 puzzle 결과

8 puzzle 소스코드

/****************************************/
/*  name : jihwan-yoon(blackcon)         */
/*  email  : 131ackcon@gmail.com       */
/*  date   : 2015. 04. 04                       */
/****************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define swap( a, b ) temp = a; a = b; b = temp;
#define TILE_NUM    9

typedef struct node{
    int parent;
    int child;
    struct node *next;
}NODE;
typedef struct list{
    int cnt;
    NODE* head;
}LIST;

char start[ TILE_NUM ] = { 2, 8, 3, 1, 6, 4, 7, -1, 5 }; 
char goal[ TILE_NUM ]  = { 1, 2, 3, 8, -1, 4, 7, 6, 5};  
char close = 0;     // 왔던 길은 close노드에 추가한다.
int  dist = 0;

void o_c_node_init( LIST *list );
void add_o_node( LIST *list, int parent, int child );
void del_node( LIST *list );
void func();
int  find_empty();
int  heruistic( LIST *list );
void draw( char *node );

void o_c_node_init( LIST *list )
{
    list->cnt = 0;
    list->head = NULL;
}

void add_o_node( LIST *list, int parent, int child )
{
    int i = 0;
    NODE *p = (NODE *)malloc( sizeof( NODE ) );
    p->parent = parent;
    p->child = child;
    NODE *tmp = list->head;
    // 다음 이동할 경로가 직전에 있었던 위치라면 return
    if( close == child )
        return;
    if( list->cnt == 0 ){
        list->head = p;
        p->next = list->head;
        list->cnt = 1;
    }
    else{
        tmp = list->head;
        for( i = 0; i < list->cnt; i++)
            tmp = tmp->next;
        p->next = tmp->next;
        tmp->next = p;
        list->cnt++;
    }
}

void del_node( LIST *list )
{
    NODE *tmp = list->head;
    while( list->cnt != 0 ){
        free( list->head );
        list->head = tmp->next;
        tmp->next = (tmp->next)->next;
        list->cnt--;
    }
}
int find_empty()
{
    int i = 0;
    int j = 0;
    int cnt = 0;
    /* 비어있는 타일을 찾는다.  */
    for( i = 0; i < TILE_NUM ; i++){
        if( start[i] == -1 ){
            return i;
        }
    }
    return -1;  // 비어있는 타일을 못찾았을 경우 -1반환.
}
void func()
{
    int i = 0;
    int cnt = 0;
    int empty = 0;
    int select[2] = {0x0, };    // [0] = parent, [1] = child

    LIST list;
    NODE *tmp;
    o_c_node_init( &list );   // 오픈 노드, 클로즈 노드  초기화
    empty = find_empty();   // 빈 타일 찾기

    /* 인접한 타일을 open노드에 추가한다. */
    if( empty != -1 ){
        if( empty > 2 ){                // UP
            add_o_node( &list, empty, empty-3 );
        }
        if( empty < 6 ){           // DOWN
            add_o_node( &list, empty, empty+3 );
        }
        if( (empty % 3) != 2 ){    // RIGHT
            add_o_node( &list, empty, empty +1 );
        }
        if( (empty % 3) != 0){     // LEFT
            add_o_node( &list, empty, empty -1);
        }

        /* 이동비용이 최소인 값을 찾는다. */
        dist++;
        close = empty;
        select[1] = heruistic( &list );
        tmp = list.head;
        while( 1 ){
            if( select[1] == tmp->child ){
                select[0] = tmp->parent;
                break;
            }
            tmp = tmp->next;
        }
        /* 공백(-1)과 이동할 위치에 있는 타일을 바꾼다. */
        start[ select[0] ] = start[ select[1] ];
        start[ select[1] ] = -1;
    }
    del_node( &list );
}
int heruistic( LIST *list )
{
    char node[ TILE_NUM ] = {0x0,};
    int misplaced = 0;
    int totalHerst = 0;
    int i = 0;
    int j = 0;
    int _short = -1;
    int select_node = 0;
    NODE *tmp = list->head;

    while( 1 ){
        if( i == list->cnt )
            break;
        else{
            misplaced = 0;
            memcpy( node, start, 9 );
            node[ tmp->child ]  = node[ tmp->parent ];
            node[ tmp->parent ] = -1;

            /* 목표 타일과 이동했을 때의 타일을 비교하여, 맞지 않는 타일의 개수를 확인한다. */
            for( j = 0; j < TILE_NUM ; j++){
                if( node[j] != goal[j] )
                    misplaced += 1;
            }
            totalHerst = dist + misplaced;

            /* 열린 노드중에서 F값이 가장 작은 노드를 찾는다. */
            if( (_short == -1) || (_short > totalHerst ) ){
                _short = totalHerst;
                select_node = tmp->child;
            }
            tmp = tmp->next;
            i++;
        }
    }
    printf( "close : %d, dist : %d, short path : %d, select tile: %d\n", close, dist, _short, select_node );
    return select_node;
}

void draw( char *node )
{
    int i = 0;
    for( i = 0; i < TILE_NUM; i++ ){
        if( i % 3 == 0 )    printf("\n" );
        if( node[i] == -1 )
            printf("  ");
        else
            printf("%d ", node[i] );
    }
    printf("\n");
}
int main( void )
{
    draw( start );
    while( 1 ){
        printf("=================\n");
        if( memcmp( start, goal, 9 ) == 0)  break;
        func();
        draw( start );
    }
    return 0;
}