【正文】 而有些題目，這些常規(guī)的優(yōu)化方法很難有用武之地。 但還給出物品位置之間的限制（例如：如果 1放在 3則 2不能放在 1）。 部分搜索 +匹配的方法已經(jīng)在很多題目中得到了應(yīng)用。 搜索的時(shí)間復(fù)雜度為 O(n!)。 只有 4個(gè)數(shù)據(jù)可以在時(shí)限內(nèi)出解，另外 6個(gè)如果卡時(shí)，有 2個(gè)也可以得到最優(yōu)解。 如果，炸彈 i炸不到 S， 則 MaxT[i][S]=S1。 部分搜索＋匹配算法體現(xiàn)了搜索與其他方法的有機(jī)結(jié)合，充分發(fā)揮兩者的長(zhǎng)處，相互彌補(bǔ)對(duì)方的不足，這就是其高效的主要原因所在。 最簡(jiǎn)單的搜索 優(yōu)化的搜索 進(jìn)一步優(yōu)化的搜索 1 2 3 4 TimeOver TimeOver 5 6 TimeOver 7 TimeOver TimeOver 8 TimeOver 9 TimeOver 10 TimeOver 總結(jié)：本文中的兩個(gè)例子都可以應(yīng)用部分搜索＋匹配的方法高效解決。 因此，在枚舉劃分長(zhǎng)度時(shí)，可以通過以前的劃分和匹配情況（被匹配的邊），用 O(n2)的時(shí)間復(fù)雜度的寬度優(yōu)先搜索計(jì)算出下一個(gè)劃分的最大長(zhǎng)度maxL， 顯然下一個(gè)劃分的長(zhǎng)度在 [1， maxL]都一定可以找到可行的匹配。左邊第 i個(gè)點(diǎn)到右邊第 j個(gè)點(diǎn)有邊的條件即： C[Si][Ti][j]。 面對(duì)此類問題，一般只有搜索策略。搜索的優(yōu)勢(shì)在于應(yīng)用性廣，可以克服復(fù)雜的情況，匹配算法的優(yōu)勢(shì)在于效率高。 于是我們需要利用很多技巧來提高效率： 可行性剪枝， 最優(yōu)性剪枝， 調(diào)整搜索順序， 等方法都很有用，在它們的幫助下，我們可以大大提高搜索的效率。 求一組可行解，或給每一種對(duì)應(yīng)關(guān)系一個(gè)權(quán)，求滿足條件的最優(yōu)解。 一個(gè)部分搜索 +匹配算法的經(jīng)典例子。 即使加上優(yōu)化，程序效率也不是很高。 優(yōu)化： 優(yōu)化可以通過可行性和最優(yōu)性兩方面分析。 求 MaxT[i][S]可以用動(dòng)態(tài)規(guī)劃的方法解決。 因此，在搜索問題中靈活地應(yīng)用部分搜索的方法，往往可以創(chuàng)造出奇效。 甚至對(duì) n=200的隨機(jī)數(shù)據(jù)，也可以在瞬間出解，可見程序的效率有了很大的提高。 進(jìn)一步優(yōu)化： 優(yōu)化二雖然排除了許多不必要