第二章 問題歸約法.

1、第二章第二章 問題歸約法問題歸約法 Problem Reduction Representation問題歸約法v 問題歸約（問題歸約（Problem Reduction）是另外一種是另外一種基于狀態(tài)空間基于狀態(tài)空間的問題描述與求解方法的問題描述與求解方法已知問題的描述，通過一系列已知問題的描述，通過一系列變換變換把此問題變?yōu)橐粋€把此問題變?yōu)橐粋€子問題集合子問題集合這些子問題的解可以這些子問題的解可以直接得到（本原問題）直接得到（本原問題），從而解，從而解決了初始問題決了初始問題問題歸約法v 問題歸約法的組成部分問題歸約法的組成部分一個初始問題描述；一個初始問題描述；一套把問題變換為子問題的一套

2、把問題變換為子問題的操作符操作符；一套一套本原問題本原問題描述。描述。( (本原問題本原問題: :不能再分解或變換且不能再分解或變換且直接可解的子問題直接可解的子問題) )v 問題歸約的實(shí)質(zhì)：問題歸約的實(shí)質(zhì)：從目標(biāo)（要解決的問題）出發(fā)從目標(biāo)（要解決的問題）出發(fā)逆向推理逆向推理，建立子問題，建立子問題以及子問題的子問題，直到最后把初始問題歸約為以及子問題的子問題，直到最后把初始問題歸約為一一個本原問題集合個本原問題集合。問題歸約法v 問題歸約法舉例：問題歸約法舉例：漢諾塔問題（漢諾塔問題（ Hanoi ） p 從從1移到移到3p 每次移動一個盤子每次移動一個盤子p 大盤在下小盤在上大盤在下小盤在

3、上123CBA初始狀態(tài)（初始狀態(tài)（111111）目標(biāo)狀態(tài)（目標(biāo)狀態(tài)（333333）CBA漢諾塔問題v 原始問題可以歸約為下列原始問題可以歸約為下列3 3個子問題：個子問題：子問題子問題1 1：子問題子問題2 2：子問題子問題3 3：漢諾塔問題v 歸約過程（歸約過程（3 3個圓盤）個圓盤）漢諾塔問題v 漢諾塔問題歸約圖漢諾塔問題歸約圖本原問題本原問題本原問題本原問題與或圖與或圖CBA梵塔問題的答案v一圓盤問題要走幾步，兩圓盤問題要走幾步？三個、四個、六十四個圓盤呢？圓盤個數(shù)圓盤個數(shù)移動圓盤次數(shù)移動圓盤次數(shù)11222-1=3323-1=764264-1264-1=18446744073709551

4、615 一年一年=365*24*60*60=31536000秒秒1844674407370955161531536000584942417355年年 問題歸約法v 與或圖表示：與或圖表示：用一個類似于圖的結(jié)構(gòu)來表示把問題歸約為用一個類似于圖的結(jié)構(gòu)來表示把問題歸約為后繼問題的替換集合。后繼問題的替換集合。與圖：與圖：把一個復(fù)雜問題把一個復(fù)雜問題分解為若干個較為簡單的分解為若干個較為簡單的子問題，形成子問題，形成“與與”樹。樹?；驁D：或圖：把原問題變換為把原問題變換為若干個較為容易求解的新若干個較為容易求解的新問題，形成問題，形成“或或”樹。樹。問題歸約法v 與或圖表示：與或圖表示：BCDEFGA

5、HMBCDEFGAN子問題替代集合結(jié)構(gòu)圖子問題替代集合結(jié)構(gòu)圖與或圖與或圖問題歸約法v 一些關(guān)于與或圖的術(shù)語一些關(guān)于與或圖的術(shù)語起始節(jié)點(diǎn)起始節(jié)點(diǎn)對應(yīng)于原對應(yīng)于原始問題描始問題描述述終葉節(jié)點(diǎn)對應(yīng)于本原問題終葉節(jié)點(diǎn)對應(yīng)于本原問題問題歸約法v 與或圖的構(gòu)成規(guī)則與或圖的構(gòu)成規(guī)則 1 1）與或圖中的每個節(jié)點(diǎn)代表一）與或圖中的每個節(jié)點(diǎn)代表一個要解決的單一問題或問題集合。個要解決的單一問題或問題集合。圖中所含起始節(jié)點(diǎn)對應(yīng)于原始問圖中所含起始節(jié)點(diǎn)對應(yīng)于原始問題題A A。 2 2）對應(yīng)于本原問題的節(jié)點(diǎn)稱為）對應(yīng)于本原問題的節(jié)點(diǎn)稱為終葉節(jié)點(diǎn)，它沒有后繼節(jié)點(diǎn)。終葉節(jié)點(diǎn)，它沒有后繼節(jié)點(diǎn)。 3 3）對于把算符應(yīng)用于問題）

