B*
B*| 그래프 및 트리쉬 알고리즘 |
|---|
| 목록 |
| 관련 항목 |
컴퓨터 과학에서 B*("B star"로 발음됨)는 주어진 초기 노드에서 (하나 이상의 가능한 목표 중) 목표 노드까지의 최소 비용 경로를 찾는 최선의 그래프 검색 알고리즘이다.1979년 한스 베를리너에 의해 처음 출판된 이 책은 A* 검색 알고리즘과 관련이 있다.
요약
알고리즘은 단일 점 값 추정치와 반대로 트리 노드의 간격을 저장한다.그런 다음 최상위 노드 중 하나가 분명히 "최상"인 간격을 가질 때까지 트리의 리프 노드를 검색할 수 있다.
세부 사항
추정치가 아닌 구간 평가
B*-트리의 리프 노드는 단일 숫자가 아닌 간격의 평가가 주어진다.간격은 해당 노드의 실제 값을 포함하도록 되어 있다.리프 노드에 부착된 모든 구간이 이 특성을 만족하는 경우, B*는 목표 상태에 대한 최적의 경로를 식별한다.
백업 프로세스
트리 내의 간격을 백업하기 위해 부모의 상한은 자녀의 상한 최대값으로 설정된다.부모의 하한은 자녀의 하한 최대값으로 설정된다.다른 아이들이 이러한 한계를 제공할 수 있다는 점에 유의하십시오.
검색종료
B*는 "분리"를 만들기 위해 체계적으로 노드를 확장하는데, 이는 루트 직계 아동의 하한이 적어도 다른 직계 아동의 상한만큼 클 때 발생한다.뿌리에 분리를 만드는 나무에는 적어도 최고의 아이는 다른 아이와 다름없다는 증거가 들어 있다.
실제로 복잡한 검색은 실제 리소스 제한 내에서 종료되지 않을 수 있다.그래서 알고리즘은 일반적으로 시간이나 메모리 한계와 같은 인위적인 종료 기준으로 증강된다.인위적인 한계에 부딪혔을 때, 당신은 어떤 움직임을 선택해야 하는지에 대해 경험적으로 판단해야 한다.일반적으로, 나무는 루트 노드의 간격과 같은 광범위한 증거를 당신에게 제공할 것이다.
팽창
B*는 나무를 가로지르는 것이 매우 효율적이라는 뜻으로, 확장시킬 잎을 찾기 위해 반복적으로 내리막길을 내려가는 것이 매우 효과적이라는 것을 의미한다.이 절에서는 확장할 노드를 선택하는 방법을 설명한다.(참고:트리가 메모리에 상주하는지의 여부는 트리가 실제 또는 가상 메모리를 통해 매핑 및/또는 관리될 수 있는 방법을 포함하여 전체적인 구현 효율성의 기능이다.)
트리의 뿌리에서 알고리즘은 증명-최선과 반증-휴식이라는 두 가지 전략 중 하나를 적용한다.증명 최선의 전략에서 알고리즘은 최고 상한과 연관된 노드를 선택한다.그 노드를 확장하면 다른 노드의 상한보다 하한이 더 높게 상승할 수 있을 것으로 희망한다.
불균형 휴식 전략은 상한이 두 번째로 높은 뿌리의 자식을 선택한다.희망은 그 노드를 확장함으로써 상한을 가장 좋은 아이의 하한보다 작게 줄일 수 있다는 것이다.
전략선택
상한이 가장 높은 하위 노드의 하한이 모든 하한 중 가장 높을 때까지 불균형 휴식 전략을 적용하는 것은 무의미하다는 점에 유의한다.
원래의 알고리즘 설명은 어떤 전략을 선택해야 하는지에 대한 추가적인 지침을 제공하지 않았다.더 작은 트리를 가진 선택의 폭을 넓히는 것과 같은 몇 가지 합리적인 대안이 있다.
루트 노드가 아닌 노드에서 전략 선택
일단 루트의 아동을 선택(증명-최상 또는 반증-휴식 사용)하면 알고리즘은 상한이 가장 높은 아동을 반복적으로 선택하여 리프 노드로 하강한다.
leaf 노드에 도달하면 알고리즘은 모든 후속 노드를 생성하고 평가 기능을 사용하여 이들에게 간격을 할당한다.그런 다음 백업 작업을 사용하여 모든 노드의 간격을 백업해야 한다.
전송이 가능한 경우 백업 작업은 선택 경로에 있지 않은 노드 값을 변경해야 할 수 있다.이 경우 알고리즘은 변화가 전파될 수 있도록 자녀에서 모든 부모에게 전달되는 포인터가 필요하다.백업 작업이 노드와 관련된 간격을 변경하지 않으면 전파를 중지할 수 있다는 점에 유의하십시오.
강건함
간격이 부정확하면(노드의 게임-이론적 값이 구간 내에 포함되지 않는다는 의미에서), B*는 정확한 경로를 식별하지 못할 수 있다.그러나 알고리즘은 실제 오류에 상당히 강하다.
메이븐(Scrabble) 프로그램은 평가 오류가 가능할 때 B*의 강건성을 향상시키는 혁신을 가지고 있다.분리로 인해 검색이 종료되면 메이븐은 모든 평가 간격을 소량 확대한 후 검색을 다시 시작한다.이 정책은 점진적으로 트리를 넓혀 결국 모든 오류를 지운다.
2인용 게임으로 확장
B* 알고리즘은 2인칭 결정론 제로섬 게임에 적용된다.사실, 유일한 변화는 그 노드에서 움직이는 측면과 관련하여 "최상"을 해석하는 것이다.따라서 옆구리가 움직이면 최대값을, 상대가 움직이면 최소값을 가져간다.마찬가지로 이동할 측면의 관점에서 모든 간격을 표시한 다음 백업 작업 중에 값을 무효화할 수 있다.
적용들
Andrew Palay는 체스에 B*를 적용했다.엔드포인트 평가는 null-move 검색을 수행하여 할당되었다.같은 하드웨어에서 작동하는 알파-베타 제거 검색 엔진에 비해 이 시스템이 얼마나 잘 작동했는지에 대한 보고는 없다.
메이븐(스크래블) 프로그램은 엔드게임에 B* 검색을 적용했다.종말점 평가는 경험적 접근 계획 시스템을 사용하여 할당되었다.
B* 검색 알고리즘은 조합 게임 집합의 합계 게임에서 최적의 전략을 계산하기 위해 사용되어 왔다.
참고 항목
참조
- Berliner, Hans (1979). "The B* Tree Search Algorithm. A Best-First Proof Procedure". Artificial Intelligence. 12 (1): 23–40. doi:10.1016/0004-3702(79)90003-1. Archived from the original on 2017-09-27. Retrieved 2018-04-29.
- Russell, S. J.; Norvig, P. (2003). Artificial Intelligence: A Modern Approach. Upper Saddle River, N.J.: Prentice Hall. p. 188. ISBN 0-13-790395-2.
- Sheppard, Brian (2002). "World-championship-caliber Scrabble". Artificial Intelligence. 134 (1–2): 241–275. doi:10.1016/S0004-3702(01)00166-7.
