AND-OR 검색 트리 편집하기

'''AND-OR 검색 트리'''<!--And-or 검색트리, And-or 검색트리-->(And-or tree)는 하위 문제의 접속사 및 분리에 대한 문제 또는 목표의 감소를 그래픽으로 표현한 것이다.

== 개요 ==
상대의 움직임이 어떨지에 대한 결정을 내리지 못하기 때문에, AND-OR 트리의 검색 방식과 OR 트리의 검색 방식은 다르다. OR 트리는 트리를 검색해서 최선의 해결책이나 가장 얕은 해결책을 찾는 것이 목표이지만, AND-OR 트리의 경우에는 해결책을 찾는 것과는 거의 관계가 없다. 트리의 크기가 보통 일반적인 OR 트리의 크기보다 훨씬 크기때문에 트리 전체를 검색 할 수 없다. 그 대신에, AND-OR 트리를 검색하면 일정한 수의 변화를 예상하고, 그 깊이에서 가능한 각 상태의 게임 상태를 평가한 다음, 그 값을 트리로 다시 전달해서 가장 적합한 이동을 결정한다. 대신 AND-OR 트리 검색은 유동적이지 않은 수를 예측한 다음, 해당 깊이에서 할 수 있는 각 상태에서 게임 상태를 평가하고, 값을 트리로 전달하여 가장 적합한 이동을 결정한다. 게임의 특정 상태가 얼마나 유익한지를 알려주는 평가 함수를 사용하는 데는 종종 어려움을 겪지만, 트리로 값을 거꾸로 전파하기 위한 최소극대화(미니맥스) 알고리즘이 있다.<ref> Bruce Rosen, 〈[http://web.cs.ucla.edu/~rosen/161/notes/search2.html CS 161 Recitation Notes - AND-OR Trees]〉, 《캘리포니아대학교 로스앤젤레스》, 2009</ref>

AND-OR 검색 트리는 조합이나 인공지능 같은 많은 문제들에게 유용하게 사용될 수 있다. AND-OR 검색 트리는 내부 노드에 AND 또는 OR 테이블이 지정된 트리이다. 비 이론적 알고리즘이 비 결정적 튜링 머신과 유사하다는 부분에서 계산 이론상 대체 튜링 머신의 아이디어와 유사하다. AND와 OR의 평가는 각 잎에 참과 거짓을 지정하는 것이다. 트리 T와 T의 잎에 대한 평가가 주어지면 내부 노드와 T의 값은 명백하게 재귀적으로 정의된다. 제한되지 않은 AND-OR 트리의 예시가 다음 조건을 만족한다고 하자. 
# 하위 노드 중 하나 이상이 참이면 OR 노드는 참이다. 
# 모든 자식이 참이면 AND 노드는 참이다. 
제한된 AND-OR 검색 트리가 일반적이고, 참으로 표시된 잎은 일종의 계약조건을 충족해야 한다. 제한된 AND-OR 검색 트리의 해결책은 제약 조건을 만족시키고 트리에 참값을 제공하는 평가이다.<ref>〈[https://cs.nyu.edu/courses/spring01/G22.2560-001/andor.html#Definition Constrained AND/OR trees]〉, 《뉴욕대학》</ref>

== 개념 ==
;예시
[[파일:AND-OR 검색 트리.png|300픽셀|오른쪽|'''AND-OR 검색 트리'''(And-or tree)]]
목표 감소 방법을 사용하여 문제 P를 해결하기 위한 검색 공간을 나타낸다. 
* P if Q and R
* P if S
* Q if T
* Q if U

;정의
문제 <math>P_{0}</math>와 다음과 같은 형식의 문제 해결방법이 제공될 경우,
 <math>P</math> if <math>P_{1}</math> and … and <math>P_{n}</math>
AND-OR 검색 트리는 트리의 뿌리가 <math>P0</math>으로 라벨을 붙인 노드다. 문제 P로 표시된 노드 N은 P 형식의 방법이 있으면 성공 노드(즉, P는 "사실"이다)이다. P를 해결하는 방법이 없는 경우 노드는 장애 노드이다. 같은 호로 결합된 노드 N의 모든 자식들이 성공 노드라면 노드 N도 성공 노드다. 그렇지 않으면 노드가 장애 노드이다.

== 관계 ==
* '''논리 프로그램'''
:트리를 생성하는 데 사용되는 방법은 변수가 없는 제안형 논리 프로그램이다. 변수를 포함하는 논리 프로그램의 경우, 결합형 하위 문제의 해결책이 호환되어야 한다. 이러한 복잡성에 따라, AND-OR 검색 트리에 대한 순차 및 병렬 검색 전략은 논리 프로그램 실행을 위한 연산 모델을 제공한다.

{{각주}}

== 참고자료 ==
* And-or tree 영문 위키백과 - https://en.wikipedia.org/wiki/And%E2%80%93or_tree
* 〈[https://cs.nyu.edu/courses/spring01/G22.2560-001/andor.html#Definition Constrained AND/OR trees]〉, 《뉴욕대학》
* Bruce Rosen, 〈[http://web.cs.ucla.edu/~rosen/161/notes/search2.html CS 161 Recitation Notes - AND-OR Trees]〉, 《캘리포니아 대학교 로스앤젤레스》, 2009
* Robert Eugeniu Mateescu , 〈[AND/OR Search Spaces for Graphical Models DISSERTATION]〉, 《캘리포니아 대학교》, 2007

== 같이 보기 ==
* [[알고리즘]]

{{알고리즘|토막글}}