http://blog.naver.com/mcjin02?Redirect=Log&logNo=80036338822
탐색의 개요
- 문제 풀이는 대부분의 인공지능 응용에 있어서 기본이 되며, 사실상 문제를 풀이하는 능력은 인간과 기계에 대한 지능을 평가하는 측도로서 자주 사용
- 두 가지 형태의 문제
- 성공을 보장하는 결정적인 절차(procedure)를 사용함으로써 해결될 수 있는 문제. 이러한 절차는 계산(computation)이라고 부르며, 계산에 의한 풀이는 수학에서 그 절차가 존재하는 문제의 형태에 적용할 수 있으며 이와 같은 문제들을 풀기 위하여 사용되는 방법들은 컴퓨터가 실행할 수 있는 알고리즘의 형태로 변환 가능
- 실세계의 문제들은 거의 계산적인 방법으로는 해결할 수 없기 때문에 탐색에 의하여 해를 구하는 문제. 인공지능으로부터의 접근이 필요
- 탐색 방법의 성능을 평가 측도
- 얼마나 빨리 해를 발견하는가 ?
- 발견된 해가 얼마나 좋은 해(good solution)인가 ?
경로 발견
- 경로를 발견하는 작업은 두 가지 종류의 노력
- 임의의 경로나 가장 짧은 경로를 발견하는데 투자한 노력
- 경로를 여행하는데 실질적으로 투자한 노력
탐색 방법
- 망라적 탐색(blind search)
- 사전에 정보가 제공되지 않은 경우
- 초기 상태,연산자,목표 상태인지를 판정하기 위한 검사 이외에는 아무런 정보도 사용되지 않음
- 사전에 예정된 순서나 무작위로 노드를 탐색하는 방법과 같이 조직적이고 체계적인 방법으로 진행
- 너비 우선 탐색(breadth-first search)
- 초기 노드에서출발하여 초기 노드의 모든 후계 노드, 즉 깊이 1인 모든 노드들을 탐색하고, 그 다음에는 깊이 2인 모든 노드 등의 순서로 탐색하여 목표 노드가 발견되거나 가장 깊은 노드가 탐색될 때까지 계속하여 탐색하는 방법
- 알고리즘
- 루트 노드를 큐(queue)에 넣는다.
- 큐가 비거나 목표에 도달할 때까지 큐의 첫 번째 노드가 목표 노드인가를 조사한다.
- 첫 번째 요소가 목표 노드이면 아무 것도 하지 않는다.
- 첫 번째 요소가 목표 노드가 아니면 큐로부터 첫 번째 요소를 제거하고 그 자식들을 큐의 뒷부분에 첨가한다.
- 목표 노드를 발견하면 성공, 발견하지 못하면 실패한다.
- 만일 해가 존재한다면, 출발 노드에서 목표 노드까지 연산자의 적용 횟수를 최소로 하는 최단 경로(shortest length path)를 찾는 것을 보장. 즉, 최초로 찾아지는 해가 최단 경로를 갖는 해
- 단점은 가지 수가 많거나 깊이가 깊은 그래프를 탐색할 경우, 검색해야 할 노드 수가 기하급수적으로 증가하여 메모리 공간을 많이 차지하기 때문에 비효율적
- 깊이 우선 탐색(depth-first search)
- 출발 노드로부터 시작하여 노드를 계속적으로 확장하고, 가장 최근에 생성된 노드를 먼저 확장시키는 탐색 기법
- 만약 후계 노드가 없다든지, 어떤 노드의 모든 후계 노드를 방문했지만 목표 노드를 발견하지 못하였을 경우에는 즉각적으로 바로 직전 노드로 돌아감
- 경우에 따라서는 해가 없는 경로를 계속해서 따라갈 수 있으므로, 필요에 따라 상위 노드로 되돌아가는 백트랙킹(backtracking)을 할 수 있는 방안를 마련 해야 함
- 일반적으로 적당한 깊이 제한을 두어 어떤 노드가 그 이상의 깊이를 갖게 되면 이 노드를 더 이상 확장시키지 않고, 깊이 제한을 넘지 않는 것 중에서 가장 깊은(즉, 가장 최근에 생성된) 노드를 골라서 확장
- 알고리즘
- 루트 노드를 스택에 넣는다.
- 스택이 비거나 목표에 도달할 때까지 스택의 첫 번째(top) 노드가 목표 노드인가를 조사한다.
- 첫 번째 요소가 목표 노드이면 아무 것도 하지 않는다.
- 첫 번째 요소가 목표 노드가 아니면 스택으로부터 첫 번째 요소를 제거하고 그 자식들을 스택의 앞부분(top)에 첨가한다.
- 목표 노드를 발견하면 성공, 발견하지 못하면 실패한다.
- 장점으로는 신속하게 원하는 목표를 찾을 수 있으며 구현하기가 용이하며 많은 가지들을 가지고 있는 상태 공간에서 매우 유용
- 단점으로는 해가 없는 경로를 계속해서 탐색할 수 있기 때문에 통상적으로 깊이 제한을 두어 필요에 따라 전 노드로 되돌아갈 수 있는 백트랙킹이 요구
- 최단 경로의 해를 반드시 구할 수는 없으나, 일반적으로 너비 우선 탐색 보다 효율이 좋음
- 균일 비용 탐색(uniform-cost search)
- 출발노트로부터의 경로비용이 최소인 노드를 선택하여 확장
- 탐색과정에서 어떠한 노드 n을 확장시켜 m개의 후계노드가 생성될 경우 후계노드를 ni(i=1,2,...,m)라 할 때 ni의 경로비용
- g(ni)=g(n)+C(n, ni)
- g(n): 출발노드로부터 노드 n까지의 경로비용
- C(n, ni): 노드 n에서 노드 ni로 이동하는데 소비되는 비용
- 출발노드로부터의 경로비용이 최소인 노드가 먼저 확장되며, 따라서 이 과정에서 발견된 목표노드는 최소의 비용이 소요되는 경로
- 탐색을 하기 전에 정보가 제공되지 않은 경우에는 너비 우선 탐색이나 깊이 우선 탐색과 같은 망라적 탐색방법을 시도. 이때 어떤 망라적 탐색 방법을 선택할 것인가는 목표 상태가 있을 법한 위치와 구하고자 하는 해의 성질에 따라 선택
- 그다지 깊지 않은 곳에 해가 존재할 것 같은 경우에는 너비 우선 탐색이 가능하고, 해가 탐색 트리의 왼쪽편의 깊은 곳에 존재할 것 같은 경우에는 깊이 우선 탐색이 가능할 것. 최적해를 구할 경우에는 너비 우선 탐색을, 좋은 해라도 무방할 경우에는 깊이 우선 탐색을 시도
- 망라적 탐색 방법은 소규모 문제에는 적용이 가능해도 대규모 문제에서는 조합에 의한 폭발이 발생하기 때문에 이를 해결하기 위하여 문제 고유의 휴리스틱(Heuristic)이 요구
- 알고리즘
- OPEN에 출발노드를 넣는다. 출발노드의 비용은 0이다.
- OPEN에 노드가 남아 있는 동안 다음을 반복한다.
- OPEN의 제일 앞에 있는 노드를 꺼내어 CLOSED에 넣는다.이 노드를 n이라고 한다.
- 노드 n이 목표 노드라면 탐색은 성공적으로 끝난다. 포인터를 역으로 추적하면 탐색 경로를 얻을수 있다
- 노드 n을 확장하여 후계노드 n1,n2,.....,ni을 생성한다. 이를 후계노드에 부모노드인 노드 n을 가리키는 포인터를 첨부한다.
- 후계노드 n1,n2,..,ni의 경로비용을 계산한다.
- 각각의 후계노드 nj,j=1,2,...,i에 대해 다음을 수행한다.
- nj와 동일한 노드가 OPEN에 존재하고, 그 노드의 경로비용이 nj의 경로비용보다 크다면 그노드를 nj로 대치하고, 그렇지 않으면 nj는 무시한다.
- nj와 동일한 노드가 CLOSED에 존재한다면 그 노드의 경로비용은 nj의 경로비용 보다 작다. 따라서 nj는 무시한다.
- nj와 동일한 노드가 OPEN이나 CLOSED에 존재하지 않으면 nj를 OPEN에 첨가한다.
- OPEN에 저장된 노드들을 경로비용의 오름차순으로 정렬한다.
- 탐색은 실패로 끝난다.
- 휴리스틱 탐색
- 망라적 탐색 방법은 목표 노드까지의 경로를 찾는데 상당히 소모적. 원칙적으로 이 방법들은 경로를 찾는 문제에 대한 해를 제공하지만, 경로를 발견하기까지 너무 많은 노드를 확장시키므로 실용적이지 못한 경우가 많음
- 많은 문제에서 탐색 작업을 축소시키기 위하여, 항상 옳은 것은 아니지만 대부분의 경우에 잘 맞는 경험에 의한 규칙(rules of thumb)들을 이용하는 경우가 많음. 이와 같은 정보를 사용하여 탐색 작업을 효율적으로 탐색을 진행시키는 방법을 휴리스틱 탐색 방법(heuristic search methods)이라고 부르며, 이때 사용되는 정보를 휴리스틱(heuristic)이라고 부름
- 휴리스틱 정보는 비록 부정확하고 보장되지는 않지만, 빠르게 해를 발견하거나 최적인 해를 발견하거나 또는 둘 다를 만족할 수 있는 가능성을 증가 시킴
- 휴리스틱 정보를 이용하는 탐색 방법들은 탐색 과정에서 노드들의 확장 순서를 정하기 위해 평가 함수(evaluation function)를 사용. 목적은 확장시킬 노드들에 순위를 매김으로써 어떤 것이 목표 노드까지의 최상의 경로에 있음직한가를 결정하는 것
- 언덕 오르기 탐색
- 목표 상태를 언덕의 꼭대기에 비유하고, 각 노드에서 언덕의 꼭대기에 가장 빨리 도달할 수 있는 다음 노드를 선택하는 방법을 언덕 오르기 탐색(hill climbing search)
- 이 방법은 깊이 우선 탐색과 비슷한 방법으로 가장 유망한 자녀 노드를 선택. 자녀 노드들이 알려져 있을 때, 평가 함수를 사용하여 노드 선택을 위한 함수값을 계산. 함수값에 근거하여 최선의 노드를 선택하고 그 후에는 부모 노드나 자녀 노드에 대한 참고는 더 이상 하지 않음
- 즉, 언덕 오르기 탐색을 통하여 트리를 확장하는 방법은 깊이 우선 탐색과 동일하지만, 목표까지 남아 있는 거리라는 휴리스틱에 따라 확장할 노드들에 대하여 평가값을 부여한 후 정렬
- 목표 상태로 접근하는 방향으로 상태를 변화시킬 수 없는 경우가 발생하는데, 평가 함수의 값이 극대값이나 평원 혹은 산등성이에 도착했을 때 이러한 상태가 발생
- 극대값(local maximum)은 인접한 근처의 모든 상태들보다도 원하는 목표 상태에 가깝지만, 멀리 떨어져 있는 다른 모든 상태들보다는 목표 상태에 가깝지 못할 경우인데 이 때는 백트랙킹이 필요하게 됨
- 평원(plateau)은 인접한 상태들이 모두 같은 값을 갖는 탐색 공간의 평탄한 지역이며 국부적 비교를 이용하여 움직일 최적 방향을 결정하는 것이 불가능. 따라서 평원을 벗어나기 위한 연산자의 적용이 필요
- 산등성이(ridge)는 주위 지역보다는 높지만, 하나의 움직임만으로는 어느 일정한 방향으로 탐색을 계속 수행할 수 없는 탐색 공간의 영역이므로 테스트할 방향의 수를 늘임으로써 이를 극복 가능
- 신뢰할 만한 정보를 산출할 수 있는 함수에 의하여 전체적인 목적 노드를 찾기 위한 탐색을 잘 유도할 수 있다면 망라적 탐색 보다 훨씬 효율적
- 알고리즘
- 루트 노드를 스택에 넣는다.
- 스택이 비거나 목표에 도달할 때까지 스택의 첫 번째 노드가 목표 노드인가를 조사한다.
- 첫 번째 요소가 목표 노드이면 아무 것도 하지 않는다.
- 첫 번째 요소가 목표 노드가 아니면 스택으로부터 첫 번째 요소를 제거하고 그 자식들을 평가된 남은 거리에 따라 정렬하여 스택의 앞 부분(top)에 첨가(push)한다.
- 목표 노드를 발견하면 성공, 발견하지 못하면 실패한다.
- 최적 우선 탐색(best-first search)
- 지역적으로 확장된 트리의 모든 노드 중, 가장 좋은 노드부터 탐색을 시작
- 산의 최고 지점을 찾기 위해 여러 팀이 협동하여 움직이는 것과 비슷
- 기본적으로 우선 순위가 정해져야 하고, 많은 메모리가 필요하며 구현 방법이 복잡
- 알고리즘 (알고리즘 설명상에서는 priority queue 자료구조를 이야기 하지 않는가 생각된다.)
- 루트 노드를 큐(queue)에 넣는다.
- 큐가 비거나 목표에 도달할 때까지 큐의 첫 번째 노드가 목표 노드인가를 조사한다.
- 첫 번째 요소가 목표 노드이면 아무 것도 하지 않는다.
- 첫 번째 요소가 목표 노드가 아니면 큐로부터 첫 번째 요소를 제거하고 그 자식들을 큐에 첨가한다.그리고 평가값에 따라 큐의 모든 요소를 정렬한다.
- 목표 노드를 발견하면 성공, 발견하지 못하면 실패한다.
- A* 알고리즘
- 출발노드로부터 목표노드까지의 최적경로를 탐색하기 위한 것
- 각각의 노드에 대한 평가함수를 정의
- 알고리즘
- 출발노드를 OPEN에 넣는다. 출발노드의 평가함수 값을 식에 따라 계산하면 된다.
- OPEN에 노드가 남아 잇는 동안 다음을 반복한다.
- OPEN에서 f값이 최소인 노드를 꺼내어 CLOSED에 넣는다. 이 노드가 n이라 한다. 만일 동일한 f값을 가지고 있는 노드가 여러 개 있을 때에는 임의로 선택하되 목표 노드가 있다면 우선적으로 선택한다.
- 노드 n이 목표노드라면 타색은 성공적으로 끝난다.포인터를 역으로 추적하면 탐색경로를 얻을 수 있다.
- 노드 n을 확장하여 후계노드 n1,n2,...ni를 생성한다.이들 후계노드에 부모노드인 노드 n을 가리키는 포인터를 첨부한다.
- 각각의 후계노드에 대해 평가함수 f(n1),f(n2),...,f(ni)를 계산하여 첨부한다.
- 각각의 후계노드 nk, k=1,2,.....,i에 대하여
- 동일한 노드가 OPEN에 이미 존재한다면(그 노드를 n old라 하자)
- f(n old)가 f(nk)보다 작다면 nk는 버린다
- 그렇지 않으면, n old를 OPEN에서 제거한다.
- 동일한 노드가 CLOSED에 이미 존재한다면(그 노드를 n' old라 하자)
- f(n' old)가 f(nk)보다 작다면 nk는 버린다.
- 그렇지 않으면 n'old의 부모포인터가 노드 n을 가리키도록 수정하고 평가함수를 f(nk)으로 수정한다.또한 n'old의 모든 후계노드에 대한 경로비용 g가 변화하였으므로 이를 수정한다.
- 동일한 노드가 OPEN이나 CLOSED에 존재하지 않으면 nk을 OPEN에 삽입한다.
- 동일한 노드가 OPEN에 이미 존재한다면(그 노드를 n old라 하자)
- 탐색은 실패로 끝난다.
- 8-퍼즐 문제의 탐색 예
- 표현
- 연산자 : UP, DOWN, LEFT, RIGHT
- 제약 조건 : 한번에 한 칸씩 이동, 퍼즐의 내부에서만 이동
- 목적 함수 : 현 상태와 목표 상태와의 차를 최소화
- 너비 우선 탐색
- 깊이 우선 탐색
- 휴리스틱 탐색
- 노드의 확장 순서를 결정하기 위해서는 노드의 가능성을 계산하는 방법이 필요
- 평가 함수를 구하는 방법. 노드가 가장 우수한 경로 상에 있을 확률을 정의하거나, 노드와 목표 노드 사이의 거리 또는 차의 측도를 제안하거나, 또는 판을 사용하는 게임의 경우에는 목표를 향하고 있는 국면에 있는가 어떤가에 관한 특징에 따라 그 국면의 값을 정하거나 함
- 간단한 평가 함수
- f(n) = d(n) + w(n)
- d(n)은 탐색 트리의 노드 n의 깊이, w(n)은 노드 n에 대한 잘못 놓여 있는 숫자판의 수
- 만약 평가 함수의 값을 단순히 f(n) = d(n)으로 하면 너비 우선 탐색과 동일
- 정말로 가능성이 있는 노드를 딘가에서 빠뜨리게 되는 평가 함수를 사용하면, 최소 비용의 경로를 얻을 수가 없고, 모든 노드에 대하여 도하게 평가하는 평가 함수(예를 들어 너비 우선 탐색으로 되는 평가 함수)를 사용하면 아주 많은 노드를 확장
- 표현
- 게임에서의 탐색
- Babbage는 그의 수리 엔진(analytic engine)을 사용하여 체스를 두는 프로그램을 작성하려 했으며, 후에 삼목놀이(tic-tac-toe)를 하는 기계를 만듬
- Shannon은 체스 프로그램에 사용될 수 있는 기법과 관련된 논문을 발표했으며, 몇 년 후 Turing은 체스 프로그램을 작성
- 1960년대 초기에 Samuel에 의해 실제로 사용이 가능한 게임 프로그램이 처음으로 만들어졌으며, 이 프로그램은 단순히 체스를 두는 것 뿐만 아니라 실수를 깨닫고 수행 능력을 향상
- 게임이 기계의 지능을 조사하기에 적합한 분야로 생각되는데는 두 가지 이유
- 게임은 이기고 지는 것을 쉽게 알아낼 수 있는 구조화된 작업
- 기계에 의한 게임 분야에 대해 계속적인 관심을 두는 것과 관련
- 게임은 많은 양의 지식을 필요로 하지 않는다. 게임은 출발 상태로부터 승리의 상태를 찾는 탐색에 의해 해결될 수 있다고 생각되었다.
- 단순한 게임을 제외한 어느 게임에도 적용되지 못함
- 이유(체스 경우)
- 평균 분기 계수는 35 정도이다.
- 평균적으로 한 게임에서 경기자는 50수 정도를 둔다.
- 따라서 완전한 게임 트리를 조사하기 위해서는 35100개의 위치를 조사해야 한다.
- 게임은 이기고 지는 것을 쉽게 알아낼 수 있는 구조화된 작업
- 단순히 게임 트리만을 탐색하는 프로그램은 상대방이 살아있는 동안 단 한 수도 두지 못할 것이 분명. 이를 해결하기 위해 일종의 경험적 탐색 방법이 필요
- 탐색 과정의 기본적인 기법은 해답의 생성과 테스트
- 다음 두 가지를 수행하여 탐색을 기초로 한 문제 풀이 프로그램의 효율성을 향상 시킬 수 있음
- 적절한 움직임(경로)만을 만들도록 해답의 생성 과정을 향상시킨다.
- 최적 움직임을 찾아 먼저 조사하기 위해, 테스트 과정을 향상시킨다.
- 체스 문제로 살펴 보기
- 매번 이용 가능한 움직임은 35개 정도
- 만약 단순히 움직임만을 만드는 과정을 사용한다면, 테스트 과정(이 과정은 탐색과 경험적 지식에 사용되는 평가 함수를 적절히 결합하여 사용한다)에서 이들 각각을 조사
- 이 경우 테스트 과정은 매우 많은 가능성을 조사해야 하기 때문에 엄청나게 빨리 수행. 따라서 테스트 과정은 수행되어야 할 일을 모두 정확하게 처리하지 못할 경우도 있음
- 움직임만을 만드는 과정 대신, 이길 가능성이 있는 이동을 만들어 내는 과정(plausible move generator)을 사용하여, 유망한 몇 개의 움직임만을 선택하기 위해 경험적 지식을 사용하는 것이 더욱 더 중요. 이것은 체스 프로그램에서 특히 중요한 역할
- 상당히 선택적인 움직임을 만들어 내는 테스트 과정을 사용할 경우, 주어진 각 움직임의 가치를 평가하기 위해 필요한 시간이 증가할 수 있음. 따라서 신뢰도가 높은 결과를 얻을 수 있음
- 경험적 지식을 해답의 생성과 테스트 과정과 함께 결합하여 전체적인 시스템의 수행 능력을 향상시킬 수 있음
- 문제에 대한 풀이를 찾기 위해 탐색 과정을 사용할 때 이상적인 방법은 목표 상태에 도착할 때까지 문제 공간 내에서의 움직임을 만들어 내는 것
- 게임 프로그램의 목표 상태는 승리의 상태. 그러나 체스와 같은 게임의 경우, 비록 이길 수 있는 움직임을 효과적으로 만들어 내는 과정을 사용한다 하더라도, 목표 상태를 찾아 낼 때까지 탐색하는 것은 대체로 불가능.
- 최적 움직임을 선택하기 위해서는 정적 평가 함수(static evaluation function)를 사용하여 만들어진 체스판의 위치를 비교함으로써 유망한 움직임을 찾음
- 개개의 체스판 위치로부터 궁극적인 승리의 가능성을 추정하는 정적 평가 함수는 이용할 수 있는 모든 정보를 사용하여 각 체스판의 위치에 대한 가치를 평가
- 유망한 움직임의 결과로 만들어진 체스판의 상태에 직접 정적 함수를 적용할 수도 있지만, 매우 효율적인 정적 평가 함수를 만든다는 것이 어렵기 때문에 가능한 한 게임 트리의 많은 레벨에 대하여 평가 함수를 적용하는 것이 좋음
- MINIMAX 프로시저
- 게임에서 판의 상황에 관한 모든 판단을 하나의 평가값으로 변환할 수 있는 상황 분석기(situation analyzer)를 가지고 있다고 가정. 그리고 편의상 평가값의 양수 값은 한 경기자가 유리함을 나타내고 음수 값은 다른 경가자가 유리함을 나타낸다고 가정. 유리함의 정도는 평가값의 절대값에 정비례
- 정적 평가(static evaluation) : 평가값을 결정하는 프로시저
- 이동 가능한 제한된 경로의 마지막 레벨에서 정적 평가기(static evaluator)라고 불리는 상황 분석기에 의해 만들어진 정적 평가값을 발견할 수 있음
- 양수의 평가값을 원하는 경기자를 최대화 경기자(maximizing player), 그 상대방 경기자는 최소화 경기자(minimizing player)
- 만약 최대화 경기자의 차례라면, 그는 가장큰 양수값으로 인도하는 경로를 찾을 것. 최대화 경기자는 그의 상대편은 가장 큰 음수값을 갖는 경로로 게임을 진행.
- 게임 트리를 통하여 득점(scoring) 정보를 위의 노드로 전달하는 프로시저를 MINIMAX 프로시저라 하며 각 노드의 득점은 바로 아래 노드들의 득점들 중 최소값 혹은 최대값을 취한 것이기 때문.
- 마지막 레벨에 도달했는가 혹은 해당 레벨이 최소화 레벨인지 아니면 최대화 레벨인지를 결정
- 만약 마지막 레벨에 도달했다면 해당 경기자에게 해당되는 현재 위치의 정적 값을 계산하고 그 결과를 보고한다
- 만약 최소화 레벨이면 현재 위치의 자식들에게 MINIMAX를 적용하고, 그 결과의 최소값을 보고한다.
- 만약 최대화 레벨이면 현재 위치의 자식들에게 MINIMAX를 적용하고, 그 결과의 최대값을 보고한다.
- 최대 최소 프로시저의 전체적인 아이디어는 게임의 판세를 단일 숫자인 정적 값으로 나타내는 사실에 있다는 점
- 판세를 단일 숫자로 나타내는 것은 심각한 결점을 가지고 있다. 즉, 숫자가 어떻게 결정되었는가에 대하여 아무런 언급을 하지 않음
- 최대 최소 프로시저는 경로를 특별한 정책없이 생성시키고, 정적 함수를 계산함으로써 비용이 듬. 이러한 비용은 사용되는 수 발생기(move generator)와 정적 평가기의 정교함에 따라 달라짐
- ALPHA-BETA 프로시저
- 우선 정적 평가기는 트리의 마지막 레벨에서 발견되는 각 상황에서 사용되어야 하는 것처럼 보일 수 있으나 다행스럽게도 그렇지는 않다. 생성되어야 할 트리의 가지 수와 정적 평가의 횟수를 줄이는 프로시저가 제안되어 있어, 트리의 마지막 레벨까지 따라가 보지 않고도 어떤 경로들이 나쁜가를 알아낼 수 있으며, 이를 위하여 탐색 전반에 걸쳐서 절단(cutting)이 이루어지고 있음
- 키 원리(key principle)가 유용함은 명백
- 만일 상대방의 잠재적 수(potential move)가 나쁜 반응을 하면 그 나쁜 수에 대한 다른 반응들을 검사할 필요가 없음. 나쁜 길에 대하여 얼마나 많은 길들이 있으며 얼마나 나쁜 경우가 있는지 발견할 필요가 없음.
- 주어진 노드에서 바랄 수 있는 최선의 것에 대한 어떤 것이 발견될 때마다, 조상 노드에 대하여 무엇이 알려져 있는지 검사. 주어진 노드 아래를 더 이상 찾지 않아도 될 수 있음.
- 한 노드의 정확한 값이 결정될 때마다, 부모에 대해 무엇이 알려져 있는지 검사. 부모 노드가 바랄 수 있는 최선의 값이 개선되거나 정확히 정해질 수 있음.
댓글 없음:
댓글 쓰기