6、對于把算符應(yīng)用于問題A A的每的每種可能情況，都把問題變換為一種可能情況，都把問題變換為一個子問題集合；有向弧線自個子問題集合；有向弧線自A A指指向后繼節(jié)點(diǎn)表示所求得的子問題向后繼節(jié)點(diǎn)表示所求得的子問題集合。集合。HMBCDEFGAN問題歸約法v 與或圖的構(gòu)成規(guī)則與或圖的構(gòu)成規(guī)則 4 4）一般對于代表兩個或兩個以上）一般對于代表兩個或兩個以上子問題集合的每個節(jié)點(diǎn)，有向弧子問題集合的每個節(jié)點(diǎn)，有向弧線從此節(jié)點(diǎn)指向次子問題集合中線從此節(jié)點(diǎn)指向次子問題集合中的各個節(jié)點(diǎn)。由于只有當(dāng)集合中的各個節(jié)點(diǎn)。由于只有當(dāng)集合中所有項(xiàng)都有解時，這個子問題的所有項(xiàng)都有解時，這個子問題的集合才能獲得解答，所以這些子集

7、合才能獲得解答，所以這些子問題節(jié)點(diǎn)叫做與節(jié)點(diǎn)。問題節(jié)點(diǎn)叫做與節(jié)點(diǎn)。 5 5）特殊情況下，當(dāng)只有一個算符）特殊情況下，當(dāng)只有一個算符可應(yīng)用于問題可應(yīng)用于問題A A，而且這個算符產(chǎn)，而且這個算符產(chǎn)生具有一個以上子問題的某個集生具有一個以上子問題的某個集合時，由上述規(guī)則合時，由上述規(guī)則3 3）和規(guī)則）和規(guī)則4 4）所產(chǎn)生的圖可以得到簡化。所產(chǎn)生的圖可以得到簡化。MDEFAADEF簡化簡化問題歸約法v與或圖的搜索：與或圖的搜索：目的在于表明起始節(jié)點(diǎn)是有解的。目的在于表明起始節(jié)點(diǎn)是有解的。v可解節(jié)點(diǎn)可解節(jié)點(diǎn)終葉節(jié)點(diǎn)是可解節(jié)點(diǎn)（對應(yīng)于本原問題）。終葉節(jié)點(diǎn)是可解節(jié)點(diǎn)（對應(yīng)于本原問題）。如果某個非終葉節(jié)點(diǎn)含有

8、如果某個非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)或后繼節(jié)點(diǎn)，那么只要當(dāng)其后，那么只要當(dā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)，那么只有當(dāng)其后，那么只有當(dāng)其后繼節(jié)點(diǎn)全部為可解時，此非終葉節(jié)點(diǎn)才是可解的。繼節(jié)點(diǎn)全部為可解時，此非終葉節(jié)點(diǎn)才是可解的。問題歸約法v不可解節(jié)點(diǎn)不可解節(jié)點(diǎn)沒有后裔的非終葉節(jié)點(diǎn)為不可解節(jié)點(diǎn)。沒有后裔的非終葉節(jié)點(diǎn)為不可解節(jié)點(diǎn)。 如果某個非終葉節(jié)點(diǎn)含有如果某個非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)或后繼節(jié)點(diǎn)，那么只有當(dāng)其，那么只有當(dāng)其全全部后裔為不可解時部后裔為不可解時，此非終葉節(jié)點(diǎn)才是不可解的。，此非終葉節(jié)點(diǎn)才是不可解的。 如果某個非終葉節(jié)點(diǎn)含有如果某個非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)與后繼節(jié)點(diǎn)，那么只要當(dāng)其，那么只要當(dāng)其后后裔至少有一個為不可解時裔至少有一個為不可解時，此非終葉節(jié)點(diǎn)才是不可解的。，此非終葉節(jié)點(diǎn)才是不可解的。v解樹解樹由可解節(jié)點(diǎn)所構(gòu)成，并且由這些可解節(jié)點(diǎn)可推出初始節(jié)由可解節(jié)點(diǎn)所構(gòu)成，并且由這些可解節(jié)點(diǎn)可推出初始節(jié)點(diǎn)為可解節(jié)點(diǎn)的子樹稱為解樹。點(diǎn)為可解節(jié)點(diǎn)的子樹稱為解樹。解樹中一定包含初始節(jié)點(diǎn)，它對應(yīng)于原始