본문 바로가기
Computer Languages/C | C++

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

by blackcon 2015. 4. 4.
728x90

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

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

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

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

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

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;
}
728x90

댓글8

  • 코드실행이 안됩니다 ㅠㅠ 2015.04.08 01:06

    코드 win32콘솔창 cpp로 실행했는데
    빌드는 되는데 73번째 줄에서 디버깅이 자꾸 뜨네요ㅠㅠ
    어떻게 해야될까요 ㅠㅠ
    답글

    • blackcon 2015.04.09 00:37 신고

      일단 저는 Ubuntu 14.04에서 gcc 4.8.2버전으로 컴파일했구요.
      그리고 win32에서 컴파일해도 작동될텐데말이죠. 지금 어떤상황인지도 모르겠고 그 상황에서 디버깅해봐야 알거같아여 :D

  • 파아랑새 2015.10.17 14:36 신고

    숫자 몇개 위치 바꿔어 봤는데 무한 루프에 빠져요ㅜㅜ
    답글

    • blackcon 2015.10.17 22:06 신고

      저거 이론은 맞는데 과제에 급급하다 보니깐 다른케이스 테스트를 못해봤네요...ㅎㅎ 다른 예외도 좀 많이 있을듯 하구요. 일단 모든 케이스에 대해서 완벽한 코드는 아니라는점 알아주세요^^

  • 이레 2016.09.26 12:03

    정말감사합니다ㅠ 다른글 읽어봐도 도대체 이걸 어떻게 8-퍼즐에 응용해야할지 모르겠는데
    딱알려주시네요.
    살았습니다.
    코드는 직접 짜봐야겠네요
    그런데 어떻게 저런푸는방법이 나온건지 궁굼하네요.
    뭔가... 공식만알지 이공식이 어떻게 나온건지 모르겠다 뭐 그런느낌입니다
    답글

  • 2016.12.08 21:29

    비밀댓글입니다
    답글

  • ㅜㅜ 2021.05.21 15:42

    tmp->next = (tmp->next)->next; 부분에서

    아래와 같은 에러가 뜨는데 해결방법 있을까요?

    처리되지 않은 예외가 throw됨: 읽기 액세스 위반입니다.
    tmp->**next**이(가) 0xDDDDDDDD였습니다.


    답글

    • blackcon 2021.05.26 14:37 신고

      음, 포인터 참조가 잘못된듯한데요. tmp변수에 다음 구조체의 주소가 제대로 들어갔는지 확인이 필요할듯 하구요.

      그리고 tmp 멤버변수들(NODE구조체)이 제대로 할당 되었는지도 확인이 필요해보입니다! :)