# 너비 우선 탐색


너비 우선 탐색에서는 상태를 전개해 탐색 트리를 성장시킬 때 같은 레벨의 상태를 병행해서 전개해 탐색을 진행한다.
전개 작업은 목적으로 하는 노드를 발견할 때까지 반복한다.

예를 들어, 그림 2-11을 보면 첫 번째로 루트 노드 S를 전개하여 노드 A를 얻고 있다.
다음으로 전개할 노드를 결정할 때, 이미 구한 노드 A가 아닌 S를 전개하여 얻을 수 있는 다른 노드를 먼저 구한다.
그림 2-11에서는 노드 B와 C가 이에 해당한다.
이처럼 너비 우선 탐색에서는 어떤 노드를 전개할 때 전개 가능한 모든 노드를 먼저 구해둔다.

사용자 삽입 이미지



# 너비 우선 탐색 알고리즘

1) 오픈 리스트와 클로즈드 리스트 초기화
2) 오픈 리스트 끝에 루트 노드 삽입

> 아래 과정을 반복함
3) 오픈 리스트가 비어 있으면 종료(목표 노드를 발견하지 못함)
4) 오픈 리스트의 선두 요소가 목표 노드면 종료(목표 노드를 발견함)
5) 오픈 리스트의 선두 요소를 expand() 함수를 이용해 전개
6) 전개된 노드 중 오픈 리스트 또는 클로즈드 리스트의 노드와 중복되지 않는 노드를 오픈 리스트의 끝에 추가
7) 오픈 리스트의 선두 요소를 클로즈드 리스트의 끝으로 이동

너비우선 탐색 프로그램 width.c
width.c (513)


/************************************/
/*      너비 우선 탐색 프로그램     */
/*      width.c                     */
/************************************/

#include <stdio.h>

/*   기호 상수                    */
#define LIMITL 256 /* 배열 최대 영역 */
#define TRUE 1     /* 참(논리 값) */
#define START 1    /* 시작 노드 번호 */
#define GOAL 999   /* 목표 노드 번호 */

/*     노드를 표현하는 구조체     */
struct node {
    int nodeid; /* 노드 번호 */
    int parentid; /* 상위 노드 번호 */
};
/* 오픈 리스트와 클로즈드 리스트 */
struct node openlist[LIMITL];
int openlistep = 0;
struct node closedlist[LIMITL];
int closedlistep = 0;

/*   함수 프로토타입 선언   */
/* 리스트 초기화 */
void initlist();
/* 리스트의 상태 출력 */
void printlist();
/* 노드 전개 */
void expand(int id);
/* 선두 요소를 클로즈드 리스트로 이동 */
void movetofirst();
/* 오픈 리스트의 선두 요소 삭제 */
void removefirst();
/* ID 중복 검사 */
int check(int id);
/* 목표 노드까지의 경로 출력 */
void printroute(int id);


/**********************/
/*     main() 함수    */
/**********************/
int main()
{
    
    /* 초기화 */
    initlist();
    printlist();
    /* 탐색의 본체 */
    while (TRUE) {
        if (openlistep == 0) {
            /* 목표 노드를 발견하지 못함 */
            printf("목표 노드를 찾을 수 없습니다.\n");
            break;
        }
        /* 오픈 리스트의 선두 요소가 목표 노드면 종료 */
        if (openlist[0].nodeid == GOAL) {
            printf("\n목표 노드를 찾았습니다.\n");
            printf("%d[%d]", openlist[0].nodeid,
                   openlist[0].parentid);
            printroute(openlist[0].parentid);
            break;
        }
        /* 오픈 리스트의 선두 요소를 전개 */
        expand(openlist[0].nodeid);
        
        /* 선두 요소를 클로즈드 리스트로 이동 */
        movetofirst(); /* 클로즈드 리스트로 이동 */
        
        printlist();
        
    }
    
    return 0;
}
/************************************/
/*  printroute() 함수               */
/*  목표 노드에 이르는 경로를 출력  */
/************************************/
void printroute(int id)
{
    int i;
    /* 노드 번호가 id인 노드를 찾음 */
    for (i = 0; i < closedlistep; ++i)
        if (closedlist[i].nodeid == id) {
            printf("<-%d[%d]", closedlist[i].nodeid,
                   closedlist[i].parentid);
            break;
        }
    /* 다음 노드 출력 */
    if (closedlist[i].parentid != 0)
    /* 시작이 아니면 출력을 속행 */
        printroute(closedlist[i].parentid);
    printf("\n");
    
}

