熱線：021-5161-9676 |
熱線：021-5161-9676 |
２．１０ 與／或樹表示法 ７５ 圖２．２９ 與／或樹 用與／或樹 來 表示，即 在解 決 大多 數(shù) 問題 時，對原 問 題的 分 解與變換是相結(jié)合的。氮吹儀價格 在與／或樹 中，其根 節(jié)點 對 應(yīng)著 待求 解的原始問題。 ４． 端節(jié)點與終止節(jié)點 在與／或樹中，沒有子節(jié)點的節(jié)點稱為端節(jié)點；本原問題 所對應(yīng)的節(jié) 點稱 為 終 止 節(jié) 點。可 見，終止 節(jié) 點 一 定 是端 節(jié) 點，但端節(jié)點卻不一定是終止節(jié)點。 ５． 可解節(jié)點與不可解節(jié)點 在與／或樹中，滿足以下三個條件之一的節(jié)點為可解節(jié)點： （１） 該節(jié)點是一個終止節(jié)點。 （２） 該節(jié)點是一個“或”節(jié)點，且其子節(jié)點中至少有一個為可解節(jié)點。 （３） 該節(jié)點是一個“與”節(jié)點，且其子節(jié)點全部為可解節(jié)點。 同樣，滿足下列條件之一的節(jié)點為不可解節(jié)點： （１） 該節(jié)點是一個端節(jié)點，但卻不是終止節(jié)點。 圖２．３０ 解樹 （２） 該節(jié) 點 是一 個“或”節(jié)點，但其 子 節(jié) 點中 沒有一個是可解節(jié)點。 （３） 該節(jié)點是“與”節(jié)點，且其子節(jié)點 中至少有 一個為不可解節(jié)點。
６． 解樹 解樹是一 個 由 可 解 節(jié) 點 構(gòu) 成，并 且 可 由 這 些 可解節(jié)點推出初始 節(jié)點（它 對應(yīng) 著原始 問題）也為 可解節(jié) 點 的 子 樹。在 解 樹 中 一 定 包 含 初 始 節(jié) 點。 例如，在圖２．３０ 所 給出 的與／或樹 中，用 粗線 表示 的子樹就是它的一個解樹。該圖中 的節(jié)點 Ｐ 為原 始問題節(jié) 點，標 有 ｔ的 節(jié) 點 是 終 止 節(jié) 點。由 可 解 節(jié)點的定義，可以容易推知原始問題 Ｐ 為可解節(jié)點。 ２．１０．３ 用與／或樹表示問題的步驟 用與或樹表示法表示問題的步驟如下： （１） 對所要求解的問題進行分解或等價變換。 （２） 若所得的子問題不是本原問題，則繼續(xù)分解或變換，直到分解或變換為本原問題。 ７６ 第二章 知識表示方法 （３） 在分解或變換中，若是不等價的分解，則用“與樹”表示，若是等價 變換，則用“或樹” 表示。 ２．１０．４ 與／或樹表示舉例 例２．１４ 三階 Ｈａｎｏｉ塔問 題。設(shè)有 Ａ、Ｂ、Ｃ 三 個盤子（Ａ 比 Ｂ小，Ｂ比 Ｃ 小）及三 根柱 子，三 個盤子 按自 上而 下從
小 到大 的順序 穿在 １號 柱子 上，要求 把它們 全部 移到 ３號 柱子 上，而且每次只能移動一個盤子，任何時刻都不能把大的盤 子壓在小 的盤子 上面，如圖２．３１ 所示。 圖２．３１ 三階 Ｈａｎｏｉ塔問題 解 這個問題我們在前面已經(jīng)用一階謂詞邏輯法表示過了，上一節(jié)，我們又用狀態(tài)空間 表示法對二階 Ｈａｎｏｉ塔問題作過 表示 和求解。 現(xiàn)在 在嘗試 著用 與／或 樹表示 法對 它進 行表 示。 第一步，設(shè)用三元組 （ｉ，ｊ，ｋ） 表示問題在任一時刻的狀態(tài)，用“→”表示狀態(tài)的轉(zhuǎn)換。在上述三元組中，ｉ代 表盤子 Ｃ 所在 的柱子號，ｊ代表盤子 Ｂ所在的柱子號，ｋ代表盤子 Ａ 所在的柱子號。則原問題可以表示為 （１，１，１）→（３，３，３） 第二步，利用歸約方法，原問題可分解為以下三個子問題： （１） 把盤子 Ａ 和 Ｂ 移到２號柱子上的雙盤子移動問題。即 （１，１，１）→（１，２，２） （２） 把盤子 Ｃ移到３號柱子上的單盤子移動問題。即 （１，２，２）→（３，２，２） （３） 把盤子 Ａ 和 Ｂ 移到３號柱子的雙盤子移動問題。即 （３，２，２）→（３，３，３） 其中，子問題（１）和（３）都是一個二階 Ｈａｎｏｉ塔 問題，它們 都還 可以 再繼續(xù) 進行 分解；子 問題 （２）是本原問題，它已不需要再分解。 （１，１，１）→（１，２，２）又可分解為（１，１，１）→（１，１，３）、（１，１，
３）→（１，２，３）和（１，２，３）→（１， ２，２）三個本原問題；（３，２，２）→（３，３，３）又可分解為（３，２，２）→（３，２，１）、（３，２，１）→（３，３，１）和 ２．１０ 與／或樹表示法 ７７ （３，３，１）→（３，３，３）三個本原問題。 第三步：根據(jù)分解與變換情況畫出與／或樹。如圖２．３２所示。 圖２．３２ 三階 Ｈａｎｏｉ塔的與／或樹 圖２．３２所示的與／或樹是對三階 Ｈａｎｏｉ塔問題分解過程的圖示說明。在該與／或樹中， 有７個終止節(jié)點，它們分別對應(yīng)著７個本原問題。如果把這些本原問題從左至右排列起來， 即得到了原始問題的解： （１，１，１）→（１，１，３） （１，１，３）→（１，２，３） （１，２，３）→（１，２，２） （１，２，２）→（３，２，２） （３，２，２）→（３，２，１） （３，２，１）→（３，３，１） （３，３，１）→（３，３，３） 知識表示是人工智能研究的主要問題之一，也是 利用 人工智 能求 解實際 問題 的必 經(jīng)之 路。本章討論了知識表示常用的９種方法，針對每一 種方法，都討論了它適于表示的知識種 類，特別是討論了表示知識的步驟和方法，并通過舉例對這些步驟和方法進行了說明，使得知 識表示的可操作性更強、更實用。學(xué)習(xí)者通過本章，可以克服在表示知識時所遇到的困難。 習(xí) 題 二 ２．１ 什么是知識？它有哪些特性？有哪幾種分類方法？
