의견.png

AND-OR 검색 트리

위키원
(And or 검색 트리에서 넘어옴)
이동: 둘러보기, 검색

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

개요[편집]

상대의 움직임이 어떨지에 대한 결정을 내리지 못하기 때문에, AND-OR 트리의 검색 방식과 OR 트리의 검색 방식은 다르다. OR 트리는 트리를 검색해서 최선의 해결책이나 가장 얕은 해결책을 찾는 것이 목표이지만, AND-OR 트리의 경우에는 해결책을 찾는 것과는 거의 관계가 없다. 트리의 크기가 보통 일반적인 OR 트리의 크기보다 훨씬 크기 때문에 트리 전체를 검색할 수 없다. 그 대신에, AND-OR 트리를 검색하면 일정한 수의 변화를 예상하고, 그 깊이에서 가능한 각 상태의 게임 상태를 평가한 다음, 그 값을 트리로 다시 전달해서 가장 적합한 이동을 결정한다. 대신 AND-OR 트리 검색은 유동적이지 않은 수를 예측한 다음, 해당 깊이에서 할 수 있는 각 상태에서 게임 상태를 평가하고, 값을 트리로 전달하여 가장 적합한 이동을 결정한다. 게임의 특정 상태가 얼마나 유익한지를 알려주는 평가 함수를 사용하는 데는 종종 어려움을 겪지만, 트리로 값을 거꾸로 전파하기 위한 최소극대화(미니맥스) 알고리즘이 있다.[1]

AND-OR 검색 트리는 조합이나 인공지능 같은 많은 문제들에 유용하게 사용될 수 있다. AND-OR 검색 트리는 내부 노드에 AND 또는 OR 테이블이 지정된 트리이다. 비 이론적 알고리즘이 비결정적 튜링 머신과 유사하다는 부분에서 계산 이론상 대체 튜링 머신의 아이디어와 유사하다. AND와 OR의 평가는 각 잎에 참과 거짓을 지정하는 것이다. 트리 T와 T의 잎에 대한 평가가 주어지면 내부 노드와 T의 값은 명백하게 재귀적으로 정의된다. 제한되지 않은 AND-OR 트리의 예시가 다음 조건을 만족한다고 하자.

  1. 하위 노드 중 하나 이상이 참이면 OR 노드는 참이다.
  2. 모든 자식이 참이면 AND 노드는 참이다.

제한된 AND-OR 검색 트리가 일반적이고, 참으로 표시된 잎은 일종의 계약조건을 충족해야 한다. 제한된 AND-OR 검색 트리의 해결책은 제약 조건을 만족시키고 트리에 참값을 제공하는 평가이다.[2]

개념[편집]

예시
AND-OR 검색 트리(And-or tree)

목표 감소 방법을 사용하여 문제 P를 해결하기 위한 검색 공간을 나타낸다.

  • P if Q and R
  • P if S
  • Q if T
  • Q if U
정의

문제 와 다음과 같은 형식의 문제 해결방법이 제공될 경우,

 if  and … and 

AND-OR 검색 트리는 트리의 뿌리가 으로 라벨을 붙인 노드다. 문제 P로 표시된 노드 N은 P 형식의 방법이 있으면 성공 노드(즉, P는 "사실"이다)이다. P를 해결하는 방법이 없는 경우 노드는 장애 노드이다. 같은 호로 결합한 노드 N의 모든 자식이 성공 노드라면 노드 N도 성공 노드다. 그렇지 않으면 노드가 장애 노드이다.

관계[편집]

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

각주[편집]

  1. Bruce Rosen, 〈CS 161 Recitation Notes - AND-OR Trees〉, 《캘리포니아대학교 로스앤젤레스》, 2009
  2. Constrained AND/OR trees〉, 《뉴욕대학》

참고자료[편집]

같이 보기[편집]


  의견.png 이 AND-OR 검색 트리 문서는 알고리즘에 관한 토막글입니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 이 문서의 내용을 채워주세요.