與-或樹

與或樹（and–or tree）是一種圖形表示法，用以呈現將問題（或目標）歸約為子問題（或子目標）的合取（conjunctions）與選取（disjunctions）。

範例

與或樹：

代表使用目標歸約法解決問題 P 的搜尋空間：

P 若 Q 與 R

P 若 S

Q 若 T

Q 若 U

定義

給定一個初始問題 P₀ 及一組形式如下的問題解決方法：

P 若 P₁ 且 … 且 Pn

其相關的與或樹是一組帶有標記的節點，其特性如下：

樹的根節點是一個標記為 P₀ 的節點。
對於每個標記為問題或子問題 P 的節點 N，以及對於每個形式為 P 若 P₁ 且 ... 且 Pn 的方法，節點 N 都存在一組子節點 N₁, ..., Nn，使得每個節點 Ni 都標記為 Pi。這些節點由一個弧線進行合取連接，以區別於可能與其他方法相關聯的 N 的子節點。

一個標記為問題 P 的節點 N，若存在一個形式為 P 若無 (P if nothing) 的方法（即 P 是一個「事實」），則該節點為成功節點。若沒有解決 P 的方法，則該節點為失敗節點。

若一個節點 N 的所有由同一弧線合取連接的子節點都是成功節點，則節點 N 也是一個成功節點。否則，該節點為失敗節點。

搜尋策略

與或樹只定義了解決問題的搜尋空間。搜尋此空間可以採用不同的搜尋策略。這些策略包括使用某種衡量解方優劣的指標，進行深度優先、廣度優先或最佳優先的樹搜尋。搜尋策略可以是循序的，一次搜尋或生成一個節點；也可以是平行的，平行地搜尋或生成數個節點。

與邏輯程式設計的關係

用於生成與或樹的方法是命題邏輯程式（不含變數）。在包含變數的邏輯程式中，合取子問題的解必須相容。考慮到這個複雜性，與或樹的循序與平行搜尋策略為執行邏輯程式提供了一個計算模型。

與雙人博弈的關係

與或樹也可用於表示雙人博弈的搜尋空間。此類樹的根節點代表了其中一位玩家從遊戲初始狀態開始，到贏得博弈的問題。給定一個節點 N，其標記為玩家從特定局勢 P 贏得博弈的問題，則存在一組合取的子節點，對應於對手所有可能的應對走步。對於這些子節點中的每一個，都存在一組非合取的子節點，對應於該玩家所有可能的防禦走步。

為了使用證明數搜尋系列的演算法來解決博弈樹，博弈樹需要被對應到與或樹。MAX 節點（即輪到最大化方走步）表示為 OR 節點，MIN 節點則對應到 AND 節點。當搜尋只針對一個二元目標（通常是「輪到走步的玩家贏得博弈」）時，這種對應是可行的。

參考書目

Russell, S. and Norvig, P., 2021. Artificial Intelligence: a modern approach, 4th US ed. University of California, Berkeley, p 141.

Category:樹 (資料結構) Category:人工智慧