傳說(shuō)中的算法寶典

1、一共考5道題，每道題2問(wèn)1、 （重要）設(shè)L為n元數(shù)組，其中的數(shù)已按增序排列，另給定數(shù)值x，試采用二分搜索技術(shù)設(shè)計(jì)算法，查找數(shù)值是否在L中。要求若x在L中，則輸出j，使L(j)=x；其x不在L中，則輸出0。并證明，在最壞情況下，對(duì)所有n元數(shù)組L(n1)，二分搜索算法將數(shù)值x與L中元素比較次數(shù)為。解：比較次數(shù)：由于是2分搜索，每次比較或者成功，或者將搜索范圍縮小一半。因此最多比較次數(shù)為2的對(duì)數(shù)，又當(dāng)時(shí)，至少比較1次，所以比較次數(shù)不超過(guò)。二、滿足三角不等式的TSP問(wèn)題是否是NPC？為什么？解：證明思路，將哈密頓回路HC問(wèn)題多項(xiàng)式變換到TSP問(wèn)題:，且變換到TSP問(wèn)題的實(shí)例是滿足三角不等式的。因?yàn)?，?/p>

2、滿足三角不等式的。多項(xiàng)式變換：設(shè)HC的實(shí)例為，據(jù)此構(gòu)造TS實(shí)例，兩個(gè)頂點(diǎn)之間的距離定義為，并設(shè)TSP旅游界值為。易知這個(gè)變換是多項(xiàng)式的。若HC存在一條哈密頓回路，則這條回路在上的長(zhǎng)度必為B，而是最短旅游的界值，故這條回路是滿足實(shí)例的一個(gè)TSP旅游。若存在一個(gè)滿足B的TSP旅游，則該旅游必經(jīng)過(guò)長(zhǎng)度為1的邊，而這些邊均在G上，因此這個(gè)TSP旅游在G上是一條HC回路。這樣就將，而。變換到的TSP實(shí)例的邊長(zhǎng)為1或2，可知該實(shí)例滿足三角不等式，這就證明了滿足三角不等式的TSP問(wèn)題是NPC問(wèn)題。三、給定城市集合，任兩城市距離，求最小貨郎旅游。試證明滿足三角不等式的貨郎優(yōu)化問(wèn)題為NP-hard。（重要）求滿

3、足三角不等式的TSP的近似算法，并設(shè)計(jì)出能解答該問(wèn)題的多項(xiàng)式時(shí)間近似算法A，其近似性能比為。證明：即滿足三角不等式的TSP問(wèn)題。證明思路，將哈密頓回路HC問(wèn)題多項(xiàng)式變換到TSP問(wèn)題:且變換到TSP問(wèn)題的實(shí)例是滿足三角不等式的（見(jiàn)第1題）。因?yàn)?，故滿足三角不等式的TSP問(wèn)題是NPC問(wèn)題。設(shè)存在TSP優(yōu)化問(wèn)題求解算法，設(shè)計(jì)TSP判定問(wèn)題的算法如下：對(duì)于給定TSP判定問(wèn)題的實(shí)例：，調(diào)用，求得城市排列：，若，則回答yes，否則回答no。若為多項(xiàng)式算法，則上述算法能夠在多項(xiàng)式時(shí)間內(nèi)解答，故TSP判定問(wèn)題可以圖靈歸約到TSP優(yōu)化問(wèn)題，而已知TSP判定問(wèn)題是NPC的，所以TSP優(yōu)化問(wèn)題是NPH的。算法：對(duì)調(diào)

4、用最小支撐樹(shù)（有權(quán)圖權(quán)值之和最小的連通子圖）算法，得到樹(shù)設(shè)的奇數(shù)頂點(diǎn)為，在中求點(diǎn)集的最小對(duì)集，將加入中，形成歐拉圖在中求歐拉回路抄近路得到證明：因?yàn)門SP是回路，最小生成樹(shù)是樹(shù)，所以又對(duì)于所有最小對(duì)集的兩條邊，小于這四點(diǎn)相連的最小TSP旅游距離，所以，4、 對(duì)于背包問(wèn)題 證明：(1) 、當(dāng)時(shí)，該問(wèn)題不存在多項(xiàng)式時(shí)間絕對(duì)近似算法(2) 、背包問(wèn)題存在絕對(duì)近似性能比的多項(xiàng)式時(shí)間近似算法證明:(1)假設(shè)存在A,則存在常數(shù)（2）：實(shí)例為價(jià)值，為重量，為背包容量詢問(wèn)：求向量，使。算法：將物體按照排序，使從1到n將物體裝包，直到不能裝為止，記其總價(jià)值和為取復(fù)雜性：步驟，步驟，故總的時(shí)間復(fù)雜性為近似性能比：

