DFS, BFS, UCS

요샌 이것저것 발표 준비와 학교 수업 + 레포트 + 중간고사..로 인해 거의 글을 못쓰고 있습니다.;;
DFS, BFS, UCS는 이번 인공지능 과목에서 교수님이 내주신 레포트입니다.

세 알고리즘을 코딩하여 비교 분석하라는 레포트였습니다. 

 
 프로그래밍 해놓은 코드를 올려놓기 전에 DFS, BFS, UCS가 뭔지 간략하게만 설명하겠습니다.

DFS :  Depth-First Search ( 깊이 우선 탐색 )
우리의 초기노드 a에서 목표노드 u를 찾아가는데 있어서 깊이우선으로 탐색한다는 것입니다.
즉 찾는 순서는
 
a -> b -> e -> k -> s -> i -> t -> f -> m .............
이런식으로 가게됩니다. 초록색으로 써져있는 숫자는 UCS를 할 때 사용되는 각 경로 비용입니다.

위와 같이 찾아가게됩니다. "현재 탐색할 노드(총 경로비용,부모노드)" 이렇게 구성이되고
OPEN노드 가장 앞에 있는 것이 u인지 검사 후 아니면 해당 노드의 자식 노드들이 있으면 자식 노드를 OPEN의 앞에 넣고 해당 노드를 CLOSED에 넣는 것입니다. 이런식으로 진행;;

BFS :  Breadth-Firsh Search ( 넓이 우선 탐색 )

찾는 순서
a -> b -> c -> d -> e -> f -> g -> h -> i -> ....
이런식으로 갑니다.

구현 시 DFS와 다른 점은 자식 노드를 OPEN에 넣을 때 앞에 넣는 것이 아닌 뒤에 넣으면 됩니다.

 

UCS :  Uniform-Cost Search ( 균일 비용 탐색 )

이 알고리즘의 찾는 순서는 OPEN 노드에 있는 노드들 중 가장 경로비용이 작은 값을 선택해서 찾아가는 것입니다.
OPEN과 CLOSE로 비교를 해보겠습니다. ( 아래 그림은 위 문제와는 약간 다르게 썼습니다. 경로비용을 임의로 잡음 )

 

중간에 sorting을 한번 해주는 것입니다. ( Bubble sort 사용 )
경로 비용의 값에 따라 오름차순으로 정렬를 시켜 준 후 BFS와 똑같이 동작하게끔 하면 됩니다.  