/**************************/
/*     check() 함수       */
/*     ID 중복 검사       */
/**************************/
int check(int id)
{
    int i;
    int res = 0;
    
    /* 오픈 리스트와의 중복 검사 */
    for (i = 0; i < openlistep; ++i)
        if (openlist[i].nodeid == id)
            res = TRUE;
    /* 클로즈드 리스트와의 중복 검사 */
    for (i = 0; i < closedlistep; ++i)
        if (closedlist[i].nodeid == id)
            res = TRUE;
    return res;
}


/**********************************/
/*   removefirst() 함수           */
/*   오픈 리스트의 선두 요소 삭제 */
/**********************************/
void removefirst()
{
    int i;
    for (i = 0; i < openlistep; ++i)
        openlist[i] = openlist[i+1];
    --openlistep;
}


/***********************/
/*  movetofirst() 함수 */
/*  선두 요소 이동     */
/***********************/
void movetofirst()
{
    /* 선두 요소를 클로즈드 리스트로 이동 */
    closedlist[closedlistep++] = openlist[0];
    /* 오픈 리스트 선두 요소 삭제 */
    removefirst();
}



/**********************/
/*   expand() 함수    */
/*   노드 전개        */
/**********************/
void expand(int id)
{
    /* 접속 관계 정보 */
    int tree[][5] = {
        {1, 2, 3, 5},
        {2, 4},
        {3, 6, 7},
        {5, 4, 8},
        {6, 5, 7},
        {8, 7, 999},
        {0} /* 정보의 끝 */
    };
    int i = 0;
    int j;
    
    while (tree[i][0] != 0) {
        if (tree[i][0] == id) {
            /* 전개 */
            for (j = 1; tree[i][j] != 0; ++j) {
                if (check(tree[i][j]) != TRUE) { /* 중복 검사 */
                    openlist[openlistep].nodeid = tree[i][j];
                    openlist[openlistep++].parentid = id;
                }
            }
            break;
        }
        ++i;
    }
    
}


/**********************/
/*  initlist() 함수   */
/*  리스트 초기화     */
/**********************/
void initlist()
{
    /* 오픈 리스트 초기화 */
    openlist[0].nodeid = START;
    openlist[0].parentid = 0;
    ++openlistep;
}

/**********************/
/*  printlist() 함수  */
/* 리스트의 상태 출력 */
/**********************/
void printlist()
{
    int i;
    
    /* 오픈 리스트 출력 */
    printf("\n오픈 리스트  ");
    for (i = 0; i < openlistep; ++i)
        printf("%d[%d],", openlist[i].nodeid,
               openlist[i].parentid);
    printf("\n");
    
    /* 클로즈드 리스트 출력 */
    printf("클로즈드 리스트  ");
    for (i = 0; i < closedlistep; ++i)
        printf("%d[%d],", closedlist[i].nodeid,
               closedlist[i].parentid);
    printf("\n");
}



사용자 삽입 이미지


width.c 프로그램의 실행에서는 오픈 리스트와 클로즈드 리스트가 변하는 모습을 나타내고 있다.
초기 상태에서는 루트 노드가 오픈 리스트에 저장되고, 탐색이 진행되면서 오픈 리스트의 선두 노드가 전개되어 간다.
마지막으로 오픈 리스트의 선두에 노드 번호 999인 목표 노드가 나타나면 목표 노드를 찾고 탐색을 종료한다.


# 실행 2-1 width.c 프로그램 실행
$ gcc width.c -o width
$ ls
width  width.c

$ ./width

오픈 리스트  1[0],
클로즈드 리스트 

오픈 리스트  2[1],3[1],5[1],
클로즈드 리스트  1[0],

오픈 리스트  3[1],5[1],4[2],
클로즈드 리스트  1[0],2[1],