5、設(shè)包含物體價(jià)值為，則 ， 而， 故， 即5、 n個(gè)整數(shù)，正整數(shù)m。求向量。證明是NPC的；若，求多項(xiàng)式時(shí)間算法，證明其正確性。六、給定WPAR問(wèn)題實(shí)例：集合，對(duì)于每個(gè)有長(zhǎng)度。詢問(wèn)：是否存在子集(1) 、試?yán)脛澐諴AR是NPC問(wèn)題，證明WPAR問(wèn)題屬于NPC類；(2) 、試設(shè)計(jì)擬多項(xiàng)式算法：(a) 判斷是否存在，(b)若存在，應(yīng)給出一個(gè)滿足詢問(wèn)條件的。(3) 、針對(duì)如下實(shí)例，說(shuō)明你設(shè)計(jì)算法的執(zhí)行過(guò)程解：(1)、證明WPAR是NPC證明：(將)設(shè)PAR實(shí)例為，構(gòu)造WPAR實(shí)例：，其中若PAR中存在一個(gè)劃分，使得，則在WPAR中，而。因此，必存在使若WPAR中存在使，則。分析元素構(gòu)成，中必含不含，

6、而中必含，不含。則有，即A中存在一個(gè)劃分。又上述變換可在多項(xiàng)式時(shí)間內(nèi)進(jìn)行，因此，又，因此（2） 、設(shè)計(jì)WPAR擬多項(xiàng)式算法解：設(shè)，若B不能被3整除則無(wú)劃分；若B能被3整除，則設(shè)計(jì)表t為n行，列。，若，則最終回答yes，否則no 若則若，則求解算法：記（3） 、用設(shè)計(jì)算法求解實(shí)例j：i0123456789101TT2TTTT3TTTTTT4TTTTTTT5TTTTTTTT七、（重要）給定2SAT問(wèn)題實(shí)例，布爾變量集合，項(xiàng)集合，為U上布爾變量字母。試設(shè)計(jì)多項(xiàng)式時(shí)間算法：(1)、判定2SAT實(shí)例是否有可滿足真值指派；(2)、若有可滿足真值指派則算法給出使C滿足U的真值指派。8、 證明團(tuán)問(wèn)題屬于NPC

7、思路：已知頂點(diǎn)覆蓋，而最大獨(dú)立集問(wèn)題，故最大獨(dú)立集問(wèn)題（若是上的點(diǎn)覆蓋，則是上的最大獨(dú)立集。若是上的最大獨(dú)立集，則是上的點(diǎn)覆蓋）。又最大獨(dú)立集問(wèn)題，故(若是上的最大獨(dú)立集，則在的補(bǔ)圖上所對(duì)應(yīng)的子圖是上的團(tuán))點(diǎn)覆蓋：上的最小頂點(diǎn)集合，覆蓋上所有的邊；獨(dú)立集：上的點(diǎn)集合，中任兩點(diǎn)之間無(wú)邊；補(bǔ)圖：（？）團(tuán)：上最大完全子圖9、 TSP判定問(wèn)題是數(shù)問(wèn)題嗎？是否存在擬多項(xiàng)式算法？為什么？答：TSP判定問(wèn)題是數(shù)問(wèn)題，因?yàn)槿蝺沙鞘虚g的距離及界值沒(méi)有任何約束。因?yàn)榭梢詫?，從而證明，而有限制，事實(shí)上,故不受限制的原始TSP問(wèn)題是強(qiáng)NPC。因此TSP問(wèn)題不存在擬多項(xiàng)式時(shí)間算法。10、 集合覆蓋問(wèn)題T實(shí)例：為子集族詢

8、問(wèn)：求，使最小求證：時(shí)，上述問(wèn)題無(wú)多項(xiàng)式時(shí)間絕對(duì)近似算法證明：若限制,則集合覆蓋問(wèn)題變?yōu)閄3C問(wèn)題。而，故集合覆蓋問(wèn)題是NPC問(wèn)題。(反證法)設(shè)存在多項(xiàng)式時(shí)間絕對(duì)算法A，有現(xiàn)將復(fù)制份到，易知，在上應(yīng)用算法A有，故：(之所以取整，是因?yàn)榧细采w問(wèn)題是求最小值問(wèn)題）因此可以構(gòu)造算法：（1）、；（2）、對(duì)調(diào)用A，得子集族的子集及；（3）、計(jì)算即為實(shí)例的最優(yōu)解值因?yàn)槭嵌囗?xiàng)式的，所以也是多項(xiàng)式的，這就多項(xiàng)式時(shí)間回答了集合覆蓋問(wèn)題。而我們已知集合覆蓋問(wèn)題是NPC，這與矛盾，故假設(shè)不成立。即不存在多項(xiàng)式時(shí)間絕對(duì)近似算法。十一、假設(shè)一臺(tái)處理機(jī)可連續(xù)加工任務(wù)。但在每個(gè)時(shí)刻，只允許加工一個(gè)任務(wù)，含有待加工任務(wù)集合