#include <stdio.h> #include <Windows.h> #include <conio.h> enum { GREY = 0x7, WHITE = 0xF, GREEN = 0xA, CYAN = 0xB, RED = 0xc, YELLOW = 0xE }; typedef struct Node{ Node* leftNode; char key; Node* parentNode; Node* middleNode; int cost; int totalCost; Node* rightNode; int num; }Node; typedef struct Open{ Open* previous; Node* node; Open* next; }Open; typedef struct Closed{ Node* node; }Closed; Node node[22] = {0,}; Open open[22]; Closed closed[22] = {0,}; void DFS(char goal); void BFS(char goal); void UCS(char goal); void ascendingNode(Open* open, int* FirstNode, int* LastNode); void printOPEN_CLOSED(Open* open, Closed* closed, int FirstNode, int closeNum); void FindPath(Open* open,int FirstNode, int FindNum); void Set_Color_Console(WORD color) { HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE); SetConsoleTextAttribute(hConsole,color); } void InitializeNodes() { for(int i = 0 ; i < 22; i++) { memset(&node[i],0,sizeof(Node)); memset(&closed[i],0,sizeof(Closed)); memset(&open[i],0,sizeof(Open)); } node[1].leftNode = &node[2]; node[1].key = 'a'; node[1].parentNode = NULL; node[1].middleNode = &node[3]; node[1].cost = 0; node[1].totalCost = 0; node[1].rightNode = &node[4]; node[1].num = 1; node[2].leftNode = &node[5]; node[2].key = 'b'; node[2].parentNode = &node[1]; node[2].middleNode = NULL; node[2].cost = 3; node[2].totalCost = 0; node[2].rightNode = &node[6]; node[2].num = 2; node[3].leftNode = &node[7]; node[3].key = 'c'; node[3].parentNode = &node[1]; node[3].middleNode = NULL; node[3].cost = 4; node[3].totalCost = 0; node[3].rightNode = &node[8]; node[3].num = 3; node[4].leftNode = &node[9]; node[4].key = 'd'; node[4].parentNode = &node[1]; node[4].middleNode = NULL; node[4].cost = 4; node[4].totalCost = 0; node[4].rightNode = &node[10]; node[4].num = 4; node[5].leftNode = &node[11]; node[5].key = 'e'; node[5].parentNode = &node[2]; node[5].middleNode = NULL; node[5].cost = 2; node[5].totalCost = 0; node[5].rightNode = &node[12]; node[5].num = 5; node[6].leftNode = NULL; node[6].key = 'f'; node[6].parentNode = &node[2]; node[6].middleNode = NULL; node[6].cost = 7; node[6].totalCost = 0; node[6].rightNode = &node[13]; node[6].num = 6; node[7].leftNode = &node[14]; node[7].key = 'g'; node[7].parentNode = &node[3]; node[7].middleNode = NULL; node[7].cost = 8; node[7].totalCost = 0; node[7].rightNode = NULL; node[7].num = 7; node[8].leftNode = &node[15]; node[8].key = 'h'; node[8].parentNode = &node[3]; node[8].middleNode = NULL; node[8].cost = 2; node[8].totalCost = 0; node[8].rightNode = &node[16]; node[8].num = 8; node[9].leftNode = NULL; node[9].key = 'i'; node[9].parentNode = &node[4]; node[9].middleNode = NULL; node[9].cost = 10; node[9].totalCost = 0; node[9].rightNode = &node[17]; node[9].num = 9; node[10].leftNode = NULL; node[10].key = 'j'; node[10].parentNode = &node[4]; node[10].middleNode = NULL; node[10].cost = 3; node[10].totalCost = 0; node[10].rightNode = &node[18]; node[10].num = 10; node[11].leftNode = &node[19]; node[11].key = 'k'; node[11].parentNode = &node[5]; node[11].middleNode = NULL; node[11].cost = 5; node[11].totalCost = 0; node[11].rightNode = NULL; node[11].num = 11; node[12].leftNode = NULL; node[12].key = 'l'; node[12].parentNode = &node[5]; node[12].middleNode = NULL; node[12].cost = 6; node[12].totalCost = 0; node[12].rightNode = &node[20]; node[12].num = 12; node[13].leftNode = NULL; node[13].key = 'm'; node[13].parentNode = &node[6]; node[13].middleNode = NULL; node[13].cost = 9; node[13].totalCost = 0; node[13].rightNode = NULL; node[13].num = 13; node[14].leftNode = NULL; node[14].key = 'n'; node[14].parentNode = &node[7]; node[14].middleNode = NULL; node[14].cost = 1; node[14].totalCost = 0; node[14].rightNode = NULL; node[14].num = 14; node[15].leftNode = NULL; node[15].key = 'o'; node[15].parentNode = &node[8]; node[15].middleNode = NULL; node[15].cost = 3; node[15].totalCost = 0; node[15].rightNode = NULL; node[15].num = 15; node[16].leftNode = NULL; node[16].key = 'p'; node[16].parentNode = &node[8]; node[16].middleNode = &node[21]; node[16].cost = 5; node[16].totalCost = 0; node[16].rightNode = NULL; node[16].num = 16; node[17].leftNode = NULL; node[17].key = 'q'; node[17].parentNode = &node[9]; node[17].middleNode = NULL; node[17].cost = 8; node[17].totalCost = 0; node[17].rightNode = NULL; node[17].num = 17; node[18].leftNode = NULL; node[18].key = 'r'; node[18].parentNode = &node[10]; node[18].middleNode = NULL; node[18].cost = 7; node[18].totalCost = 0; node[18].rightNode = NULL; node[18].num = 18; node[19].leftNode = NULL; node[19].key = 's'; node[19].parentNode = &node[11]; node[19].middleNode = NULL; node[19].cost = 7; node[19].totalCost = 0; node[19].rightNode = NULL; node[19].num = 19; node[20].leftNode = NULL; node[20].key = 't'; node[20].parentNode = &node[12]; node[20].middleNode = NULL; node[20].cost = 8; node[20].totalCost = 0; node[20].rightNode = NULL; node[20].num = 20; //We will find this node. node[21].leftNode = NULL; node[21].key = 'u'; node[21].parentNode = &node[16]; node[21].middleNode = NULL; node[21].cost = 6; node[21].totalCost = 0; node[21].rightNode = NULL; node[21].num = 21; for(int i = 1; i < 22; i++) { open[i].node = &node[i]; } open[1].node = &node[1]; } int main(void) { int menu; int goal; while(1) { InitializeNodes(); Set_Color_Console(RED); printf( " ____ __ ___ __ __ \n" " / __ \\____ ______/ /__ / (_) / / / /___ ____ ____ \n" " / /_/ / __ `/ ___/ //_/ __ / / / / /_/ / __ \\/ __ \\/ __ \\ \n" " / ____/ /_/ / / / ,< / /_/ / / / __ / /_/ / /_/ / / / / \n" "/_/ \\__,_/_/ /_/|_| \\____/_/ /_/ /_/\\____/\\____/_/ /_/ \n" ); Set_Color_Console(GREY); printf("=== Search Menu === \n"); printf("1. DFS \n"); printf("2. BFS \n"); printf("3. UCS \n"); printf("Select Num : "); scanf("%d",&menu); fflush(stdin); printf("Input Goal : "); scanf("%c",&goal); printf("\n"); switch(menu) { case 1: DFS(goal); break; case 2: BFS(goal); break; case 3: UCS(goal); break; } system("cls"); } return 0; } //깊이우선탐색 void DFS(char goal) { int FirstNode = 1; int closeNum = 1; int FindNum = 0; while(1) { printOPEN_CLOSED(open,closed,FirstNode,closeNum); FindNum++; if(open[FirstNode].node->key != goal) { bool L = false; bool M = false; bool R = false; //Chile Node가 있는지 탐색 //있으면 OPEN에 넣기 위해 구조체 할당 if(open[FirstNode].node->leftNode != NULL) { open[FirstNode].node->leftNode->totalCost = open[FirstNode].node->totalCost + open[FirstNode].node->leftNode->cost; L = true; } if(open[FirstNode].node->middleNode != NULL) { open[FirstNode].node->middleNode->totalCost = open[FirstNode].node->totalCost + open[FirstNode].node->middleNode->cost; M = true; } if(open[FirstNode].node->rightNode != NULL) { open[FirstNode].node->rightNode->totalCost = open[FirstNode].node->totalCost + open[FirstNode].node->rightNode->cost; R = true; } //더블 링크드 리스트로 OPEN 정리 if(R == true) { closed[closeNum++].node = open[FirstNode].node; //OPEN의 가장 앞에 오른쪽 노드를 넣음 open[open[FirstNode].node->rightNode->num].next = open[FirstNode].next; if(open[FirstNode].next != NULL) open[FirstNode].next->previous = &open[open[FirstNode].node->rightNode->num]; if(M == true) { open[open[FirstNode].node->middleNode->num].next = &open[open[FirstNode].node->rightNode->num]; open[open[FirstNode].node->rightNode->num].previous = &open[open[FirstNode].node->middleNode->num]; if(L == true) { open[open[FirstNode].node->leftNode->num].next = &open[open[FirstNode].node->middleNode->num]; open[open[FirstNode].node->middleNode->num].previous = &open[open[FirstNode].node->leftNode->num]; FirstNode = open[FirstNode].node->leftNode->num; } else { FirstNode = open[FirstNode].node->middleNode->num; } } else if(L == true) { open[open[FirstNode].node->leftNode->num].next = &open[open[FirstNode].node->rightNode->num]; open[open[FirstNode].node->rightNode->num].previous = &open[open[FirstNode].node->leftNode->num]; FirstNode = open[FirstNode].node->leftNode->num; } else { FirstNode = open[FirstNode].node->rightNode->num; } } else if(M == true) { closed[closeNum++].node = open[FirstNode].node; open[open[FirstNode].node->middleNode->num].next = open[FirstNode].next; open[FirstNode].next->previous = &open[open[FirstNode].node->middleNode->num]; if(L == true) { open[open[FirstNode].node->leftNode->num].next = &open[open[FirstNode].node->middleNode->num]; open[open[FirstNode].node->middleNode->num].previous = &open[open[FirstNode].node->leftNode->num]; FirstNode = open[FirstNode].node->leftNode->num; } else { FirstNode = open[FirstNode].node->middleNode->num; } } else if(L == true) { closed[closeNum++].node = open[FirstNode].node; open[open[FirstNode].node->leftNode->num].next = open[FirstNode].next; open[FirstNode].next->previous = &open[open[FirstNode].node->leftNode->num]; FirstNode = open[FirstNode].node->leftNode->num; } else { int temp; closed[closeNum++].node = open[FirstNode].node; temp = open[FirstNode].next->node->num; open[FirstNode].next->previous = NULL; open[FirstNode].next = NULL; FirstNode = temp; } } else break; } FindPath(open,FirstNode,FindNum); } //넓이우선탐색 void BFS(char goal) { int PreviousFirstNode = 1; int FirstNode = 1; int LastNode = 1; int closeNum = 1; int FindNum = 0; while(1) { printOPEN_CLOSED(open,closed,FirstNode,closeNum); FindNum++; if(open[FirstNode].node->key != goal) { bool L = false; bool M = false; bool R = false; //Chile Node가 있는지 탐색 //있으면 OPEN에 넣기 위해 구조체 할당 if(open[FirstNode].node->leftNode != NULL) { open[FirstNode].node->leftNode->totalCost = open[FirstNode].node->totalCost + open[FirstNode].node->leftNode->cost; L = true; } if(open[FirstNode].node->middleNode != NULL) { open[FirstNode].node->middleNode->totalCost = open[FirstNode].node->totalCost + open[FirstNode].node->middleNode->cost; M = true; } if(open[FirstNode].node->rightNode != NULL) { open[FirstNode].node->rightNode->totalCost = open[FirstNode].node->totalCost + open[FirstNode].node->rightNode->cost; R = true; } //First Node Delete closed[closeNum++].node = open[FirstNode].node; PreviousFirstNode = FirstNode; if(open[FirstNode].next != NULL) { FirstNode = open[FirstNode].next->node->num; open[PreviousFirstNode].next->previous = NULL; open[PreviousFirstNode].next = NULL; open[PreviousFirstNode].previous = NULL; } else { if(L == true) FirstNode = open[FirstNode].node->leftNode->num; else if(M == true) FirstNode = open[FirstNode].node->middleNode->num; else if(R == true) FirstNode = open[FirstNode].node->rightNode->num; } //더블 링크드 리스트로 OPEN 정리 if(L == true) { open[open[PreviousFirstNode].node->leftNode->num].previous = &open[LastNode]; if(open[LastNode].previous != NULL) open[LastNode].next = &open[open[PreviousFirstNode].node->leftNode->num]; if(M == true) { open[open[PreviousFirstNode].node->middleNode->num].previous = &open[open[PreviousFirstNode].node->leftNode->num]; open[open[PreviousFirstNode].node->leftNode->num].next = &open[open[PreviousFirstNode].node->middleNode->num]; if(R == true) { open[open[PreviousFirstNode].node->rightNode->num].previous = &open[open[PreviousFirstNode].node->middleNode->num]; open[open[PreviousFirstNode].node->middleNode->num].next = &open[open[PreviousFirstNode].node->rightNode->num]; LastNode = open[PreviousFirstNode].node->rightNode->num; } else { LastNode = open[PreviousFirstNode].node->middleNode->num; } } else if(R == true) { open[open[PreviousFirstNode].node->leftNode->num].next = &open[open[PreviousFirstNode].node->rightNode->num]; open[open[PreviousFirstNode].node->rightNode->num].previous = &open[open[PreviousFirstNode].node->leftNode->num]; LastNode = open[PreviousFirstNode].node->rightNode->num; } else { LastNode = open[PreviousFirstNode].node->leftNode->num; } } else if(M == true) { open[open[PreviousFirstNode].node->middleNode->num].previous = &open[LastNode]; if(open[LastNode].previous != NULL) open[LastNode].next = &open[open[PreviousFirstNode].node->middleNode->num]; if(R == true) { open[open[PreviousFirstNode].node->rightNode->num].previous = &open[open[PreviousFirstNode].node->middleNode->num]; open[open[PreviousFirstNode].node->middleNode->num].next = &open[open[PreviousFirstNode].node->rightNode->num]; LastNode = open[PreviousFirstNode].node->rightNode->num; } else { LastNode = open[PreviousFirstNode].node->middleNode->num; } } else if(R == true) { open[open[PreviousFirstNode].node->rightNode->num].previous = &open[LastNode]; if(open[LastNode].previous != NULL) open[LastNode].next = &open[open[PreviousFirstNode].node->rightNode->num]; LastNode = open[PreviousFirstNode].node->rightNode->num; } } else break; } FindPath(open,FirstNode,FindNum); } //균일비용탐색 void UCS(char goal) { int PreviousFirstNode = 1; int FirstNode = 1; int LastNode = 1; int closeNum = 1; int FindNum = 0; while(1) { //totalCost 값에 따라 오름차순으로 OPEN 정렬 ( bubble sort 사용.. ) ascendingNode(open,&FirstNode,&LastNode); printOPEN_CLOSED(open,closed,FirstNode,closeNum); FindNum++; if(open[FirstNode].node->key != goal) { bool L = false; bool M = false; bool R = false; //Chile Node가 있는지 탐색 //있으면 OPEN에 넣기 위해 구조체 할당 if(open[FirstNode].node->leftNode != NULL) { open[FirstNode].node->leftNode->totalCost = open[FirstNode].node->totalCost + open[FirstNode].node->leftNode->cost; L = true; } if(open[FirstNode].node->middleNode != NULL) { open[FirstNode].node->middleNode->totalCost = open[FirstNode].node->totalCost + open[FirstNode].node->middleNode->cost; M = true; } if(open[FirstNode].node->rightNode != NULL) { open[FirstNode].node->rightNode->totalCost = open[FirstNode].node->totalCost + open[FirstNode].node->rightNode->cost; R = true; } //First Node Delete closed[closeNum++].node = open[FirstNode].node; PreviousFirstNode = FirstNode; if(open[FirstNode].next != NULL) { FirstNode = open[FirstNode].next->node->num; open[PreviousFirstNode].next->previous = NULL; open[PreviousFirstNode].next = NULL; open[PreviousFirstNode].previous = NULL; } else { if(L == true) FirstNode = open[FirstNode].node->leftNode->num; else if(M == true) FirstNode = open[FirstNode].node->middleNode->num; else if(R == true) FirstNode = open[FirstNode].node->rightNode->num; } //더블 링크드 리스트로 OPEN 정리 if(L == true) { open[open[PreviousFirstNode].node->leftNode->num].previous = &open[LastNode]; if(open[LastNode].previous != NULL) open[LastNode].next = &open[open[PreviousFirstNode].node->leftNode->num]; if(M == true) { open[open[PreviousFirstNode].node->middleNode->num].previous = &open[open[PreviousFirstNode].node->leftNode->num]; open[open[PreviousFirstNode].node->leftNode->num].next = &open[open[PreviousFirstNode].node->middleNode->num]; if(R == true) { open[open[PreviousFirstNode].node->rightNode->num].previous = &open[open[PreviousFirstNode].node->middleNode->num]; open[open[PreviousFirstNode].node->middleNode->num].next = &open[open[PreviousFirstNode].node->rightNode->num]; LastNode = open[PreviousFirstNode].node->rightNode->num; } else { LastNode = open[PreviousFirstNode].node->middleNode->num; } } else if(R == true) { open[open[PreviousFirstNode].node->leftNode->num].next = &open[open[PreviousFirstNode].node->rightNode->num]; open[open[PreviousFirstNode].node->rightNode->num].previous = &open[open[PreviousFirstNode].node->leftNode->num]; LastNode = open[PreviousFirstNode].node->rightNode->num; } else { LastNode = open[PreviousFirstNode].node->leftNode->num; } } else if(M == true) { open[open[PreviousFirstNode].node->middleNode->num].previous = &open[LastNode]; if(open[LastNode].previous != NULL) open[LastNode].next = &open[open[PreviousFirstNode].node->middleNode->num]; if(R == true) { open[open[PreviousFirstNode].node->rightNode->num].previous = &open[open[PreviousFirstNode].node->middleNode->num]; open[open[PreviousFirstNode].node->middleNode->num].next = &open[open[PreviousFirstNode].node->rightNode->num]; LastNode = open[PreviousFirstNode].node->rightNode->num; } else { LastNode = open[PreviousFirstNode].node->middleNode->num; } } else if(R == true) { open[open[PreviousFirstNode].node->rightNode->num].previous = &open[LastNode]; if(open[LastNode].previous != NULL) open[LastNode].next = &open[open[PreviousFirstNode].node->rightNode->num]; LastNode = open[PreviousFirstNode].node->rightNode->num; } } else break; } FindPath(open,FirstNode,FindNum); } void ascendingNode(Open* open, int* FirstNode, int* LastNode) { int temp[22] = {0,}; int nodeNum = 1; int tempNodeNum = *FirstNode; for(int i = 0; ; i++) { temp[i] = tempNodeNum; if(open[tempNodeNum].next != NULL) nodeNum++; else break; tempNodeNum = open[tempNodeNum].next->node->num; } for (int i = 0; i < nodeNum-1; i++) { for (int j = 0; j < nodeNum-1; j++) { if(open[temp[j]].next == NULL) continue; if (open[temp[j]].node->totalCost > open[temp[j+1]].node->totalCost) { temp[j] ^= temp[j+1] ^= temp[j] ^= temp[j+1]; } } } for (int i = 1; i < nodeNum-1; i++) { open[temp[i]].next = &open[temp[i+1]]; open[temp[i]].previous = &open[temp[i-1]]; } *FirstNode = temp[0]; *LastNode = temp[0+nodeNum-1]; open[temp[0]].next = &open[temp[1]]; open[temp[0]].previous = NULL; open[temp[0+nodeNum-1]].previous = &open[temp[0+nodeNum-2]]; open[temp[0+nodeNum-1]].next = NULL; } void FindPath(Open* open,int FirstNode, int FindNum) { int a = 0; printf("Found goal node!! The number of search : "); Set_Color_Console(CYAN); printf("%d \n",FindNum); Set_Color_Console(GREY); Set_Color_Console(YELLOW); while(1) { if(a++ == 0) { printf("%c",open[FirstNode].node->key); } else printf(" ← %c",open[FirstNode].node->key); if(open[FirstNode].node->parentNode == NULL) break; FirstNode = open[FirstNode].node->parentNode->num; } Set_Color_Console(GREY); printf("\n"); getch(); } void printOPEN_CLOSED(Open* open, Closed* closed, int FirstNode, int closeNum) { Set_Color_Console(GREEN); printf("OPEN List : "); Set_Color_Console(GREY); while(1) { if(open[FirstNode].node->parentNode != NULL) printf("%c(%d,%c) ",open[FirstNode].node->key,open[FirstNode].node->totalCost,open[FirstNode].node->parentNode->key); else printf("%c(%d,NULL) ",open[FirstNode].node->key,open[FirstNode].node->totalCost); if(open[FirstNode].next == NULL) break; else FirstNode = open[FirstNode].next->node->num; } printf("\n"); Set_Color_Console(GREEN); printf("CLOSED List : "); Set_Color_Console(GREY); for(int i = 1; i < closeNum; i++) { if(closed[i].node->parentNode != NULL) printf("%c(%d,%c) ",closed[i].node->key,closed[i].node->totalCost,closed[i].node->parentNode->key); else printf("%c(%d,NULL) ",closed[i].node->key,closed[i].node->totalCost); } printf("\n\n"); }

세 알고리즘의 장단점을 생각해보면..

BFS

   장점 : 깊이 우선 이므로 Level이 높은 목표 노드에 대해서 효율적인 알고리즘

   단점 : Level이 낮은 목표노드에 대해선 비효율적인 알고리즘

DFS

   장점 : 넓이 우선 이므로 Level이 낮은 목표 노드를 찾기에 효율적인 알고리즘

   단점 : Level이 높은 목표 노드에 대해선 비효율적인 알고리즘

UCS

   장점 : 경로 비용이 최소인 구간을 찾아 가기 때문에 여러 길이 있을 때 효율적인 알고리즘

   단점 : 이번 문제의 상태공간 그래프에서는 비효율적인 알고리즘