오픈 리스트  5[1],4[2],6[3],7[3],
클로즈드 리스트  1[0],2[1],3[1],

오픈 리스트  4[2],6[3],7[3],8[5],
클로즈드 리스트  1[0],2[1],3[1],5[1],

오픈 리스트  6[3],7[3],8[5],
클로즈드 리스트  1[0],2[1],3[1],5[1],4[2],

오픈 리스트  7[3],8[5],
클로즈드 리스트  1[0],2[1],3[1],5[1],4[2],6[3],

오픈 리스트  8[5],
클로즈드 리스트  1[0],2[1],3[1],5[1],4[2],6[3],7[3],

오픈 리스트  999[8],
클로즈드 리스트  1[0],2[1],3[1],5[1],4[2],6[3],7[3],8[5],

목표 노드를 찾았습니다.
999[8]<-8[5]<-5[1]<-1[0]


실제 전개 작업은 expand() 함수 내부에 있는 167~179행의 while 문에서 처리한다.
expand() 함수에 인수로 주어진 노드 번호를 tree[][] 배열에서 찾아내고, 대응하는 전개 결과의 노드 번호를 오픈 리스트 끝에 추가한다.
다만 이때 171행에서 전개한 결과가 이미 오픈 리스트나 클로즈드 리스트에 포함되어 있는지를 check() 함수로 조사한다.
어느 한 쪽 리스트가 전개 결과 노드를 포함할 때는 오픈 리스트에 삽입하지 않는다.

expand() 함수의 서브 함수인 check() 함수(104~118행)에서는 인수로 주어진 노드 번호가 오픈 리스트 또는 클로즈드 리스트에 포함되어 있는지 조사한다.
구체적으로 110~112행에서 openlist[] 배열에 포함되어 있는지 조사하고, 114~116행에서 closedlist[] 배열을 조사한다.

# 탐색 트리의 데이터 변경후 실행
width2.c는 width.c 프로그램과 탐색 트리만 다른 프로그램

expand() 함수에 주는 데이터를 변경한 width2.c 프로그램 실행 예