9、。其中所有任務(wù)都有相同的加工最早起始時(shí)間，但它們所需要的加工時(shí)間和加工最遲完成時(shí)間不同，即對(duì)于一個(gè)任務(wù)，其所需加工時(shí)間為，加工最遲完成時(shí)間為且，試設(shè)計(jì)一個(gè)多項(xiàng)式時(shí)間算法，給出任務(wù)集合的排工表，使能按要求完成的任務(wù)數(shù)達(dá)到最大。要求證明你所設(shè)計(jì)算法的正確性，并分析其時(shí)間復(fù)雜性，并通過(guò)下述實(shí)例說(shuō)明算法的運(yùn)行情況：（重要）算法，將所有任務(wù)按其結(jié)束時(shí)間由小到大排列，若滿足時(shí)，有。令空，S為排工表。若，轉(zhuǎn)設(shè)對(duì)個(gè)任務(wù)，已經(jīng)安排了個(gè)任務(wù)加工。則對(duì)第個(gè)任務(wù)，只要有,則將其安排為第個(gè)任務(wù)：即，然后轉(zhuǎn)若,則從已安排的個(gè)任務(wù)中，另?yè)褚粋€(gè)加工時(shí)間最長(zhǎng)的任務(wù)，若，則將從中移出，將后的任務(wù)前移，再把并入，轉(zhuǎn)否則（），k=k

10、+1, 轉(zhuǎn)完成，S即排工表。正確性：由于的排序是一定的，只需證明每一步操作都使加工時(shí)間最短，則它的加工任務(wù)最多。歸納法證明：（1） 當(dāng)時(shí)，顯然成立；（2） 假設(shè) 時(shí)正確，即若個(gè)中拔下個(gè)，且加工時(shí)間最短，下面證明時(shí)也正確。當(dāng)時(shí)，若，則安排第個(gè)任務(wù)，顯然個(gè)任務(wù)最多能安排個(gè)，且時(shí)間最短；若，則由于算法中選擇了中最長(zhǎng)的任務(wù)，且當(dāng)時(shí)用代替，使總加工時(shí)間，故仍滿足加工時(shí)間最短，任務(wù)最多。綜上所述，把個(gè)任務(wù)排完時(shí)，算法是正確的。復(fù)雜性：設(shè)有個(gè)任務(wù)，則最壞情況下對(duì)每個(gè)加工任務(wù)都有，從而從中查找最長(zhǎng)加工時(shí)間任務(wù)，則一次查找為，每個(gè)任務(wù)都查找為，排序加工任務(wù)為，因此總的復(fù)雜度為。算法的實(shí)例運(yùn)行情況：S=t1 k=

11、1 m=1 Ls=6S=t2 Ls+L2=10d2 Ti=T1, LiL2,Ti out, T2 in k=2, Ls=4S=t2t3ls+L3=6d5,Ti=T4,LiL5,k=5,Ls=11S=t2t3t4t6Ls+L6=13d6,k=6,Ls=13,m=4K=6,putout S=t2t3t4t6十二、排工問(wèn)題（區(qū)間排工）實(shí)例：只有一臺(tái)機(jī)器，n個(gè)任務(wù)，。對(duì)于每任務(wù)有加工起始時(shí)間，終止時(shí)間，加工長(zhǎng)度詢問(wèn)：加工表，表示的真正開(kāi)始。使按時(shí)完成。時(shí)，在之前開(kāi)始，或，在之前開(kāi)始。（兩個(gè)任務(wù)不同時(shí)開(kāi)始進(jìn)行）試證：(1)、問(wèn)題（2） 、若限制，稱為限制排工問(wèn)題，試設(shè)計(jì)一多項(xiàng)式算法，限制排工任務(wù)數(shù)目最大

