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