AND-OR 검색 트리

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

개요

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

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

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

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

개념

예시

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

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

정의

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

$P$ if $P_{1}$ and … and $P_{n}$

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

관계

• 논리 프로그램

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

참고자료

• And-or tree 영문 위키백과 - https://en.wikipedia.org/wiki/And%E2%80%93or_tree
• 〈Constrained AND/OR trees〉, 《뉴욕대학》
• Bruce Rosen, 〈CS 161 Recitation Notes - AND-OR Trees〉, 《캘리포니아 대학교 로스앤젤레스》, 2009
• Robert Eugeniu Mateescu , 〈[AND/OR Search Spaces for Graphical Models DISSERTATION]〉, 《캘리포니아 대학교》, 2007

같이 보기

• 알고리즘

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

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘, 알고리즘 □■⊕, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 채굴 알고리즘 SHA-256 • X11 • X11고스트 • X13 • X14 • X15 • X16R • X17 • 그로스톨 • 네오스크립트 • 니스트5 • 리라2알이 • 미리아드-그로스톨 • 블레이크 • 블레이크2 • 블레이크B • 블레이크2B • 블레이크256R8 • 블레이크256R14 • 스컹크해시 • 스케인 • 스크립트 알고리즘 • 스크립트엔 • 엘비알와이(LBRY) • 이더해시 • 이퀴해시 • 제반 • 쿼크 알고리즘 • 큐빗 알고리즘 • 크립토나이트 • 크립토나이트 라이트 • 타임트래블10 • 텐서리티 • 파스칼 • 프로그작업증명(ProgPoW) 매칭 알고리즘 경매 • 더치 경매 • 매칭 알고리즘 • 매칭튜터 • 비크리 경매 • 센디 • 집닥 • 튜다 • 틴더 추천 알고리즘 TF-IDF • 추천 알고리즘 • 콘텐츠 기반 필터링 • 협업 필터링 고급 검색 알고리즘 AND-OR 검색 트리 • 국소 검색 알고리즘 • 국소 다발 검색 • 모의정련 • 언덕 오르기 검색 • 유전 알고리즘 대항 검색 검색의 차단 • 알파베타 가지치기 • 전방 가지치기 • 최소최대 알고리즘 제약 만족 문제 국소검색 • 역추적검색 • 제약전파 게임이론 게임이론 • 공유지의 비극 • 내시균형 • 메커니즘 디자인 • 비협조게임 • 사회선택이론 • 역게임이론 • 제로섬게임 • 조정게임 • 죄수의 딜레마 • 치킨게임 • 팃포탯 • 협조게임 위키 : 자동차, 교통, 지역, 산업, 기업, 단체, 업무, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반