12、，再證明算法的正確性，分析其復(fù)雜性。解：（1）見(jiàn)教材，試圖將區(qū)間排工。設(shè)實(shí)例，對(duì)每一個(gè)有均為整數(shù)，。根據(jù)問(wèn)題實(shí)例構(gòu)造排工問(wèn)題實(shí)例：， 我們不考慮B為奇數(shù)的情況，因?yàn)锽為奇數(shù)時(shí)，PAR不存在一個(gè)劃分。若存在一個(gè)劃分，則可如此排工：將中所對(duì)應(yīng)的任務(wù)安排在E之前完成，將所對(duì)應(yīng)的任務(wù)安排在E之后完成。由此排工問(wèn)題存在一個(gè)排工。若排工問(wèn)題存在一個(gè)排工，則可如此進(jìn)行劃分：將位于E之前的任務(wù)對(duì)應(yīng)的置入集合，E之后的任務(wù)所對(duì)應(yīng)的放在中。由于E之前的任務(wù)加工長(zhǎng)度為（B為偶數(shù)），E之后的任務(wù)加工長(zhǎng)度為，而，故，即存在一個(gè)劃分。因此，我們得區(qū)間排工，由于，故區(qū)間排工。(2) 、算法，將所有任務(wù)按其結(jié)束時(shí)間由小到大排

13、列，若滿足時(shí)，有。令空，S為排工表。若，轉(zhuǎn)設(shè)對(duì)個(gè)任務(wù)，已經(jīng)安排了個(gè)任務(wù)加工。則對(duì)第個(gè)任務(wù)，只要有,則將其安排為第個(gè)任務(wù)：即，然后轉(zhuǎn)若,則從已安排的個(gè)任務(wù)中，另?yè)褚粋€(gè)加工時(shí)間最長(zhǎng)的任務(wù)，若，則將從中移出，將后的任務(wù)前移，再把并入，轉(zhuǎn)否則，k=k+1, 轉(zhuǎn)完成，S即排工表。正確性：由于的排序是一定的，只需證明每一步操作都使加工時(shí)間最短，則它的加工任務(wù)最多。歸納法證明：（3） 當(dāng)時(shí)，顯然成立；（4） 假設(shè) 時(shí)正確，即若個(gè)中拔下個(gè)，且加工時(shí)間最短，下面證明時(shí)也正確。當(dāng)時(shí)，若，則安排第個(gè)任務(wù)，顯然個(gè)任務(wù)最多能安排個(gè)，且時(shí)間最短；若，則由于算法中選擇了中最長(zhǎng)的任務(wù)，且當(dāng)時(shí)用代替，使總加工時(shí)間，故仍滿足加工

14、時(shí)間最短，任務(wù)最多。綜上所述，把個(gè)任務(wù)排完時(shí)，算法是正確的。復(fù)雜性：設(shè)有個(gè)任務(wù)，則最壞情況下對(duì)每個(gè)加工任務(wù)都有，從而從中查找最長(zhǎng)加工時(shí)間任務(wù)，則一次查找為，每個(gè)任務(wù)都查找為，排序加工任務(wù)為，因此總的復(fù)雜度為。13、 給定個(gè)整數(shù)，滿足（超遞增序列），有一正整數(shù)，試設(shè)計(jì)算法，找出一維0，1向量，使得或無(wú)解。解：算法證明：因?yàn)椋匀?，必有，故?yīng)為1，否則使全為1也沒(méi)有正確答案。復(fù)雜度：易知為。14、 （1）平面圖的最大團(tuán)問(wèn)題有多項(xiàng)式時(shí)間算法嗎？Why?答：有，因?yàn)楫?dāng)在平面圖上考慮團(tuán)問(wèn)題時(shí)，任何平面圖都不會(huì)含有多于4個(gè)頂點(diǎn)的完全圖，故只需檢查所有的頂點(diǎn)個(gè)數(shù)，不超過(guò)4個(gè)子圖就能找到極大團(tuán)。因4是常數(shù)，

15、故子圖數(shù)目是多項(xiàng)式有界的。所以必有多項(xiàng)式算法。(2) 平面圖的3著色問(wèn)題有多項(xiàng)式算法嗎？Why?答：沒(méi)有，因?yàn)槲覀兛梢栽O(shè)計(jì)一個(gè)轉(zhuǎn)線軌道圖，用局部替換技術(shù)將一般圖中的交點(diǎn)處理，將其轉(zhuǎn)化為平面圖。一般圖的3著色問(wèn)題，故平面圖3著色也是NPC的，所以不存在多項(xiàng)式時(shí)間算法。15、 （重要）當(dāng)時(shí)，TSP優(yōu)化問(wèn)題是否存在的多項(xiàng)式算法？答：不存在，用反證法證明。證明：設(shè)存在常數(shù)，使，即存在算法，對(duì)TSP的任意實(shí)例有。設(shè)是哈密頓問(wèn)題任意實(shí)例，由構(gòu)造TSP問(wèn)題實(shí)例如下。 若存在哈密頓回路，則若不存在哈密頓回路，則，因此可以設(shè)計(jì)哈密頓問(wèn)題的TSP實(shí)例，調(diào)用算法由是否成立判定哈密頓是否存在解，又是多項(xiàng)式時(shí)間的，即哈