/**********************/
/*   expand() 함수    */
/*   노드 전개        */
/**********************/
void expand(int id)
{
154 |    /* 접속 관계 정보 */
155 |    int tree[][5] = {
156 |        {1, 2, 3, 4},
157 |        {2, 10, 11},
158 |        {3, 12, 13, 14},
159 |        {4, 15, 16, 17},
160 |        {11, 21},
161 |        {12, 22},
162 |        {14, 23, 24},
163 |        {15, 4, 10, 999},
164 |        {16, 25},
165 |        {17, 26, 27},
166 |        {0} /* 정보의 끝 */
167 |    };

width2.c 프로그램에서 expand() 함수에 준 탐색 트리 데이터(tree[][] 배열의 초깃값, 위의 예제 154~163행에 대응)


width2.c 프로그램 실행
width2.c (521)


오픈 리스트  1[0],
클로즈드 리스트 

오픈 리스트  2[1],3[1],4[1],
클로즈드 리스트  1[0],

오픈 리스트  3[1],4[1],10[2],11[2],
클로즈드 리스트  1[0],2[1],

오픈 리스트  4[1],10[2],11[2],12[3],13[3],14[3],
클로즈드 리스트  1[0],2[1],3[1],

오픈 리스트  10[2],11[2],12[3],13[3],14[3],15[4],16[4],17[4],
클로즈드 리스트  1[0],2[1],3[1],4[1],

오픈 리스트  11[2],12[3],13[3],14[3],15[4],16[4],17[4],
클로즈드 리스트  1[0],2[1],3[1],4[1],10[2],

오픈 리스트  12[3],13[3],14[3],15[4],16[4],17[4],21[11],
클로즈드 리스트  1[0],2[1],3[1],4[1],10[2],11[2],

오픈 리스트  13[3],14[3],15[4],16[4],17[4],21[11],22[12],
클로즈드 리스트  1[0],2[1],3[1],4[1],10[2],11[2],12[3],

오픈 리스트  14[3],15[4],16[4],17[4],21[11],22[12],
클로즈드 리스트  1[0],2[1],3[1],4[1],10[2],11[2],12[3],13[3],

오픈 리스트  15[4],16[4],17[4],21[11],22[12],23[14],24[14],
클로즈드 리스트  1[0],2[1],3[1],4[1],10[2],11[2],12[3],13[3],14[3],

오픈 리스트  16[4],17[4],21[11],22[12],23[14],24[14],999[15],
클로즈드 리스트  1[0],2[1],3[1],4[1],10[2],11[2],12[3],13[3],14[3],15[4],

오픈 리스트  17[4],21[11],22[12],23[14],24[14],999[15],25[16],
클로즈드 리스트  1[0],2[1],3[1],4[1],10[2],11[2],12[3],13[3],14[3],15[4],16[4],

오픈 리스트  21[11],22[12],23[14],24[14],999[15],25[16],26[17],27[17],
클로즈드 리스트  1[0],2[1],3[1],4[1],10[2],11[2],12[3],13[3],14[3],15[4],16[4],17[4],

오픈 리스트  22[12],23[14],24[14],999[15],25[16],26[17],27[17],
클로즈드 리스트  1[0],2[1],3[1],4[1],10[2],11[2],12[3],13[3],14[3],15[4],16[4],17[4],21[11],

오픈 리스트  23[14],24[14],999[15],25[16],26[17],27[17],
클로즈드 리스트  1[0],2[1],3[1],4[1],10[2],11[2],12[3],13[3],14[3],15[4],16[4],17[4],21[11],22[12],

오픈 리스트  24[14],999[15],25[16],26[17],27[17],
클로즈드 리스트  1[0],2[1],3[1],4[1],10[2],11[2],12[3],13[3],14[3],15[4],16[4],17[4],21[11],22[12],23[14],

오픈 리스트  999[15],25[16],26[17],27[17],
클로즈드 리스트  1[0],2[1],3[1],4[1],10[2],11[2],12[3],13[3],14[3],15[4],16[4],17[4],21[11],22[12],23[14],24[14],

목표 노드를 찾았습니다.
999[15]<-15[4]<-4[1]<-1[0]



출처 : 인공지능을 이용한 빅데이터 처리

※ 위 내용은, 여러 자료를 참고하거나 제가 주관적으로 정리한 것입니다.
   잘못된 정보나 보완이 필요한 부분을, 댓글 또는 메일로 보내주시면 많은 도움이 되겠습니다.
07 30, 2014 11:29 07 30, 2014 11:29


Trackback URL : http://develop.sunshiny.co.kr/trackback/1018

Leave a comment

« Previous : 1 : ... 27 : 28 : 29 : 30 : 31 : 32 : 33 : 34 : 35 : ... 648 : Next »

Recent Posts

  1. HDFS - Python Encoding 오류 처리
  2. HP - Vertica ROS Container 관련 오류...
  3. HDFS - Hive 실행시 System Time 오류
  4. HP - Vertica 사용자 쿼리 이력 테이블...
  5. Client에서 HDFS 환경의 데이터 처리시...

Recent Comments

  1. 안녕하세요^^ 배그핵
  2. 안녕하세요^^ 도움이 되셨다니, 저... sunshiny
  3. 정말 큰 도움이 되었습니다.. 감사합... 사랑은
  4. 네, 안녕하세요. 댓글 남겨 주셔서... sunshiny
  5. 감사합니다 많은 도움 되었습니다!ㅎㅎ 프리시퀸스

Recent Trackbacks

  1. Mysql - mysql 설치후 Character set... 멀고 가까움이 다르기 때문 %M

Calendar

«   10 2019   »
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    

Bookmarks

  1. 위키피디아
  2. MysqlKorea
  3. 오라클 클럽
  4. API - Java
  5. Apache Hadoop API
  6. Apache Software Foundation
  7. HDFS 생태계 솔루션
  8. DNSBL - Spam Database Lookup
  9. Ready System
  10. Solaris Freeware
  11. Linux-Site
  12. 윈디하나의 솔라나라

Site Stats

TOTAL 2724089 HIT
TODAY 555 HIT
YESTERDAY 589 HIT