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