16、密頓可以多項(xiàng)式時(shí)間求解，這與矛盾。故假設(shè)不成立，TSP不存在的多項(xiàng)式算法。16、 （重要）劃分問(wèn)題的擬多項(xiàng)式時(shí)間算法，并求劃分的具體方案解：設(shè)，若B為奇數(shù)，顯然不能劃分。若B為偶數(shù)，設(shè)一個(gè)布爾變量：若,則回答yes，否則no計(jì)算的條件：若，則若，則框圖如右：時(shí)間復(fù)雜度：外循環(huán)n，內(nèi)循環(huán)，故。因?yàn)榈妮斎腴L(zhǎng)度為，并不是輸入長(zhǎng)度的多項(xiàng)式，故不是多項(xiàng)式算法，是擬多項(xiàng)式算法，。十七、已知MAXLA問(wèn)題屬于NPC類，MAXLA問(wèn)題描述為實(shí)例：簡(jiǎn)單圖G=(V，E)及正整數(shù)K。詢問(wèn)：是否存在一一對(duì)應(yīng)映射P：V1,2,.,|V|，使試證明MINLA問(wèn)題也屬于NPC類，MINLA問(wèn)題為實(shí)例：與MAXLA相同。詢問(wèn)

17、：是否存在一一對(duì)應(yīng)映射P：V1,2,.,|V|，使證明：試圖將 設(shè)圖及正整數(shù)為的實(shí)例，定義的實(shí)例為圖，其中，即為的補(bǔ)圖。 對(duì)頂點(diǎn)集合中所有可能的映射，考慮：固定一點(diǎn)與其它所有點(diǎn)的值，即對(duì)固定頂點(diǎn)，為 所以又與互為補(bǔ)圖所以所以當(dāng)且僅當(dāng)所以，18、 用圖靈歸約技術(shù)證明個(gè)最大子集個(gè)最大子集問(wèn)題：實(shí)例：個(gè)元素，每個(gè)元素有一個(gè)長(zhǎng)度。兩個(gè)非負(fù)整數(shù)和詢問(wèn)：中是否有個(gè)不同的子集。滿足且證明：假設(shè)是解個(gè)最大子集問(wèn)題的子程序，其中長(zhǎng)度函數(shù)設(shè)集合和長(zhǎng)度函數(shù)是劃分問(wèn)題的任意實(shí)例。設(shè)計(jì)劃分問(wèn)題的算法。從計(jì)算開(kāi)始，若是奇數(shù)，則回答NO。否則，并調(diào)用子程序算法：若為奇數(shù)，則劃分問(wèn)題回答NO，結(jié)束。置，調(diào)用算法算法：求滿足的

18、最大數(shù)目。，（可能的界限）若，則并結(jié)束。；調(diào)用，檢查是否有個(gè)子集滿足若回答YES，則,轉(zhuǎn)若回答NO，則,轉(zhuǎn) 根據(jù)求出的滿足的子集的最大數(shù)目，調(diào)用一次若回答YES，則表明所有滿足的子集，也都滿足，故相應(yīng)劃分問(wèn)題回答No若回答NO，則滿足的子集一定存在，所以劃分回答Yes。十九、排工問(wèn)題大全1、區(qū)間排工實(shí)例：有限任務(wù)集合,最早開(kāi)始時(shí)間，最晚結(jié)束時(shí)間，加工長(zhǎng)度。詢問(wèn)：是否存在排工表(1) 區(qū)間排工，用劃分區(qū)間排工(2) 區(qū)間排工證明：將3劃分區(qū)間排工設(shè)三劃分實(shí)例為由此構(gòu)造區(qū)間排工實(shí)例：若三劃分問(wèn)題回答yes，變換后的區(qū)間排工也回答yes。若區(qū)間排工回答yes，則三劃分問(wèn)題也回答yes。且該變換是擬多

