２．１０ 與／或樹表示法 ７５  圖２．２９ 與／或樹 用與／或樹 來 表示，即 在解 決 大多 數 問題 時，對原 問 題的 分 解與變換是相結合的。氮吹儀價格 在與／或樹 中，其根 節點 對 應著 待求 解的原始問題。 ４． 端節點與終止節點 在與／或樹中，沒有子節點的節點稱為端節點；本原問題 所對應的節 點稱 為 終 止 節 點。可 見，終止 節 點 一 定 是端 節 點，但端節點卻不一定是終止節點。 ５． 可解節點與不可解節點 在與／或樹中，滿足以下三個條件之一的節點為可解節點： （１） 該節點是一個終止節點。 （２） 該節點是一個“或”節點，且其子節點中至少有一個為可解節點。 （３） 該節點是一個“與”節點，且其子節點全部為可解節點。 同樣，滿足下列條件之一的節點為不可解節點： （１） 該節點是一個端節點，但卻不是終止節點。 圖２．３０ 解樹 （２） 該節 點 是一 個“或”節點，但其 子 節 點中 沒有一個是可解節點。 （３） 該節點是“與”節點，且其子節點 中至少有 一個為不可解節點。

 ６． 解樹 解樹是一 個 由 可 解 節 點 構 成，并 且 可 由 這 些 可解節點推出初始 節點（它 對應 著原始 問題）也為 可解節 點 的 子 樹。在 解 樹 中 一 定 包 含 初 始 節 點。 例如，在圖２．３０ 所 給出 的與／或樹 中，用 粗線 表示 的子樹就是它的一個解樹。該圖中 的節點 Ｐ 為原 始問題節 點，標 有 ｔ的 節 點 是 終 止 節 點。由 可 解 節點的定義，可以容易推知原始問題 Ｐ 為可解節點。 ２．１０．３ 用與／或樹表示問題的步驟 用與或樹表示法表示問題的步驟如下： （１） 對所要求解的問題進行分解或等價變換。 （２） 若所得的子問題不是本原問題，則繼續分解或變換，直到分解或變換為本原問題。 ７６ 第二章 知識表示方法  （３） 在分解或變換中，若是不等價的分解，則用“與樹”表示，若是等價 變換，則用“或樹” 表示。 ２．１０．４ 與／或樹表示舉例 例２．１４ 三階 Ｈａｎｏｉ塔問 題。設有 Ａ、Ｂ、Ｃ 三 個盤子（Ａ 比 Ｂ小，Ｂ比 Ｃ 小）及三 根柱 子，三 個盤子 按自 上而 下從

小 到大 的順序 穿在 １號 柱子 上，要求 把它們 全部 移到 ３號 柱子 上，而且每次只能移動一個盤子，任何時刻都不能把大的盤 子壓在小 的盤子 上面，如圖２．３１ 所示。 圖２．３１ 三階 Ｈａｎｏｉ塔問題 解 這個問題我們在前面已經用一階謂詞邏輯法表示過了，上一節，我們又用狀態空間 表示法對二階 Ｈａｎｏｉ塔問題作過 表示 和求解。 現在 在嘗試 著用 與／或 樹表示 法對 它進 行表 示。 第一步，設用三元組 （ｉ，ｊ，ｋ） 表示問題在任一時刻的狀態，用“→”表示狀態的轉換。在上述三元組中，ｉ代 表盤子 Ｃ 所在 的柱子號，ｊ代表盤子 Ｂ所在的柱子號，ｋ代表盤子 Ａ 所在的柱子號。則原問題可以表示為 （１，１，１）→（３，３，３） 第二步，利用歸約方法，原問題可分解為以下三個子問題： （１） 把盤子 Ａ 和 Ｂ 移到２號柱子上的雙盤子移動問題。即 （１，１，１）→（１，２，２） （２） 把盤子 Ｃ移到３號柱子上的單盤子移動問題。即 （１，２，２）→（３，２，２） （３） 把盤子 Ａ 和 Ｂ 移到３號柱子的雙盤子移動問題。即 （３，２，２）→（３，３，３） 其中，子問題（１）和（３）都是一個二階 Ｈａｎｏｉ塔 問題，它們 都還 可以 再繼續 進行 分解；子 問題 （２）是本原問題，它已不需要再分解。 （１，１，１）→（１，２，２）又可分解為（１，１，１）→（１，１，３）、（１，１，

３）→（１，２，３）和（１，２，３）→（１， ２，２）三個本原問題；（３，２，２）→（３，３，３）又可分解為（３，２，２）→（３，２，１）、（３，２，１）→（３，３，１）和 ２．１０ 與／或樹表示法 ７７  （３，３，１）→（３，３，３）三個本原問題。 第三步：根據分解與變換情況畫出與／或樹。如圖２．３２所示。 圖２．３２ 三階 Ｈａｎｏｉ塔的與／或樹 圖２．３２所示的與／或樹是對三階 Ｈａｎｏｉ塔問題分解過程的圖示說明。在該與／或樹中， 有７個終止節點，它們分別對應著７個本原問題。如果把這些本原問題從左至右排列起來， 即得到了原始問題的解： （１，１，１）→（１，１，３） （１，１，３）→（１，２，３） （１，２，３）→（１，２，２） （１，２，２）→（３，２，２） （３，２，２）→（３，２，１） （３，２，１）→（３，３，１） （３，３，１）→（３，３，３） 知識表示是人工智能研究的主要問題之一，也是 利用 人工智 能求 解實際 問題 的必 經之 路。本章討論了知識表示常用的９種方法，針對每一 種方法，都討論了它適于表示的知識種 類，特別是討論了表示知識的步驟和方法，并通過舉例對這些步驟和方法進行了說明，使得知 識表示的可操作性更強、更實用。學習者通過本章，可以克服在表示知識時所遇到的困難。 習 題 二 ２．１ 什么是知識？它有哪些特性？有哪幾種分類方法？