그리고-또는 나무

및/또는 트리는 하위 문제(또는 하위 목표)의 결합과 분리에 대한 문제(또는 목표)의 감소를 그래픽으로 표현한 것입니다.

예

및/또는 트리:

는 목표 저감 방법을 사용하여 문제 P를 해결하기 위한 서치 공간을 나타냅니다.

P if Q와 R

P if S

Q if T

Q if U

정의들

첫 번째 문제₀ P와 형식의 문제 해결 방법 집합이 주어진 경우:

P if₁ P 및 … 및_n P

연관된 및/또는 트리는 다음과 같은 라벨이 붙은 노드 세트입니다.

1. 트리의 루트는 P로₀ 라벨이 지정된 노드입니다.
2. 문제 또는 하위 문제 P에 의해 라벨링된 노드 N마다, 또한 P 및 … 및 P에_n 의해₁ 라벨링된 형식 P의 모든 방법에 대해 노드 N의 자녀 노드 N_n, …, N이 존재하며, 각 노드_i N은₁ P에 의해_i 라벨링된다.노드는 다른 메서드와 관련된N의 자녀와 구별하기 위해 호로 결합됩니다.

문제 P에 의해 라벨이 붙여진 노드 N은, 아무것도 없는 경우(즉, P가 「팩트」인 경우)의 형식 P의 방법이 있으면 성공 노드이다.P를 해결하는 방법이 없는 경우 노드는 장애 노드입니다.

같은 아크로 결합된 노드 N의 모든 자녀가 성공 노드라면 노드 N도 성공 노드이다.그렇지 않으면 노드가 장애 노드입니다.

검색 전략

및/또는 트리는 문제 해결을 위한 검색 공간만 지정합니다.공간 검색을 위한 다양한 검색 전략이 가능합니다.여기에는 솔루션의 만족도에 대한 측정값을 사용하여 나무 깊이 우선, 너비 우선 또는 최적 우선을 검색하는 작업이 포함됩니다.검색 전략은 순차적으로 한 번에 하나의 노드를 검색 또는 생성하거나 병렬로 여러 노드를 검색 또는 생성하는 것입니다.

논리 프로그래밍과의 관계

트리 생성에 사용되는 방법은 (변수가 없는) 명제 논리 프로그램입니다.변수를 포함하는 논리 프로그램의 경우, 연결 하위 문제의 해결 방법이 호환되어야 합니다.이 복잡성에 따라 순차 및/또는 트리의 병렬 검색 전략은 논리 프로그램을 실행하기 위한 계산 모델을 제공한다.

2인용 게임과의 관계

또한 트리는 2인용 게임의 검색 공간을 나타내기 위해 사용할 수도 있습니다.이러한 트리의 루트 노드는 게임의 초기 상태부터 시작되는 플레이어 중 한 명이 게임에서 승리하는 문제를 나타냅니다.특정 플레이 상태에서 게임에 당첨된 플레이어의 문제 P에 의해 라벨링된 노드 N이 주어졌을 때, 대응하는 모든 상대편 움직임에 대응하는 단일 세트의 결합 자녀 노드가 존재한다.이들 자녀 노드 각각에 대해 플레이어의 모든 방어 움직임에 대응하는 일련의 비연계 자녀 노드가 존재합니다.

알고리즘의 증명 번호 검색 패밀리로 게임 트리를 해결하려면 게임 트리를 및/또는 트리에 매핑해야 합니다.MAX 노드(즉, 플레이어가 이동하도록 최대화)는 OR 노드로 표현되며, MIN 노드는 AND 노드에 매핑됩니다.매핑은 검색이 2진수 목표만으로 이루어질 때 가능하며, 이는 보통 "이동하는 플레이어가 게임에서 승리한다"는 것입니다.

참고 문헌

• Luger, George F.; Stubblefield, William A. (1993). Artificial intelligence: structures and strategies for complex problem solving (2 ed.). The Benjamin/Cummings. ISBN 978-0-8053-4785-2. Retrieved 28 February 2013.
• Nilsson, Nils J. (1998). Artificial Intelligence: A New Synthesis. Morgan Kaufmann. ISBN 978-1-55860-467-4. Retrieved 28 February 2013.