19、項(xiàng)式變換。因?yàn)椋喝齽澐?，所以：區(qū)間排工2、 最小遲序排工，有半序關(guān)系和最晚結(jié)束時(shí)間，不能按時(shí)完成的任務(wù)，證明，用證明。3、 先行約束排工：為1，處理機(jī)為，半序關(guān)系（1） 沒(méi)有半序或半序?yàn)闃?shù)時(shí)是P問(wèn)題（2） 時(shí)是P問(wèn)題（3） 半序和任意則是NPC4、 （重要）多任務(wù)排工實(shí)例：個(gè)處理機(jī)處理任務(wù)，加工時(shí)間，任務(wù)之間有半序關(guān)系。詢問(wèn)：最短時(shí)間內(nèi)完成（1）（任意主次表，有空就加工），非空閑算法算法：開(kāi)始所有處理都空閑，所有任務(wù)都未加工對(duì)任務(wù)主次表從左向右掃描，判定每個(gè)任務(wù)是否處于加工狀態(tài)。若可加工，則安排至下標(biāo)最小的空閑處理機(jī)上加工。任務(wù)主次表是按半序關(guān)系的。（2） 證明將的時(shí)間區(qū)分成兩部分：則在半序關(guān)

20、系中存在一條通路，該通路覆蓋子區(qū)間所以：即注：當(dāng)最大加工時(shí)間，限制時(shí)，變成PAR問(wèn)題5、 （重要）獨(dú)立任務(wù)排工實(shí)例：任務(wù)，加工長(zhǎng)度（1） LPT算法，先排時(shí)間長(zhǎng)的:將任務(wù)排序，形成加工主次表對(duì)主次表從1到n掃描，若有空閑機(jī)器，則將任務(wù)安排空閑機(jī)器上加工，直至完成。復(fù)雜度：，多項(xiàng)式算法證：當(dāng)時(shí)，顯然成立。當(dāng)時(shí)，假設(shè)最后完成的任務(wù)為。若最后完成的任務(wù)是，則只考慮前個(gè)任務(wù)，若前個(gè)滿足，則個(gè)當(dāng)然滿足。在內(nèi)所有任務(wù)都非?？臻e又若，則每個(gè)機(jī)器上最多安排2個(gè)任務(wù)，這樣的排工是最優(yōu)的，當(dāng)然滿足；若，則綜上得證（再舉例說(shuō)明上界不能小于3）（2） F算法：多項(xiàng)式近似方案：將任務(wù)從大到小時(shí)間排序：確定正整數(shù)，對(duì)前個(gè)

21、任務(wù)，求最優(yōu)先排工，后個(gè)按先大后小順序排工。證明：設(shè)T是前個(gè)任務(wù)的排工時(shí)間，若，則,設(shè)。在區(qū)間所有的處理器非空閑，開(kāi)始做時(shí)，其它有任務(wù)可能未做完。又，至少有一臺(tái)機(jī)器加工了和前個(gè)任務(wù)的平均個(gè)數(shù)，即個(gè)任務(wù)；又，是前個(gè)中最小的。算法復(fù)雜度：二十、裝箱問(wèn)題實(shí)例：個(gè)物體集合，每個(gè)物體，體積為，容量為C的箱子。詢問(wèn)：需要多少個(gè)箱子才能全部裝完（1） 首次適合算法Fit-First:算法：按照一定順序依次裝入箱子。證明：任意兩個(gè)相鄰箱子裝入物體體積大于，若為偶數(shù)，則；又，若為奇數(shù)，則，又，為整數(shù)，（2） FD算法，先大后小將物體排序，體積從大到小依次裝箱，二十一、背包問(wèn)題實(shí)例：有限集合為重量，為價(jià)值判定問(wèn)題

22、：是否存在優(yōu)化問(wèn)題：，求向量。(1)、判定問(wèn)題限制為偶數(shù)，則上述問(wèn)題變?yōu)镻AR問(wèn)題。(2)、背包問(wèn)題無(wú)多項(xiàng)式時(shí)間絕對(duì)近似算法，將價(jià)值擴(kuò)大倍，變成另一個(gè)問(wèn)題。反證法.(3)、的算法（見(jiàn)前文）(4)、（）多項(xiàng)式近似方案：，證明這個(gè)公式，給出時(shí)間復(fù)雜度算法描述：對(duì)任意一種個(gè)元素的組合都先放入包中嘗試，最后選擇一個(gè)最好的嘗試。偽代碼：下面算法先裝個(gè)再繼續(xù)裝：證明：，為最優(yōu)解，為算法的解(1)設(shè)是最優(yōu)解的背包元素下標(biāo)集合，。若，則有最優(yōu)解，假設(shè)。(2) 將中物體排序按照以下規(guī)則，.是前個(gè)最大價(jià)值。從開(kāi)始到滿足。設(shè)是第一個(gè)未裝進(jìn)去的價(jià)值，則，復(fù)雜度此處省略完全多項(xiàng)式近似方案及復(fù)雜度的分析二十二、TSP問(wèn)題

