문제해결 : 해의 탐색
(Problem Solving : The Search for Solutions)
C 인공지능 프로그래밍 : Herbert Schildt 지음, 신경숙.류성렬 옮김, 세웅, 1991 (원서 : Artificial Intelligence using C, McGraw-Hill, 1987), page 29~91
1. 표현과 용어 (REPRESENTATION AND TERMINOLOGY)
2. 과도한 증가 (COMBINATION EXPLOSIONS)
4. 탐색 평가 (EVALUATION A SEARCH)
5. 깊이우선 탐색기법 (THE DEPTH-FIRST SEARCH TECHNIQUE)
(1) 깊이우선 탐색 평가하기 (Evaluating the Depth-First Search)
6. 너비우선 탐색기법 (THE BREATH-FIRST SEARCH TECHNIQUE)
(1) 너비우선 탐색평가 (Evaluating the Breadth-First Search)
7. 휴리스틱 부가 (ADDING HEURISTICS)
8. 언덕오르기 기법 (THE HILL CLIMBING SEARCH TECHNIQUE)
(1) 언덕오르기 탐색 평가 (Evaluating the Hill-Climbing Search)
9. 최소비용 탐색기법 (THE LEAST-COST SEARCH TECHNIQUE)
(1) 최소비용 탐색 평가 (Evaluating the Least-Cost Search)
10. 탐색기법 선택 (CHOOSING A SEARCH TECHNIQUE)
11. 복수 해 찾기 (FINDING MULTIPLE SOLUTIONS)
(1) 경로 제거 방법 (The Path-Removal Method)
(2) 노드 제거 방법 (The Node-Removal Method)
12. 최적해 찾기 (FINDING THE OPTIMAL SOLUTION)
13. 잃어 버린 열쇠로 돌아가서 (BACK TO THE MISSING KEYS)
문제해결은 대부분의 AI 응용에 기본이 된다. 사실상, 문제를 해결하는 능력은 종종 사람과 기계에 대한 지능의 측정 기준으로 사용된다. 주로 두가지 유형의 문제가 있다. 첫 번째 유형은 성공이 보장된 결정적 프로시저 (deterministic procedure) 를 사용함으로써 해결될 수 있다. 이 과정은 계산 (computation) 이라고 불린다. 계산에 의해 해결하는 것은 보통, 수학에서 처럼, 프로시저가 문제를 위하여 존재하는 그런 유형의 문제들에만 적용된다. 종종 이 문제들을 해결하기 위하여 사용되는 방법들을 컴퓨터가 수행할 수 있는 알고리즘으로 쉽게 바꿀 수 있다. 그러나, 계산적인 해결에 도움이 되는 실세계 문제는 거의 없기 때문에 그런 문제들은 해를 탐색함으로써 (searching for a solution) 해결하는 문제들로 구성된 두 번째 부류에 놓여야 한다. 이것이 AI 가 관계하는 문제해결 방법이다.
AI 기법을 실세계 문제에 적용하려고 할 때 극복하기 어려운 장애물 중의 하나는 대부분의 상황이 아주 크다는 것과 복잡하다는 것이다. AI 연구 초기에, 좋은 탐색방법을 개발하려는 필요와 요구에 의해 주요 목표가 되었다. 당시에 사용된 컴퓨터의 제약 때문에 프로그래머가 이러한 문제들을 해결하기 위하여 좋은 탐색 기법을 고안하는 것이 필요했다. 더욱이, 탐색이 지능의 주요 성분인 문제해결에 중심이 된다고 믿었고, 현재도 그렇게 믿기 때문에 프로그래머는 좋은 탐색 기법을 바란다.
자동차 열쇠 (key) 를 잃어 버렸다고 생각해보자. 그 열쇠들이 다음과 같이 집 어딘가에 있다는 것은 안다 :
X 는 현관에 서 있다는 것을 나타낸다. 탐색을 시작할 때 우선 거실을 점검한다. 그리고나서 복도를 따라 첫 번째 침실로 가고, 복도로 되돌아와서 두 번째 침실로 가고, 다시 복도로 되돌아와서 안방으로 간다. 아직 열쇠를 찾지 못했기 때문에, 거실로 되돌아와서 부엌으로 가고 거기에서 열쇠를 찾는다. 그림 1 에 따라간 경로에 대한 그래프를 제시한다.
그림 1 잃어 버린 열쇠를 찾는 패스 그래프
이러한 종류의 문제를 그래프로 표현할 수 있다는 사실은 다른 탐색 기법들이 어떻게 동작하는 지를 보여주는 간단한 방법을 제시하기 때문에 중요하다 (또한, 문제를 그래프로 표현할 수 있다는 것은 AI 연구가들에게 그래프 이론으로부터 여러 가지 정리를 적용할수 있게 한다. 그러나, 이것은 이 책의 범위를 넘는다). 이러한 사실을 염두에 두고, 다음 정의를 공부해 보자.
잃어 버린 열쇠 예제에서, 집의 각 방이 하나의 노드라고 생각해보자 ; 집 전체는 탐색공간이다 ; 목표는 부엌이다 ; 그리고 해의 경로는 그림 1 에 있는 그래프이다. 이 예제는 휴리스틱을 사용하지 않았지만, 이 장의 뒷부분에서 약간 보게 될 것이다.
이 시점에서, 해를 찾는 것이, 처음에 시작해서 결론까지 방법을 적용하는 것만큼 간단하다고 생각할 수 있다. 잃어 버린 열쇠의 아주 간단한 경우에 이 탐색 방법은 좋은 방법이다. 그런 문제를 해결하기 위하여 컴퓨터를 사용하기를 원하는 대부분의 문제에서, 상황은 달라진다. 일반적으로, 탐색공간에서 노드의 수가 매우 많고, 탐색공간이 커짐에 따라 목표까지의 서로 다른 경로의 수도 증가하는 그런 문제들을 해결하기 위하여 컴퓨터를 사용할 것이다. 문제는 탐색공간에 더해지는 각 노드에 하나 이상의 경로를 더해준다는 것이다 ; 즉, 목표까지 경로의 수는 각 새로운 노드에 대하여 더 빨리 증가할 것이다.
이러한 증가를 이해하기 위해서, 세 개의 대상물 (object) - A, B, C - 를 테이블 위에 배열하는 방법의 수를 생각해보자. 여섯가지 가능한 배열은 다음과 같다 :
A B C
A C B
B C A
B A C
C B A
C A B
비록 이것이 A, B, C 를 배열할 수 있는 모든 방법이라는 것을 증명할 수 있다하더라도, 사물이 결합되거나 배열되거나 또는 순열로 될 수 있는 방법의 연구인, 순열 (combinatorics) 이라고 하는 수학으로부터 정리를 사용하여 같은 수를 이끌어 낼 수 있다. 그 정리는 N 개의 대상물이 순열될수 있는 방법의 수는 N! (N factorial) 과 같다는 것이다. 한 숫자의 factorial 은 1부터 자신보다 작거나 같은 모든 정수들의 곱이다. 그러므로 3! 은 3 * 2 * 1 또는 6 이다. 이 정보가 주어져 있을 때, 배열할 4 개의 대상물을 가졌다면 4! 또는 24 개의 순열이 있다는 것을 알 수 있다. 5 개의 대상물에 대해서, 그 숫자는 120 이다. 6 개의 대상물에 대해서는 720 이다. 말하자면 1000 개의 대상물에 대해서 가능한 순열의 수는 매우 크다! 그림 2 는 AI 연구가들이 흔히 조합적 증가 (combinatoric explosion) 이라고 부르는 것을 보여준다. 약간의 가능성보다 좀 더 많으면, 모든 조합들은 빠른 속도로, 검토하기가 불가능하게 되고 실제로 나열하기 조차 불가능해 진다.
그림 2 factorial 로 폭발적으로 증가하는 그래프
조합적 증가 개념을 문제해결에 관련 지을 때, 탐색공간에 더해지는 부가적인 노드 각각은 1 보다 훨씬 더 큰 수 만큼, 가능한 해의 수를 증가시킨다. 그러므로, 어떤 지점에서, 너무 많은 가능성이 있기 때문에 계속할 수 없게 될 것이다. 가능성의 수는 아주 빨리 커지기 때문에 가장 간단한 문제조차도 소모적 탐색 (exhaustive search) 하게 한다 (소모적 탐색은 모든 노드를 검사한다). 소모적, 또는 강제적 (brute force) 기법은 이론상 항상 작동하지만, 너무 많은 시간, 너무 많은 계산 자원, 또는 둘 다를 소모하기 때문에 비실용적이다. 이 이유 때문에 다른 탐색 기법들이 개발되었다.
가능한 해를 찾기 위한 여러 가지 기법들이 있다. 다음에 있는 것들이 가장 중요하고 가장 흔하다 ;
이 장에서는 각 기법을 차례로 살펴본다.
탐색 기법의 성능을 평가하는 것은 매우 복잡할 수 있다. 사실상, 이 평가는 AI 연구의 큰 부분을 차지한다. 그러나 여기서의 토론을 위하여, 중요한 두 가지 기본 측정법이 있다.
1. 탐색이 해를 얼마나 빨리 찾는가?
2. 그 해가 얼마나 좋은가?
중요한 것은 최소의 노력으로 문제에 대한 해 - 어떤 해라도 - 를 찾는, 여러 가지 유형의 문제들이 있다. 이런 유형의 문제들에 대하여 첫 번째 측정법이 중요하다. 그러나, 다른 상황에서, 중요한 것은 그 해가 최적의 해에 얼마나 가까운가 하는 것이다.
해의 경로 길이와 방문된 노드의 실제 갯수가 탐색 속도를 결정한다. 막다른 곳으로부터의 백트래킹 (backtracking) 은 기본적으로 노력이 낭비됨을 기억해야 한다. 따라서 요구되는 것은 가능한 한 거의 백트랙하지 않는 탐색이다.
최적의 해를 발견하는 것과 좋은 해를 발견하는 것 사이의 차이를 이해하는 것은 중요하다. 최적의 (optimal) 해를 발견하는 것이 좋은 (good) 해가 발견되었는지 아닌지를 결정하는 유일한 방법일수 있기 때문에 종종 소모적 탐색을 수반한다는 사실에 차이가 있다. 그런 좋은 해를 발견하는 것은 더 나은 해가 존재하든 안하든 상관없이 일단의 제약조건 안에 있는 것을 발견하는 것을 의미한다.
이 장에서 설명된 모든 탐색 기법들은 어떤 특정 상황에서 다른 것들 보다 더 잘 작동할 것이다. 그러므로, 어는 정도로 한 가지 탐색 방법이 다른 것보다 항상 (always) 우수할 것인지 아닌지 말하는 것은 어렵다. 그런 몇가지 탐색 기법들은 평균적으로 더 낫다는 확률이 더 클 것이다. 또한, 문제가 정의되는 방법은 때때로 좋은 탐색 방법을 선택하는 데에 도움을 줄 것이다.
여러 가지 탐색 기법을 조사하기 전에, 그것을 해결하기 위하여 여러 가지 탐색을 사용할 문제가 다음에 있다. 여행사 직원이고 다소 성가신 고객이 뉴욕에서 로스앤젤리스행 XYZ 기를 예약하기를 원한다고 생각해보자. 비록 XYZ 는 뉴욕에서 로스앤젤리스로 직접 운항하는 비행기가 없다고 고객에게 말한다고 해도, 고객은 XYZ 기만 탈 것을 주장한다. XYZ 의 예정된 비행기를 보면 다음을 발견한다.
그림 3 XYZ 비행 스케쥴의 방향있는 그래프
|
1000 마일 1000 마일 800 마일 1900 마일 1500 마일 1800 마일 500 마일 1000 마일 1500 마일 1000 마일 |
연결 비행기를 이용하면 XYZ 로 뉴욕에서 로스앤젤리스까지 길이 있음을 빨리 알 수 있다. 따라서, 고객에게 비행기를 예약해준다. 그러나, 일은 훨씬 나은 방법으로 같은 일을 하는 C 프로그램을 작성하는 것이다.
XYZ 의 예정 명부에 있는 비행기 정보는 그림 3 에 있는 방향성 그래프로 변형될 수 있다. 방향성 그래프는 단순히 각 노드를 연결하는 선들의 움직임의 방향을 나타내는 화살표를 갖는 그래프이다. 방향성 그래프에서, 각 화살표화 반대 방향으로 여행하는 것은 불가능하다.
그림 4 XYZ 비행 스케쥴 트리
그러나 그림 4 에 있는 것처럼 그래프를 트리로 다시 그리면 비행기 정보는 이해하기가 더 쉽다. 이 장의 나머지에서는 이 버전 (version) 을 참조한다. 그림 4 에서 목표 로스앤젤리스는 원으로 표시되어 있고, 여러 도시들은 그 구성을 간단히 하기 위하여 트리에 한번 이상 나타냈다. 이제 뉴욕에서 로스앤젤리스까지 경로를 찾을 여러 가지 탐색 프로그램을 개발할 준비가 되어있다.
깊이우선 탐색 (depth-first search) 은 다른 경로를 시도하기 전에 결론 (또는 목표) 까지 각 가능한 경로를 찾는다. 이 탐색이 어떻게 동작하는지 정확히 이해하기 위하여 F 가 목표인 다음 트리를 생각해보자 :
깊이우선 탐색은 이 그래프를 ABDBEBACF 순으로 방문할 것이다. 만약 트리에 익숙하다면, 이런 유형의 탐색을 트리의 중이 순회 (inorder tree traversal) 와 기본적으로 같다는 것을 알 것이다. 이런 유형의 순회에서, 종단노드나 목표에 도달할 때 까지 왼쪽으로 간다. 종단 노드에 도착하면 한 수준 되돌아 가고 오른쪽으로 가서 목표나 종단노드를 만날 때 까지 왼쪽을 간다. 목표를 발견하거나 탐색 공간의 마지막 노드를 조사할 때까지 반복한다. 깊이우선 탐색은 최악의 경우에, G 가 목표일 경우에 해당될, 소모적 탐색으로 퇴보하기 때문에, 반드시 목표를 찾는다.
뉴욕에서 로스앤젤리스까지의 경로를 결정하는 C 프로그램을 작성하려면 XYZ 비행기에 대한 정보를 포함하는 데이터베이스를 사용해야 한다. 데이터베이스의 엔트리는 출발도시와 도착도시, 그 사이의 거리, 그리고 백트래킹에 도움을 줄 플래그를 포함할 것이고 이를 간단히 살펴본다. 정보를 유지할 구조가 다음에 있다.
|
#define MAX 100 /* structure of the flight database (db) */ struct FL { char from[20]; char to[20]; int distance; char skip; /* used in backtracking */ }; struct FL flight[MAX]; /* array of db structures */ int f_pos=0; /* number of entries in flight db */ int find_pos=0; /* index for searching flight db */ |
엔트리들은 flight 데이터베이스에 assert_flight() 을 이용하여 놓여진다. 그리고 setup() 은 정보를 초기화하기 위하여 사용된다. 전역변수 f_pos 는 데이터베이스에서 마지막 항목의 인덱스를 유지한다. 이 루틴들이 다음에 있다.
|
setup() { assert_flight("New York", "Chicago", 1000); assert_flight("Chicago", "Denver", 1000); assert_flight("New York", "Toronto", 800); assert_flight("New York", "Denver", 1900); assert_flight("Toronto", "Calgary", 1500); assert_flight("Toronto", "Los Angeles", 1800); assert_flight("Toronto", "Chicago", 500); assert_flight("Denver", "Urbana", 1000); assert_flight("Denver", "Houston", 1500); assert_flight("Houston", "Los Angeles", 1500); assert_flight("Denver", "Los Angeles", 1000); } /* place facts into flight db */ assert_flight(from, to. dist) char *from, *to; int dist; { if (f_pos<MAX) { strcpy(flight[f_pos].from, from); strcpy(flight[f_pos].to, to); flight[f_pos].distance=dist; flight[f_pos].skip=0; f_pos++; } else printf("flight database full. ＼n"); } |
AI 개념과 일치하기 위해서 데이터베이스를 사실 (facts) 을 포함하는 것으로 생각해야 한다. 이 절에서 개발할 프로그램은 해에 도달하기 위하여 이 사실들을 사용할 것이다. 데이터베이스가 사실을 포함하기 때문에, 많은 AI 연구가들은 데이터베이스을 지식베이스 (knowledge base) 라 일컫는다 ; 이 책은 두 용어를 혼용해서 사용한다.
뉴욕과 로스앤젤리스 사이의 경로를 찾기 위하여 실제 코드를 작성하기 전에, 여러개의 지원 함수를 필요로 한다. 우선, 두 도시 사이에 비행기가 있는지 결정할 수 있는 루틴이 필요하다. 이 함수를 match() 라 부른다 ; 그런 비행기가 없으면 0 을 리턴하고, 있으면 두 도시 사이의 거리를 리턴한다.
|
/* if connection between from and to, then return the distance fo flight ; if not, return 0 */ match(from, to) char *from, *to; { register int t; for (t=f_pos-1; t>-1; t--) if (!strcmp(flight[t].from, from) && !strcmp(flight[t].to, to)) return flight[t].distance; return 0; /* not found */ } |
필요한 다음 루틴은 find() 이다. 한 도시가 주어졌을 때, find() 는 데이터베이스에서 연결 비행기를 찾는다. find() 가 연결 비행기를 발견하면 도착 도시의 이름과 거리를 리턴한다. 만약 발견하지 못하면 0 을 리턴한다. find() 루틴이 다음에 있다 ;
|
/* given from, find anywhere */ find(from, anywhere) char *from, *anywhere; { find_pos=0; while (find_pos<f_pos) { if (!strcmp(flight[find_pos].from, from) && !flight[find_pos].skip) { strcpy(anywhere, flight[find_pos].to); flight[find_pos].skip=1; /* make active */ return flight[find_pos].distance; } find_pos++; } return 0; } |
find() 를 조사해보면 skip 필드를 1 로 지정한 도시들은 유효한 연계가 아니라는 것을 안다. 또한 find() 가 연결 비행기를 찾으면, 연결의 skip 필드를 active 로 표시한다. 이 단계는 막다른 곳으로부터 백트래킹을 제어하기 위하여 사용된다.
제 1 장에서 언급했듯이, 백트래킹은 많은 AI 기법에서 결정적인 성분이다. 되부름 루틴과 백트랙 스택을 사용하여 백트래킹을 만들 수 있다. 가상적으로 모든 백트래킹 상황은 연산에서 스택과 유사하다 - 즉, 그 상황들은 먼저 들어간 것이 나중에 나온다. 그러므로, 탐색이 경로를 찾아갈 때, 노드를 만나면 그 노드들을 스택에 넣는다. 각 막다른 곳에서, 탐색은 스택에서 마지막 노드를 꺼내고 그 점에서부터 새로운 경로를 시도한다. 이 과정은 탐색이 목표에 도달하거나 모든 경로를 다 거칠 때 까지 계속된다. 함수 push() 와 pop() 이 다음에 있다. 그 함수들은 top-of-stack 포인터 스택 배열을 저장하기 위하여 각각 전역변수 tos 와 bt_stack 을 사용한다.
|
/* stack routines */ push(from, to, dist) char *from, *to; int dist; { if (tos<MAX) { strcpy(bt_stack[tos].from, from); strcpy(bt_stack[tos].to, to); bt_stack[tos].dist=dist; tos++; } else printf("stack full. ＼n"); } pop(from, to, dist) char *from, *to; int *dist; { if (tos>0) { tos--; strcpy(from, bt_stack[tos].from); strcpy(to, bt_stack[tos].to); *dist=bt_stack[tos].dist; } else printf("stack underflow. ＼n"); } |
요구된 지원 루틴들이 모두 개발되었으므로, isflight() 라고 하는 주요 루틴을 다음에 제시한다. 이 루틴은 뉴욕과 로스앤젤리스 사이의 경로를 찾을 수 있게 해준다.
|
/* determine if there is a route between from and to */ isflight(from, to) char *from, *to; { int d, dist; char anywhere[20]; /* see if destination is reached */ if (d=match(from, to)) { push(from, to, d); return; } /* try another connection */ if (dist=find(from, anywhere)) { push(from, to, dist); isflight(anywhere, to); } else if (tos>0) { /* backtrack */ pop(from, to, &dist); isflight(from, to); } } |
isflight() 루틴이 다음과 같이 작동된다 : 먼저, match() 는 from 과 to 사이에 비행기가 있는지를 알기 위해서 데이터베이스를 체크한다. 만약 있으면, 그 루틴은 목표에 도달했다 ; 그러면 루틴은 이 연결을 스택에 넣고 함수는 리턴된다. 비행기가 없으면, find() 는 from 이 그 밖의 다른 곳 사이의 연결이 있는지 보기 위하여 체크한다. 만약 있으면, 루틴은 이 연결을 스택에 넣고 isflight() 를 되부름 방식으로 호출한다. 연결 비행기가 없으면, 백트래킹이 발생한다. 루틴은 스택으로부터 앞 노드를 제거하고 isflight() 를 되부름 방식으로 호출한다. 이 과정은 루틴이 목표를 발견할 때까지 계속한다. skip 필드는 루틴으로 하여금 같은 연결을 여러번 반복해서 시도하는 것을 막기 위한 백트래킹에 필요하다.
그 루틴이 덴버와 휴스톤을 갖고 호출되면, 루틴의 첫 부분은 성공하고 isflight() 는 끝날 것이다. 그러나, 만약 시카고와 휴스턴을 갖고 호출되면 이 두 도시 사이에 직행 비행기가 없기 때문에 첫 부분은 실패할 것이다 ; 그러므로, 루틴은 시작 도시와 다른 도시 사이의 연결 비행기를 발견하려고 시도함으로써 두 번째 부분을 시도한다. 이 경우에, 시카고와 덴버 사이에 연결 비행기가 있다 ; 그러므로, 그리고나서 루틴은 덴버와 휴스톤을 가지고 isflight() 를 되부름 방식으로 호출한다. 루틴은 다시 첫 번째 조건을 테스트하지만 이번에는 연결을 발견한다. 마지막으로, 되부름 호출은 원래대로 되돌아오고 isflight() 는 끝난다. isflight() 가 지식 베이스의 깊이우선 탐색을 수행할 것이라는 것을 스스로 증명해보자.
isflight() 는 실제로 해를 리턴하는 것이 아니라는 것을 이해하는 것이 중요하다. 해를 생성하는 것이다. 요점은 isflight() 에서 빠져나갈 때 백트랙 스택은 시카고와 휴스톤 사이의 경로를 포함한다는 (the backtrack stack contains the route Chicago and Houston) 것이다. 스택의 상태는 isflight() 의 성공 또는 실패를 나타낸다. 그러므로 전체 프로그램을 완성하는 데에 요구되는 최종 함수는 route() 라고 불린다. 따라갈 경로와 총 거리를 프린트한다.
|
/* show the route and distance */ route(to) char *to; { int dist, t; dist=0; t=0; while(t<tos) { printf("%s to", bt_stack[t].from); dist+=bt_stack[t].dist; t++; } printf("%s ＼n", to); printf("distance is %d＼n", dist); } |
깊이우선 탐색 프로그램 전체가 다음에 있다.
|
/* depth-first search */ #include "stdio.h" #define MAX 100 /* structure of the flight database (db) */ struct FL { char from[20]; char to[20]; int distance; char skip; /* used in backtracking */ }; struct FL flight[MAX]; /* array of db structures */ int f_pos=0; /* number of entries in flight db */ int find_pos=0; /* index for searching flight db */
int tos=0; /* top of stack */ struct stack { char from[20]; char to[20]; int dist; }; struct stack bt_stack[MAX]; /* backtrack stack */
main() { char from[20], to[20]; setup(); printf("from ? "); gets(from); printf("to ? "); gets(to); isflight(from, to); route(to); }
setup() { assert_flight("New York", "Chicago", 1000); assert_flight("Chicago", "Denver", 1000); assert_flight("New York", "Toronto", 800); assert_flight("New York", "Denver", 1900); assert_flight("Toronto", "Calgary", 1500); assert_flight("Toronto", "Los Angeles", 1800); assert_flight("Toronto", "Chicago", 500); assert_flight("Denver", "Urbana", 1000); assert_flight("Denver", "Houston", 1500); assert_flight("Houston", "Los Angeles", 1500); assert_flight("Denver", "Los Angeles", 1000); } /* place facts into flight db */ assert_flight(from, to. dist) char *from, *to; int dist; { if (f_pos<MAX) { strcpy(flight[f_pos].from, from); strcpy(flight[f_pos].to, to); flight[f_pos].distance=dist; flight[f_pos].skip=0; f_pos++; } else printf("flight database full. ＼n"); }
/* show the route and distance */ route(to) char *to; { int dist, t; dist=0; t=0; while(t<tos) { printf("%s to", bt_stack[t].from); dist+=bt_stack[t].dist; t++; } printf("%s ＼n", to); printf("distance is %d＼n", dist); }
/* if connection between from and to, then return the distance fo flight ; if not, return 0 */ match(from, to) char *from, *to; { register int t; for (t=f_pos-1; t>-1; t--) if (!strcmp(flight[t].from, from) && !strcmp(flight[t].to, to)) return flight[t].distance; return 0; /* not found */ }
/* given from, find anywhere */ find(from, anywhere) char *from, *anywhere; { find_pos=0; while (find_pos<f_pos) { if (!strcmp(flight[find_pos].from, from) && !flight[find_pos].skip) { strcpy(anywhere, flight[find_pos].to); flight[find_pos].skip=1; /* make active */ return flight[find_pos].distance; } find_pos++; } return 0; }
/* determine if there is a route between from and to */ isflight(from, to) char *from, *to; { int d, dist; char anywhere[20]; /* see if destination is reached */ if (d=match(from, to)) { push(from, to, d); return; } /* try another connection */ if (dist=find(from, anywhere)) { push(from, to, dist); isflight(anywhere, to); } else if (tos>0) { /* backtrack */ pop(from, to, &dist); isflight(from, to); } }
/* stack routines */ push(from, to, dist) char *from, *to; int dist; { if (tos<MAX) { strcpy(bt_stack[tos].from, from); strcpy(bt_stack[tos].to, to); bt_stack[tos].dist=dist; tos++; } else printf("stack full. ＼n"); } pop(from, to, dist) char *from, *to; int *dist; { if (tos>0) { tos--; strcpy(from, bt_stack[tos].from); strcpy(to, bt_stack[tos].to); *dist=bt_stack[tos].dist; } else printf("stack underflow. ＼n"); } |
main() 은 출발도시와 도착도시를 프롬프트로 내보냄을 주목해야 한다. 이것은 어떤 두 도시 사이의 경로도 찾기 위하여 프로그램을 사용하게 한다. 그러나, 이 장의 나머지에서는 뉴욕이 출발지이고 로스앤젤리스가 도착지라고 가정한다.
이제 프로그램으로 들어가서 컴파일해야 한다. 마이크로소프트 C 버전 4 를 포함하여 어떤 컴파일러에 대해서, 스택에 할당되는 메모리의 양을 증가시킬 필요가 있을 것이다. 왜냐하면 루틴들이 어떤 해들에 대하여 되부름 특성이 아주 크기 때문이다.
그림 5 해를 찾기 위한 깊이우선 탐색
뉴욕과 로스앤젤리스를 가지고 프로그램을 수행할 때 해는 다음과 같다.
|
New York to Chicage to Denver to Los Angeles distance is 3000 |
그림 4 를 참조하면, 이것이 깊이우선 탐색을 사용하여 발견한 최초의 해라는 것을 알게 될 것이다. 최적의 해는 아니지만 나쁘지는 않다. 최적의 해는 거리가 2600 마일인, 뉴욕에서 토론토, 로스앤젤리스 까지이다. 그림 5 는 탐색 경로를 보여준다.
방금 주어진 예에서, 깊이우선 접근방식은 백트래킹이 전혀 없이 최초의 시도에서 아주 좋은 해를 발견했다 - 이것은 아주 좋다. 그러나, 최적의 해에 도달하기 위하여 거의 모든 노드들을 방문했어야 할 것인데 이것은 아주 좋지가 않다.
그러나, 단순히 끝에 해가 없다는 것을 발견하기 위하여 특히 긴 가지를 탐색해야 하는 그런 상황에서 깊이우선은 아주 나쁠수 있다는 것을 알아야 한다. 이 경우에, 이 체인의 탐색에서 뿐만 아니라 목표까지의 백트래킹에서도 깊이우선은 상당한 시간을 낭비할 것이다. 이와같은 상황은 너비우선 탐색을 필요로 한다.
너비우선 탐색은 깊이우선 탐색의 반대이다. 너비우선 탐색은 다음의 더 깊은 수준으로 진행하기 전에 같은 수준에서 각 노드를 체크한다. 목표로 C 를 갖는 이 탐색방법이 다음에 있다.
이 예는 탐색이 노드 ABC 를 방문함을 보인다. 깊이우선 탐색처럼, 너비우선 탐색은 결국은 소모적 탐색으로 퇴보할 것이기 때문에 해가 존재하면 반드시 발견한다.
앞 절에 주어진 경로 찾기 프로그램이 너비우선 탐색만 수행하도록 그것을 변경하려면, 아래에 있는 것처럼 isflight() 프로시저를 변형해야 한다.
|
isflight(from, to) char *from, *to; { int d, temp, dist; char anywhere[20]; while (dist=find(from, anywhere)) { /* breadth-first modification */ if (d=match(anywhere, to)) { push(from, to, dist); push(anywhere, to, d); return; } } /* try an connection */ if (dist=find(from, anywhere)) { push(from, to, dist); isflight(anywhere, to); } else if (tos>0) { pop(from, to, &dist); isflight(from, to); } } |
보는 바와 같이 첫 번째 조건만이 변경되었다. 이제, 프로그램은 도착 도시와 연결되는지 알기 위하여 출발도시에 연결되는 모든 도시를 체크한다. 이제 프로그램에서 isflight() 의 이 버전을 대치해야 한다. 이 프로그램을 수행할 때, 해는 다음과 같다. 이것은 최적의 해이다.
|
New York to Chicage to Denver to Los Angeles distance is 3000 |
그림 6 은 해까지의 너비우선 탐색경로를 보여준다.
그림 6 해를 찾기 위한 너비우선 탐색
방금 주어진 예에서, 너비우선 탐색은 백트래킹 없이 해를 발견함으로써 잘 수행했다. 이것은 또한 최적의 해이다. 사실상, 발견될 처음 3 개의 해는 가장 좋은 3 개의 경로이다. 그러나, 이 결과는 컴퓨터에 저장된 것과 같은, 정보의 물리적인 구조에 의존하기 때문에 다른 상황에 적용하기 위하여 그것을 일반화시킬 수 없음을 기억해야 한다. 그러나, 이 결과는 깊이우선과 너비우선이 얼마나 근본적으로 다른지를 설명해 준다.
여러 층 깊이 위치된 목표를 찾으려 할 때 너비우선 탐색의 단점을 알게 될 것이다. 이 경우에, 너비우선은 그것을 찾기 위하여 상당한 노력을 들인다. 일반적으로, 프로그래머는 목표가 가장 있기 쉬운 곳에 관하여 추측을 함으로써 깊이우선 탐색과 너비우선 탐색 사이에서 선택한다.
지금까지 아마 깊이우선과 너비우선 탐색 루틴들이 블라인드 (blind) 라고 생각해왔다. 그 루틴들은 "교육받은 추측" 을 사용하지 않고 한 목표에서 다른 목표로 이동하는 것에만 의존하여 해를 찾는다. 이 과정은, 프로그래머로서 다른 방법에 대하여 한가지 방법을 사용하도록 알려주는 정보를 갖고 있는, 그런 제한된 상황에 대해서는 좋지만, 일반화된 AI 프로그램이 필요로 하는 것은 평균적으로 이 두 기법 중 우수한 탐색 프로시저이다. 그러한 탐색을 이루는 유일한 방법은 경험 기능 (heuristic capabilities) 을 부가하는 것이다.
휴리스틱 (Heuristic) 은 단순히 탐색이 올바른 방향으로 진행할 가능성을 적합하게 하는 규칙이다. 이를 이해하기 위해서, 숲속에서 길을 잃었고 물이 필요하다고 생각해보자. 숲이 너무 우거져서 너무 멀리 볼 수가 없고 나무가 너무 커서 둘러보기 위하여 올라갈 수도 없다. 그러나, 네가지 지식이 있다 ; 먼저, 강, 시내 그리고 못이 계곡에 있기가 가장 쉽다 ; 두 번째로, 동물들이 빈번히 물마시는 곳까지 길을 만든다 ; 세 번째로, 물 가까이 있을 때, 그것을 "알아내는" 것이 가능하다 ; 그리고 네 번째로, 물 흐르는 소리를 들을 수가 있다. 따라서, 물있는 곳으로의 길을 발견할 때, 물은 언덕 위에 있을 가능성은 없으므로 언덕 아래로 먼저 내려간다. 다음, 역시 언덕 아래로 달리는 사슴 꼬리를 우연히 발견하면, 물 있는 곳으로 인도할 수도 있기 때문에 사슴을 따라간다. 그리고나서 왼쪽에서 약간의 소란스런 소리를 듣는다. 이것이 물일 수도 있다는 것을 알면 그 방향으로 주의깊게 움직인다. 움직임에 따라 공기 중에서 습기가 많아짐을 발견한다 - 물의 "냄새" 를 맏을 수 있다. 마지막으로, 시내를 발견하고 물을 마신다. 이 예가 보여주듯이, 비록 부정확하고 보장되지 않은 것이지만 경험적 정보는 탐색 방법이 재빨리, 적절하게 목표를 찾을 기회를 증가시킨다. 즉, 빠른 성공의 가능성을 증가시킨다.
특별한 응용을 위하여 설계된 프로그램에 경험적 정보를 쉽게 포함할 수 있지만, 일반화된 경험적 탐색을 만드는 것은 불가능하다고 생각할지도 모른다. 그러나, 알다시피 이것은 그렇지가 않다.
아주 종종 경험적 탐색 방법들은 문제의 어떤 면을 최대화하거나 최소화하는 데에 기초를 둔다. 사실상 검토할 두 가지 경험적 접근방법은 반대 경험을 사용하고, 다른 결과를 낸다. 이 두 접근방식은 기본적인 깊이우선 탐색 루틴에 기초한다.
앞에서 본 뉴욕에서 로스앤젤리스까지 비행기를 예약하는 문제에서, 승객이 최소화하길 바라는 두가지 가능한 제약조건이 있다. 첫째는 만들어져야 하는 연결의 수이다. 두 번째는 경로의 길이이다. 가장 짧은 경로가 반드시 가장 적은 수의 연결을 원하는 것은 아님을 기억하여야 한다. 첫 번째 해로서 연결의 수를 최소화하는 것을 발견하려고 시도하는 탐색 알고리즘은, 고려된 거리가 길수록 목적지에 더 가까이 놓일, 그것에 의해서 연결의 수가 줄어들 가능성이 더 커진다고 하는 경험을 사용한다. AI 에서, 이런 유형의 탐색 방법을 언덕 오르기 (hill-climbing) 라고 부른다.
공식적으로, 언덕오르기 알고리즘은 다음 단계로서 목표에 가장 가깝게 놓일 것같은 노드를 선택한다. 알고리즘은 산을 반쯤 올라가서 어둠속에서 길을 잃은 도보여행자의 유추에서 그 이름을 따왔다. 도보여행자의 캠프가 산의 정상에 있다고 가정하면, 어둠 속에서조차, 여행자는 위로 올라가는 각 단계가 올바른 방향으로 가는 단계임을 안다.
비행기 예약 문제에 대하여, 지식베이스에 있는 정보만을 가지고 진행하면서 경로 배정 프로그램에 다음의 언덕오르기 경험을 통합할 수 있다 : 목적지에 더 가까울 것이라는 희망에서, 가능한한 현재 위치에서 먼 연결 비행기를 선택해보자. 이를 위해서 아래와 같이 find() 루틴을 변형해야 한다.
|
/* given from, find anywhere farthest away */ find(from, anywhere) char *from, *anywhere; { int pos, dist; pos=dist=0; find_pos=0; while (find_pos<f_pos) { if (!strcmp(flight[find_pos].from, from) && !flight[find_pos].skip) { if (flight[find_pos].distance>dist) { pos=find_pos; dist=flight[find_pos].distance; } } find_pos++; } if (pos) { strcpy(anywhere, flight[pos].to); flight[pos].skip=1; return flight[pos].distance; } return 0; } |
find() 루틴은 이제 출발 도시로부터 가장 먼 연결을 찾기 위하여 전체 데이터베이스를 탐색한다. 언덕오르기 프로그램 전체가 아래에 있다. 이번에는 컴퓨터에서 이 프로그램으로 들어가야 한다.
|
/* Hill - climbing */ #include "stdio.h" #define MAX 100 /* structure of the flight database (db) */ struct FL { char from[20]; char to[20]; int distance; char skip; /* used for backtracking */ }; struct FL flight[MAX]; /* array of db structures */ int f_pos=0; /* number of entries in flight db */ int find_pos=0; /* index for searching flight db */
int tos=0; /* top of stack */ struct stack { char from[20]; char to[20]; int dist; }; struct stack bt_stack[MAX]; /* backtrack stack */
main() { char from[20], to[20]; setup(); printf("from ? "); gets(from); printf("to ? "); gets(to); isflight(from, to); route(to); }
setup() { assert_flight("New York", "Chicago", 1000); assert_flight("Chicago", "Denver", 1000); assert_flight("New York", "Toronto", 800); assert_flight("New York", "Denver", 1900); assert_flight("Toronto", "Calgary", 1500); assert_flight("Toronto", "Los Angeles", 1800); assert_flight("Toronto", "Chicago", 500); assert_flight("Denver", "Urbana", 1000); assert_flight("Denver", "Houston", 1500); assert_flight("Houston", "Los Angeles", 1500); assert_flight("Denver", "Los Angeles", 1000); } /* place facts into flight db */ assert_flight(from, to. dist) char *from, *to; int dist; { if (f_pos<MAX) { strcpy(flight[f_pos].from, from); strcpy(flight[f_pos].to, to); flight[f_pos].distance=dist; flight[f_pos].skip=0; f_pos++; } else printf("flight database full. ＼n"); }
/* show the route and distance */ route(to) char *to; { int dist, t; dist=0; t=0; while(t<tos) { printf("%s to", bt_stack[t].from); dist+=bt_stack[t].dist; t++; } printf("%s ＼n", to); printf("distance is %d＼n", dist); }
/* if connection between from and to, then return the distance fo flight ; if not, return 0 */ match(from, to) char *from, *to; { register int t; for (t=f_pos-1; t>-1; t--) if (!strcmp(flight[t].from, from) && !strcmp(flight[t].to, to)) return flight[t].distance; return 0; /* not found */ }
/* given from, find anywhere farthest away */ find(from, anywhere) char *from, *anywhere; { int pos, dist; pos=dist=0; find_pos=0; while (find_pos<f_pos) { if (!strcmp(flight[find_pos].from, from) && !flight[find_pos].skip) { if (flight[find_pos].distance>dist) { pos=find_pos; dist=flight[find_pos].distance; } } find_pos++; } if (pos) { strcpy(anywhere, flight[pos].to); flight[pos].skip=1; return flight[pos].distance; } return 0; }
/* determine if there is a route between from and to */ isflight(from, to) char *from, *to; { int d, temp, dist; char anywhere[20];
if (d=match(from, to)) { /* is goal */ push(from, to, d); return; } /* find any connection */ if (dist=find(from, anywhere)) { push(from, to, dist); isflight(anywhere, to); } else if (tos>0) { pop(from, to, &dist); isflight(from, to); } }
/* stack routines */ push(from, to, dist) char *from, *to; int dist; { if (tos<MAX) { strcpy(bt_stack[tos].from, from); strcpy(bt_stack[tos].to, to); bt_stack[tos].dist=dist; tos++; } else printf("stack full. ＼n"); } pop(from, to, dist) char *from, *to; int *dist; { if (tos>0) { tos--; strcpy(from, bt_stack[tos].from); strcpy(to, bt_stack[tos].to); *dist=bt_stack[tos].dist; } else printf("stack underflow. ＼n"); } |
프로그램을 수행시킬 때 발견된 해는 다음과 같다.
|
New York to Denver to Los Angeles distance is 2900 |
이 결과는 아주 좋다! 도중에 최소의 정지 횟수 - 단 한번 - 를 갖는다. 그리고 가장 짧은 경로에 아주 가깝다. 더우기, 많은 백트래킹을 통한 낭비되는 시간이나 노력없이 이를 한다.
그러나 덴버에서 로스앤젤리스 까지의 연결이 존재하지 않으면 이 탐색은 좋지 않을 것이다. 사실상, 해는 4900 마일의 거리에 이르는 뉴욕, 덴버, 휴스톤, 로스앤젤리스가 될 것이다. 이 해는 휴스톤까지의 경로가 로스앤젤리스라는 목표에 더 근접시키지 않기 때문에 잘못된 정상에 오른다. 그림 7 은 해를 보이고 잘못된 정상으로의 경로를 보여준다.
그림 7 해와 잘못된 정상을 찾기위한 언덕오르기 경로
많은 상황에서, 언덕오르기 탐색은 해에 도달하기 전에 방문될 필요가 있는 노드의 수를 줄이려는 경향이 있기 때문에 아주 좋다. 첫째는 예에 있는 것처럼 잘못된 언덕을 오르는 문제이다. 이 경우에, 해를 찾기 위하여 탐색은 지나치게 백트랙한다. 두 번째는 "고원 (plateaus)" 문제이다. 여기서 모든 다음 단계들은 똑같이 좋아보인다 (또는 나빠보인다). 이 경우에, 언덕오르기는 깊이 우선 탐색과 마찬가지이다. 세 번째는 "산등성이 (ridges)" 문제이다. 이 경우에, 언덕오르기는 효과적이지 못한데, 왜냐하면 알고리즘이 백트래킹하는 동안 산등성이가 여러번 교차되게 할 것이기 때문이다. 이러한 잠재적인 문제에도 불구하고, 언덕오르기는 일반적으로, 경험을 사용하지 않는 어떤 방법보다도 더 빨리 최적의 해를 생성한다.
언덕오르기 탐색의 반대가 최소비용 탐색이다. 이 기법을 롤러 스케이트를 신고 큰 언덕의 길 중간에 서 있는 것과 비슷하다고 생각해 보자 : 위로 가는 것보다 아래로 내려가는 것이 훨씬 더 쉽다는 정확한 느낌을 갖는다! 그러므로, 최소비용은 최소의 노력이 드는 경로를 택한다.
비행기 예약 문제에 최소비용 탐색을 적용하는 것은, 발견된 경로가 가장 짧은 거리를 갖는 좋은 기회를 갖도록 프로그램이 모든 경우에 가장 짧은 연결 비행기를 택할 것이라는 것을 의미한다. 연결의 수를 최소화하는 언덕오르기 탐색과는 달리, 최소비용은 여행할 마일수를 최소화한다.
최소비용을 사용하기 위해서, 아래처럼 다시 find() 를 변경해야 한다.
|
/* find closest anywhere */ find(from, anywhere) char *from, *anywhere; { int pos, dist; pos=0; dist=32000; /* larger than the longest route */ find_pos=0; while (find_pos<f_pos) { if (!strcmp(flight[find_pos].from, from) && !flight[find_pos].skip) { if (flight[find_pos].distance>dist) { pos=find_pos; dist=flight[find_pos].distance; } } find_pos++; } if (pos) { strcpy(anywhere, flight[pos].to); flight[pos].skip=1; return flight[pos].distance; } return 0; } |
보는 바와 같이, find() 의 이 버전과 언덕오르기 탐색에서 사용된 버전과의 유일한 변화는 이 버전이 매번 가장 짧은 연결 비행기를 발견한다는 것이다. find() 의 이 버전을 가지고, 해는 다음과 같다.
|
New York to Toronto to Los Angeles distance is 2600 |
이것은 최소비용 방법이 가장 짧은 경로를 발견했음을 보여준다. 그림 8 은 해까지 최소비용 탐색의 경로를 보여준다.
그림 8 해를 찾기위한 최소비용 경로
최소비용 탐색은 순서가 뒤바뀐 것만 제외하고, 언덕오르기 탐색과 같은 장점 단점을 갖는다. 잘못된 계곡, 저지 (lowland), 골짜기가 있을 수 있다 ; 그러나 전반적으로 최소비용 탐색은 아주 잘 작동하려는 경향이 있다. 그러나 이 특별한 문제에 대하여 언덕오르기 보다 더 잘 수행했다고 해서 일반적으로 더 좋다고 생각하지는 말아야 한다. 평균적으로 blind 탐색의 성능을 능가할 것이라고만 말할 수 있다.
경험적 기법은 blind 탐색보다 더 잘 동작하려는 경향이 있다. 그러나, 다음 노드가 목표까지의 경로에 있을 가능성을 줄 충분한 정보가 없을 수도 있기 때문에 경험적 탐색을 이용할수 있는 문제들에 대해서, 그리고 두 번째는 이용할 수 없는 문제들에 대해서 문제에 경험을 적용할 수 없다면 깊이우선 탐색이 일반적으로 가장 좋기 때문에 그것을 선택해야 한다. 이 규칙의 유일한 예외는, 너비우선 탐색이 더 잘 작동할 것이라고 알려주는 정보를 갖게 되는 상황이다.
언덕오르기와 최소비용 사이의 선택은 어떤 제약조건을 최소화하거나 최대화하려고 하는데에 의존한다. 일반적으로, 언덕오르기 탐색은 방문될 노드의 수가 최소인 해를 생성하는 반면, 최소비용 탐색은 최소의 노력을 요구하는 경로를 찾는다.
만약 최적에 가까운 해를 찾고 있지만 소모적 탐색을 적용할수 없다면, 각 탐색 기법을 시도해서 가장 좋은 해를 찾아야 한다. 탐색은 실제로 다른 방법으로 작동하고, 그러므로 통계적으로 하나가 다른 것들보다 더 나은 결과를 내야 하기 때문에 이 방법은 효과적이다.
때때로, 같은 문제에 대한 여러개의 해를 발견해야 한다. 그러나 소모적 탐색에서 발생하는, 모든 해를 찾는 것과 같지는 않다. 예를들어, "꿈의 집 (dream house)" 을 설계하려 한다고 생각해보자 : 가장 좋아하는 것을 발견하기 위해 각 층의 계획을 여러 개 스케치한다 ; 모든 (all) 가능한 집들을 스케치하지는 않는다. 그러므로, 여러개의 해는 상황에 대한 가장 좋은 해를 발견하는 것을 돕기 위하여 여러 가지 옵션을 제시할수 있다.
복수의 해를 생성하는 많은 방법이 있지만, 여기서는 두 가지만 검토된다 : 경로제거와 노드제거 (path-removal and node-removal), 이 방법들의 이름이 의미하듯이, 군더더기 없이 복수의 해를 생성하는 것은 발견하는 해를 시스템으로부터 제거할 것을 요구한다. 이 방법 중 아무것도 모든 해를 발견하려고 시도하지 않는다 (또는 사용될 수도 없다) 는 것을 확실히 기억해야 한다. 모든 해를 발견하는 것은 다른 문제이고 소모적인 탐색을 의미하기 때문에 일반적으로 행해지지 않는다.
복수 해를 생성하는 경로 제거 방법은 현재의 구성하는, 그리고나서 또 다른 해를 찾으려고 시도하는 모든 노드들을 데이터베이스로부터 제거한다. 본질적으로, 경로 제거 방법은 트리에서 가지를 자른다.
경로 제거 방법을 가지고 복수 해를 발견하기 위하여 아래에 있는 것처럼 깊이우선 탐색에서 main() 을 변경하는 것만 필요하다.
|
main() { char from[20], to[20]; setup(); printf("from ? "); gets(from); printf("to ? "); gets(to); do { isflight(from, to); route(to); tos=0; /* reset the backtrack stack */ } while (getche() != 'q'); } |
해의 일부인 어떤 연결도 skip 필드가 표시되게 할 것이기 때문에, 더 이상 find() 에 의해 발견될 수 없다. 그러므로, 해에서 모든 연결은 효과적으로 제거된다. 해야 할 유일한 것은 tos 를 리셋하는 것인데, 이것은 백트랙 스택을 클리어시킨다.
main() 의 이 번전을 가지고 프로그램을 수행하면 다음을 발견한다.
|
New York to Chicago to Denver to Los Angeles distance is 3000 New York to Toronto to Los Angeles distance is 2600 New York to Denver to Los Angeles distance is 2900 |
가장 좋은 해 세 개가 발견된다는 것은 재미있다. 그러나, 이 결과에 대하여 일반화할수 있다고 기대하지는 말아야 한다. 왜냐하면, 데이터가 데이터베이스에 놓여지는 방법과, 연구하고 있는 상황에 기초를 두기 때문이다.
노드 제거 방법은 복수 해를 생성하는 또 다른 방법이다. 단순히 현재 해의 경로에서 마지막 노드를 제거하고 그리고나서 다시 시도한다. 이를 하기 위해서 main() 함수는 백트랙 스택에서 마지막 노드를 꺼내고, retract() 라고 하는 새 함수를 사용하여 데이터베이스로부터 그것을 제거해야 한다. 또한 clearmarkers() 를 사용하여 skip 필드를 모두 리셋하고, 백트랙 스택을 클리어해야 한다. main(), retract(), 그리고 clearmarkers() 함수들이 아래에 있다.
|
main() { char from[20], to[20], c1[20], c2[20]; int d; setup(); printf("To terminate, press 'q' .... ＼n"); printf("from ? "); gets(from); printf("to ? "); gets(to); do { isflight(from, to); route(to); clearmarkers(); /* reset the database */ if (tos>0) pop(c1, c2, &d); retract(c1, c2); /* remove last node from database */ tos=0; /* reset the backtrack stack */ } while (getche() != 'q'); }
/* remove an entry from the database */ retract(from, to) char *from, *to; { int t; for (t=0; t<f_pos; t++) if (!strcmp(flight[t].from, from) && !strcmp(flight[t].to, to)) { strcpy(flight[t].from, ""); return; } } |
이 방법은 도시 이름으로 단순히 길이가 0 인 스트링을 사용하여 엔트리를 제거한다 (retract). 편의를 위하여 전체 노드 제거 프로그램을 여기에 제시한다.
|
/* Depth-first with multiple solutions using the node-removal method */ #include "stdio.h" #define MAX 100 /* structure of the flight database (db) */ struct FL { char from[20]; char to[20]; int distance; char skip; /* used in backtracking */ }; struct FL flight[MAX]; /* array of db structures */ int f_pos=0; /* number of entries in flight db */ int find_pos=0; /* index for searching flight db */
int tos=0; /* top of stack */ struct stack { char from[20]; char to[20]; int dist; }; struct stack bt_stack[MAX]; /* backtrack stack */
main() { char from[20], to[20], c1[20], c2[20]; int d; setup(); printf("To terminate, press 'q' .... ＼n"); printf("from ? "); gets(from); printf("to ? "); gets(to); do { isflight(from, to); route(to); clearmarkers(); /* reset the database */ if (tos>0) pop(c1, c2, &d); retract(c1, c2); /* remove last node from database */ tos=0; /* reset the backtrack stack */ } while (getche() != 'q'); }
setup() { assert_flight("New York", "Chicago", 1000); assert_flight("Chicago", "Denver", 1000); assert_flight("New York", "Toronto", 800); assert_flight("New York", "Denver", 1900); assert_flight("Toronto", "Calgary", 1500); assert_flight("Toronto", "Los Angeles", 1800); assert_flight("Toronto", "Chicago", 500); assert_flight("Denver", "Urbana", 1000); assert_flight("Denver", "Houston", 1500); assert_flight("Houston", "Los Angeles", 1500); assert_flight("Denver", "Los Angeles", 1000); } /* place facts into flight db */ assert_flight(from, to. dist) char *from, *to; int dist; { if (f_pos<MAX) { strcpy(flight[f_pos].from, from); strcpy(flight[f_pos].to, to); flight[f_pos].distance=dist; flight[f_pos].skip=0; f_pos++; } else printf("flight database full. ＼n"); }
/* reset the "skip" field - i.e., reactivate all modes */ clearmarkers() { int t; for (t=0; t<f_pos; ++t) flight[t].skip=0; }
/* remove an entry from the database */ retract(from, to) char *from, *to; { int t; for (t=0; t<f_pos; t++) if (!strcmp(flight[t].from, from) && !strcmp(flight[t].to, to)) { strcpy(flight[t].from, ""); return; } }
/* show the route and distance */ route(to) char *to; { int dist, t; dist=0; t=0; while(t<tos) { printf("%s to", bt_stack[t].from); dist+=bt_stack[t].dist; t++; } printf("%s ＼n", to); printf("distance is %d＼n", dist); }
/* given from, find anywhere */ find(from, anywhere) char *from, *anywhere; { find_pos=0; while (find_pos<f_pos) { if (!strcmp(flight[find_pos].from, from) && !flight[find_pos].skip) { strcpy(anywhere, flight[find_pos].to); flight[find_pos].skip=1; return flight[find_pos].distance; } find_pos++; } return 0; }
/* if connection between from and to, then return the distance fo flight ; if not, return 0 */ match(from, to) char *from, *to; { register int t; for (t=f_pos-1; t>-1; t--) if (!strcmp(flight[t].from, from) && !strcmp(flight[t].to, to)) return flight[t].distance; return 0; /* not found */ }
/* determine if there is a route between from and to */ isflight(from, to) char *from, *to; { int d, dist; char anywhere[20]; if (d=match(from, to)) { push(from, to, d); /* distance */ return; } if (dist=find(from, anywhere)) { push(from, to, dist); isflight(anywhere, to); } else if (tos>0) { /* backtrack */ pop(from, to, &dist); isflight(from, to); } }
/* stack routines */ push(from, to, dist) char *from, *to; int dist; { if (tos<MAX) { strcpy(bt_stack[tos].from, from); strcpy(bt_stack[tos].to, to); bt_stack[tos].dist=dist; tos++; } else printf("stack full. ＼n"); } pop(from, to, dist) char *from, *to; int *dist; { if (tos>0) { tos--; strcpy(from, bt_stack[tos].from); strcpy(to, bt_stack[tos].to); *dist=bt_stack[tos].dist; } else printf("stack underflow. ＼n"); } |
이 프로그램을 수행하면 다음 해들을 생성한다 :
|
New York to Chicago to Denver to Los Angeles distance is 3000 New York to Chicago to Denver to Houston to Los Angeles distance is 5000 New York to Toronto to Los Angeles distance is 2600 |
여기서, 두 번째 해는 가능한 최악의 경로이지만, 프로그램은 여전히 최적의 해를 발견한다. 이 결과들은 데이터베이스에서 데이터의 물리적 구조와, 연구중인 특별한 상황에 기초하기 때문에 그것들을 일반화하는 것은 불가능하다.
지금까지 설명된 모든 탐색 기법들은 하나의 해를 찾는데에 관계한다. 경험적 탐색에 의해 보여진 것처럼, 좋은, 바람직하게는 최적의 해를 발견하는 가능성을 향상시키려는 노력이 있었다. 그러나 때때로 최적의 해만이 요구된다. 여기서 사용된 최적 해 (optimal solution) 라는 용어는 단순히 여러개의 복수 해 생성 기법들 중 하나를 사용하여 발견할 수 있는 가장 좋은 경로를 의미한다 - 실제로 가장 좋은 해가 아닐 수도 있다 (정말로 최적인 해를 발견하는 것은 아주 비싼 소모적 탐색을 요구할 것이다).
따라서, 비행기 예약의 보기를 떠나기 전, 이 절에서는, 거리를 최소화하기를 원한다는 가정하에, 최적의 예약을 발견하는 프로그램을 개발한다. 여기에서 개발된 프로그램은 복수 해를 생성하는 경로제거 방법과, 거리를 최소화하기 위하여 최소비용 탐색을 사용한다.
가장 짧은 예약을 발견해 내는 열쇠는 앞의 것보다 더 작은 거리를 갖는 해를 보유하는 것이다. 그러므로, 프로그램이 생성할 더 이상의 해가 없을 때, 최적의 해만이 남을 것이다. 이를 이루기 위해, route() 함수를 주로 변경시키고, 현재의 해를 보유하기 위해, 그리고 완성되면 최적의 해를 보유하기 위하여 solution 이라고 부르는 부가적인 스택을 만들어야 한다. 변형된 route() 가 아래에 있다.
|
/* finding shortest distance */ route(to) char *to; { int dist, t; static int old_dist=32000; if (!tos) return 0; /* all done */ dist=0; t=0; while(t<tos) { dist+=bt_stack[t].dist; t++; }
/* if shorter than make new solution */ if (dist<old_dist && dist) { t=0; old_dist=dist; stos=0; /* clear old route from solution stack */ while (t<tos) { spush(bt_stack[t].from, bt_stack[t].to, bt_stack[t].dist); t++; } } return dist; } |
전체 프로그램이 여기에 있다. main() 에서의 변화와, 새로운 해의 노드를 solution 스택에 놓는 spush() 를 더한 것을 주목해야 한다.
|
/* Optimal solution using least-cost with path-removal */ #include "stdio.h" #define MAX 100 /* structure of the flight database (db) */ struct FL { char from[20]; char to[20]; int distance; char skip; /* used for backtracking */ }; struct FL flight[MAX]; /* array of db structures */ int f_pos=0; /* number of entries in flight db */ int find_pos=0; /* index for searching flight db */
int tos=0; /* top of stack */ struct stack { char from[20]; char to[20]; int dist; }; struct stack bt_stack[MAX]; /* backtrack stack */ struct stack solution[MAX]; /* hold temporary solutions */
main() { char from[20], to[20]; int t, d; setup(); printf("from ? "); gets(from); printf("to ? "); gets(to); do { isflight(from, to); d=route(to); tos=0; /* reset the backtrack stack */ } while (d != 0); /* while still finding solutions */
t=0; printf("Optimal solution is : ＼n"); while (t<stos) { printf("%s to ", solution[t].from); d+=solution[t].dist; t++; } printf("%s ＼n", to); printf("distance is %d ＼n", d); }
setup() { assert_flight("New York", "Chicago", 1000); assert_flight("Chicago", "Denver", 1000); assert_flight("New York", "Toronto", 800); assert_flight("New York", "Denver", 1900); assert_flight("Toronto", "Calgary", 1500); assert_flight("Toronto", "Los Angeles", 1800); assert_flight("Toronto", "Chicago", 500); assert_flight("Denver", "Urbana", 1000); assert_flight("Denver", "Houston", 1500); assert_flight("Houston", "Los Angeles", 1500); assert_flight("Denver", "Los Angeles", 1000); } /* place facts into flight db */ assert_flight(from, to. dist) char *from, *to; int dist; { if (f_pos<MAX) { strcpy(flight[f_pos].from, from); strcpy(flight[f_pos].to, to); flight[f_pos].distance=dist; flight[f_pos].skip=0; f_pos++; } else printf("flight database full. ＼n"); }
/* finding shortest distance */ route(to) char *to; { int dist, t; static int old_dist=32000; if (!tos) return 0; /* all done */ dist=0; t=0; while(t<tos) { dist+=bt_stack[t].dist; t++; }
/* if shorter than make new solution */ if (dist<old_dist && dist) { t=0; old_dist=dist; stos=0; /* clear old route from solution stack */ while (t<tos) { spush(bt_stack[t].from, bt_stack[t].to, bt_stack[t].dist); t++; } } return dist; }
/* if flight between from and to, then return the distance of flight ; if not, return 0 */ match(from, to) char *from, *to; { register int t; for (t=f_pos-1; t>-1; t--) if (!strcmp(flight[t].from, from) && !strcmp(flight[t].to, to)) return flight[t].distance; return 0; /* not found */ }
/* given from, find anywhere */ find(from, anywhere) char *from, *anywhere; { find_pos=0; while (find_pos<f_pos) { if (!strcmp(flight[find_pos].from, from) && !flight[find_pos].skip) { strcpy(anywhere, flight[find_pos].to); flight[find_pos].skip=1; return flight[find_pos].distance; } find_pos++; } return 0; }
/* determine if there is a route between from and to */ isflight(from, to) char *from, *to; { int d, dist; char anywhere[20]; if (d=match(from, to)) { push(from, to, d); /* distance */ return; } if (dist=find(from, anywhere)) { push(from, to, dist); isflight(anywhere, to); } else if (tos>0) { pop(from, to, &dist); isflight(from, to); } }
/* stack routines */ push(from, to, dist) char *from, *to; int dist; { if (tos<MAX) { strcpy(bt_stack[tos].from, from); strcpy(bt_stack[tos].to, to); bt_stack[tos].dist=dist; tos++; } else printf("stack full. ＼n"); } pop(from, to, dist) char *from, *to; int *dist; { if (tos>0) { tos--; strcpy(from, bt_stack[tos].from); strcpy(to, bt_stack[tos].to); *dist=bt_stack[tos].dist; } else printf("stack underflow. ＼n"); }
/* solution stack */ spush(from, to, dist) char *from, *to; int dist; { if (stos<MAX) { strcpy(solution[stos].from, from); strcpy(solution[stos].to, to); solution[stos].dist=dist; stos++; } else printf("Shortest distance stack full. ＼n"); } |
이 방법은 한가지 비효율성을 갖는다 : 그 방법은 결론까지의 모든 경로를 따른다. 향상된 방법은 그 경로와 관련된 거리가 현재의 거리와 같거나 그것을 초과했다는 것을 발견하자마자 경로 따라가기를 멈춘다. 그러한 향상을 수용하기 위하여 이 프로그램을 변형하는 것이 재미있다는 것을 알 수 있다.
문제해결에 대한 이 장을 결론짓기 위해, 앞에서 설명된 잃어 버린 열쇠를 찾는 C 프로그램을 제공하는 것만이 적절한 것 같다. 비록 열쇠를 찾는 것은 두 도시 사이의 경로를 찾는 것과 다른 문제이지만, 그것을 해결하기 위해서도 같은 기법을 사용할 수 있다. 지금쯤은 이미 문제를 해결하기 위하여 C 를 어떻게 사용할 것인가에 대하여 아주 잘 이해해야 한다. 따라서 더 이상의 설명없이 즐거움을 위하여 프로그램을 제시한다!
|
/* Find the keys using depth-first */ #include "stdio.h" #define MAX 100 /* structure of the flight database (db) */ struct FL { char from[20]; char to[20]; char skip; }; struct FL flight[MAX]; /* array of db structures */ int f_pos=0; /* number of entries in flight db */ int find_pos=0; /* index for searching flight db */
int tos=0; /* top of stack */ struct stack { char from[20]; char to[20]; }; struct stack bt_stack[MAX]; /* backtrack stack */
main() { char from[20], to[20]; setup(); iskeys("front_door", "keys"); route(to); }
setup() { assert_keys("front_door", "lr"); assert_keys("lr", "bath"); assert_keys("lr", "hall"); assert_keys("hall", "bd1"); assert_keys("hall", "bd2"); assert_keys("hall", "mb"); assert_keys("lr", "kitchen"); assert_keys("kitchen", "keys"); }
/* place facts into database */ assert_keys(from, to) char *from, *to; int dist; { if (f_pos<MAX) { strcpy(keys[f_pos].from, from); strcpy(keys[f_pos].to, to); keys[f_pos].skip=0; f_pos++; } else printf("keys database full. ＼n"); }
/* show the route */ route(to) char *to; { int dist, t; dist=0; t=0; while(t<tos) { printf("%s ", bt_stack[t].from); t++; if (t<tos) printf(" to "); } printf("＼n"); }
match(from, to) char *from, *to; { register int t; for (t=f_pos-1; t>-1; t--) if (!strcmp(keys[t].from, from) && !strcmp(keys[t].to, to)) return 1; return 0; /* not found */ }
/* given from, find anywhere */ find(from, anywhere) char *from, *anywhere; { find_pos=0; while (find_pos<f_pos) { if (!strcmp(keys[find_pos].from, from) && !keys[find_pos].skip) { strcpy(anywhere, keys[find_pos].to); keys[find_pos].skip=1; return 1; } find_pos++; } return 0; }
/* determine if there is a route between from and to */ iskeys(from, to) char *from, *to; { char anywhere[20]; if (match(from, to)) { push(from, to); return; } if (find(from, anywhere)) { push(from, to); iskeys(anywhere, to); } else if (tos>0) { pop(from, to); iskeys(from, to); } }
/* stack routines */ push(from, to) char *from, *to; { if (tos<MAX) { strcpy(bt_stack[tos].from, from); strcpy(bt_stack[tos].to, to); tos++; } else printf("stack full. ＼n"); } pop(from, to) char *from, *to; { if (tos>0) { tos--; strcpy(from, bt_stack[tos].from); strcpy(to, bt_stack[tos].to); } else printf("stack underflow. ＼n"); } |