23、1、 滿足三角不等式的TSP是NPC解：證明思路，將哈密頓回路HC問(wèn)題多項(xiàng)式變換到TSP問(wèn)題:，且變換到TSP問(wèn)題的實(shí)例是滿足三角不等式的。因?yàn)?，故滿足三角不等式的。多項(xiàng)式變換：設(shè)HC的實(shí)例為，據(jù)此構(gòu)造TS實(shí)例，兩個(gè)頂點(diǎn)之間的距離定義為，并設(shè)TSP旅游界值為。易知這個(gè)變換是多項(xiàng)式的。若HC存在一條哈密頓回路，則這條回路在上的長(zhǎng)度必為B，而是最短旅游的界值，故這條回路是滿足實(shí)例的一個(gè)TSP旅游。若存在一個(gè)滿足B的TSP旅游，則該旅游必經(jīng)過(guò)長(zhǎng)度為1的邊，而這些邊均在G上，因此這個(gè)TSP旅游在G上是一條HC回路。這樣就將，而。變換到的TSP實(shí)例的邊長(zhǎng)為1或2，可知該實(shí)例滿足三角不等式，這就證明了滿足

24、三角不等式的TSP問(wèn)題是NPC問(wèn)題。2、 TSP是強(qiáng)NPC：將其邊長(zhǎng)為1，2，是NPC，答：TSP判定問(wèn)題是數(shù)問(wèn)題，因?yàn)槿蝺沙鞘虚g的距離及界值沒(méi)有任何約束。因?yàn)榭梢詫?，從而證明，而有限制，事實(shí)上,故不受限制的原始TSP問(wèn)題是強(qiáng)NPC。因此TSP問(wèn)題不存在擬多項(xiàng)式時(shí)間算法。3、 TSP優(yōu)化將TSP判定TSP優(yōu)化4、 TSP延伸已知部分旅游，能否延伸出一個(gè)長(zhǎng)度不超過(guò)B的全程旅游回路證明：將TSP判定TSP延伸。假設(shè)是求解TSP延伸問(wèn)題的算法。設(shè)計(jì)TSP判定算法如下（折半法）：若調(diào)用子程序：，若回答yes,則令,轉(zhuǎn)；否則，轉(zhuǎn)。若，回答yes,否則no復(fù)雜度（重要）還有排工問(wèn)題的考課件上的兩個(gè)近似算法

25、；和頂點(diǎn)覆蓋問(wèn)題滿足三角不等式的TS問(wèn)題。對(duì)實(shí)例對(duì)應(yīng)的有權(quán)完全圖G=，求最小生成樹(shù)記為T;T中度為奇數(shù)的頂點(diǎn)集為，必為偶數(shù)個(gè);調(diào)用最小對(duì)集算法P在V中求出最小對(duì)集;將中加入T中，形成歐拉圖D;在歐拉圖中求出歐拉回路（P）;用抄近路方法將歐拉回路轉(zhuǎn)換為TS旅游證明：1中d(T)OPT(I);2中d(Ep)=1/2OPT(I)故有d(T)OPT(I),d(Ep)1。觀察性質(zhì)：首先可以假設(shè)最后完成的任務(wù)是tn，為什么，因?yàn)槿糇詈笠粋€(gè)任務(wù)為tk，則只考慮前k個(gè)任務(wù)即可。n-k個(gè)任務(wù)不管。若前k個(gè)任務(wù)滿足結(jié)論，則前n個(gè)任務(wù)當(dāng)然也滿足結(jié)論。取前k個(gè)任務(wù)形成實(shí)例I1，則OPT(I)OPT(I1)，LPT(I

26、)=LPT(I1)所以在0,LPT(I)-tn內(nèi)所有任務(wù)都非空閑。LPT(I)-tnLPT(I)+tnOPT(I)所以：因OPT(I)3tn，若不然則每個(gè)機(jī)器上最多可以安排2個(gè)任務(wù)，n2m。這樣的排工是最優(yōu)的。當(dāng)然滿足。所以.背包問(wèn)題PNP時(shí)，背包問(wèn)題不存在多項(xiàng)式時(shí)間絕對(duì)近似算法。證明：假設(shè)存在算法A，則存在常數(shù)k，使得將I復(fù)制k+1份得到I所以O(shè)PT(I)=(k+1)OPT(I)由此可得背包問(wèn)題的多項(xiàng)式最優(yōu)解算法，與PNP矛盾，故假設(shè)不成立。背包問(wèn)題設(shè)計(jì)絕對(duì)性能比的多項(xiàng)式時(shí)間近似算法1)將所有元素按排序2)按上述順序依次裝入背包，直至放不下，得可行解GA(I)3)令A(yù)(I)=maxGA(I)

27、,背包問(wèn)題有最優(yōu)解為，是得到的解，求證證明：1）設(shè)R是最優(yōu)解的背包元素下標(biāo)集合，若|R|k，則可求到最優(yōu)解，下面假設(shè)|R|k2)將R中物體排成有序?qū)Γ唧w規(guī)則如下：a)前k個(gè)為R中受益最大的k個(gè)b)從i=k+1到|R|滿足3)算法中必存在如下情況，即選定前k個(gè)作為包底，記;設(shè)s是在此情況下調(diào)用L(I,P,W,M,n)增加的收益設(shè)是在調(diào)用L(I,P,W,M,n)過(guò)程中第一個(gè)沒(méi)有被裝入包的元素4) 時(shí)間復(fù)雜度O(nk)=O(n)劃分在已知?jiǎng)澐謫?wèn)題實(shí)例存在劃分的情況下T，求出具體劃分：假定已有一張表t，n行，列，記，由于存在劃分，則tn,b=T,記n=a設(shè)一個(gè)集合A存放入選元素的下標(biāo)If (a0 或

28、 b0) 則返回集合A，為所求；Else 判斷 a-，go 1)將a加入集合A；b=b-S(a)；a-；go 1)WPAR問(wèn)題設(shè)計(jì)WPAR的擬多項(xiàng)式算法，判定并求解。解：設(shè)，若B不能被3整除則無(wú)劃分，若B能被3整除，則設(shè)計(jì)表t：n行，列若，則最終回來(lái)yes，存在劃分，否則Not(i,0)=Tt(1,j)=T若ti-1,j=T，則ti,j=T若ti-1,j-S()=T，則ti,j= TTi,-1=FT0,j=F求解算法：記，記n=a （將入選元素的下標(biāo)存入集合A）If (a0 or br) 則j=0; 轉(zhuǎn)6)j=;if (x=L(j);轉(zhuǎn)6)if (xL(j) l=j+1;else r=j-1;

29、 轉(zhuǎn)2)輸出jb) 比較次數(shù)：對(duì)二維搜索，每次搜索成功將范圍減半，故最多比較次數(shù)為2的對(duì)數(shù)，又因?yàn)楫?dāng)n=1時(shí)至少比較1次，故比較次數(shù)不超過(guò) 2SAT實(shí)例，,判斷是否有真值指派，若有求出。算法：根據(jù)U,C構(gòu)造有向圖G，2n個(gè)頂點(diǎn)，分別是若，則添加和兩條邊，對(duì)，若有，則；若，則判定：若圖G中對(duì)，有和同時(shí)存在，則無(wú)真值指派。反之，亦是（G上沒(méi)有回路真值指派，因?yàn)镚中無(wú)回路不同時(shí)存在）求解：a)如2)所述賦值b)擴(kuò)展賦值（若有，則在的同時(shí)，對(duì)所有指向的節(jié)點(diǎn)賦0，所有指向的節(jié)點(diǎn)賦1）c) 對(duì)a、b之后，仍未賦值的變量，可同時(shí)賦0或同時(shí)賦1已知MAXLA問(wèn)題是NPC，求證MINLA亦是NPCMAXLA：簡(jiǎn)

30、單圖，詢問(wèn)是否一一映射，使證明：根據(jù)MAXLA實(shí)例構(gòu)造MINLA實(shí)例如下：及k，其中V=V，則G為G的補(bǔ)圖：又從MAXLA到MINLA的變換是多項(xiàng)式的求證：第k個(gè)最大子集是NP-hard實(shí)例：有限集集合A每個(gè)，有，兩個(gè)非負(fù)整數(shù)，詢問(wèn)：A中是否存在k個(gè)不同的子集，滿足證明：設(shè)SA,S,B,k是個(gè)解第k個(gè)最大子集問(wèn)題的子程序.構(gòu)造劃分問(wèn)題實(shí)例A，設(shè)計(jì)劃分問(wèn)題算法如下：S(A)為奇，則返回No再調(diào)用一次SA,S,B-1,若回答yes，則所有滿足的A也滿足，故無(wú)劃分若回答No，則使，則劃分綜上所述，若S是多項(xiàng)式算法，則可以多項(xiàng)式時(shí)間解釋劃分問(wèn)題。即PAR第k個(gè)最大子集問(wèn)題所以是Np-hard運(yùn)動(dòng)員比賽表算法：var a:array1-1024,1-1024 of integerProcedure bs(k:integer)Begin If k=0 the