外文翻譯--最小化模式下料問(wèn)題科林麥克迪爾米德 中文版

1 離散應(yīng)用數(shù)學(xué) 離散應(yīng)用數(shù)學(xué) 98(1999) 121-130 最小化模式下料問(wèn)題 科林麥克迪爾米德 統(tǒng)計(jì) 部門(mén) ，牛津大學(xué)，南 公園路一號(hào) ，牛津 大學(xué) OX1 3TG，英國(guó)收稿 于 1997 年10 月 21日，接受 于 1999 年 2月 8日 摘 要 在切割存量模式最小化問(wèn)題，我們希望，以滿足盡可能少巨型卷軸卷軸切割各種客戶的需求，并進(jìn)一步減少使用不同的切削模式的數(shù)量。我們專注于特殊情況，其中任何兩個(gè)客戶卷軸到一個(gè)巨型合適，但沒(méi)有三事：這個(gè)案件的興趣，部分是因?yàn)樗亲詈?jiǎn)單的情況是不平凡的，部分是因?yàn)樗趯?shí)踐中可能會(huì)出現(xiàn)當(dāng)一個(gè) 嘗試一個(gè)解決方案，以改善迭代。 我們發(fā)現(xiàn)，該模式最小化問(wèn)題是強(qiáng) NP 難的，即使在這種特殊情況下，當(dāng)inding 最低廢液的基本問(wèn)題是微不足道的。 我們的分析主要論點(diǎn)集中在 均衡 的子集，并提出了涉及亞均衡的啟發(fā)式搜索方法的方法。 1999 Elsevier 科學(xué) BV 公司保留所有權(quán)利。 關(guān)鍵詞： 下料，切割模式 ；分區(qū) ； NP 難 ；動(dòng)態(tài)規(guī)劃 2 1 簡(jiǎn)介 有些材料如紙，可制造性 巨無(wú)霸 卷，這是后來(lái)成為更窄輥切，以滿足客戶的需求。為了減少浪費(fèi)，應(yīng)選擇切割方式，以盡可能少的使用客機(jī)（見(jiàn) 4,7,8）。 因此，下料問(wèn) 題已基本輸入一個(gè)正整數(shù) j，不同的正整數(shù) r1的 ,., Rn和 D1的 ,.,正整數(shù)的 DN，以及需要的任務(wù)是，以盡可能客機(jī)的寬度 j的數(shù)為滿足客戶的卷筒寬度里迪需求對(duì)每個(gè) i = 1 ,.,，全 這是其中的經(jīng)典 OR問(wèn)題之一。 它包含了強(qiáng)烈的 NP -完全問(wèn)題三分區(qū)： 因此即使巨幅大小 J外面有一層氮、多項(xiàng)式滿足每個(gè)客戶的卷軸大小國(guó)際扶輪扶輪 J / 4 J / 2 -看 6,p。 224。因此我們不能指望在合理時(shí)間內(nèi)總是能找到最優(yōu)解等問(wèn)題的。 每一次不同的客戶卷軸模式是被削減，在切 割機(jī)的刀需要重新設(shè)置。甲由Cn中 Goulimis 并在第 29屆歐洲與產(chǎn)業(yè)調(diào)查研究組 1996 年 3 月有關(guān)如何找到辦法來(lái)解決上述料問(wèn)題，這進(jìn)一步減少了用于切割不同模式的數(shù)量問(wèn)題 - 見(jiàn)1,2,9 。 一般情況下這當(dāng)然是變得越來(lái)越難 。為了探討擴(kuò)展問(wèn)題雪上加霜，我們?cè)谶@里考慮一個(gè)特殊的案件中，盡量減少對(duì)客機(jī)（減少?gòu)U物），數(shù)量基本問(wèn)題是微不足道的。 最小化格局 ： 輸入： D1的正整數(shù) ；的 DN。 任務(wù)：在切割存量問(wèn)題，即要求 I 型迪卷軸是，任何兩個(gè)卷軸到一個(gè)巨型做它，但沒(méi)有三，工業(yè)最低廢液，進(jìn)一步減少了使用不同模式的數(shù)量。 這種特殊的情況是非常有限的部分原因是因?yàn)樗坪跏亲詈?jiǎn)單的情況是完全不平凡的，部分是因?yàn)樗赡軙?huì)在實(shí)踐中產(chǎn)生的，當(dāng)一個(gè)一個(gè)解決方案試圖改善迭代的興趣 。 例如，如果對(duì)目前使用的一些模式集合同意的大型卷軸和 difer小卷軸而已，它在任何兩個(gè)小卷軸左邊的大型卷軸的寬度，那么當(dāng)我們?cè)噲D重新分配小我們面臨的正是這種卷軸的特殊情況 16。 我們調(diào)查模式是否最小化問(wèn)題還很難在這個(gè)特殊的情況，并簡(jiǎn)要考慮辦法找到好的解決辦法。 很明顯，所需要的客機(jī)數(shù)量最少的是我的 di / 2，圓了總需求的一半，它是微不足道的一個(gè)相應(yīng)的最低工 業(yè)廢液。但是，它是多么容易躋身工業(yè)廢物最小的解決方案，一個(gè)能最大限度地降低使用的模式的數(shù)量，？對(duì)于這個(gè)問(wèn)題的變體在沒(méi)有三個(gè)客戶卷軸它變成珍寶，但也有一些對(duì)可能不是，它是在 1表明，問(wèn)題是強(qiáng) NP -難問(wèn)題。下面的定理加強(qiáng)這種不利的結(jié)果。 定理 1： 這個(gè)問(wèn)題最小化模式是強(qiáng) NP -難問(wèn)題。 3 對(duì)上述問(wèn)題的理解關(guān)鍵是一個(gè) 平衡的一個(gè)子集 的概念。 給定一個(gè)家庭 d =(d1,dn)的非負(fù)整數(shù) ,表示 x(d)的 在任何解決方案中使用最少的廢物模式的最小數(shù)量。 還有 ,另一個(gè)平衡的非空的子集 1,n ,如果它能夠被分割成兩個(gè)集 合A和 B,tA di = 5ieB di。因此 ,如果 di = 0 然后單獨(dú)設(shè)置 i是平衡的。讓 v(d)是最大的數(shù)字的平衡子集兩兩相互無(wú) 關(guān)的。 引理 1： 如果 J2i di 是偶數(shù) ,然后 x(d)= n - v(d)。 如果 i di 是奇數(shù)，令 x(d) = i(d),其中 d1 從 D獲得通過(guò)增加一個(gè)額外的統(tǒng)籌的 DN +1 = 1。 我們將在下一節(jié)中證明這個(gè)引理。 當(dāng)與一個(gè)模式最小化所面臨的問(wèn)題，我們領(lǐng)導(dǎo)的定理 1 和引理 1以上考慮啟發(fā)式方法 inding 亞群平衡的好包裝。不幸的是 NP -完全甚至 是 測(cè)試，如果一個(gè)家庭中的 正整數(shù)格 a1,.,an有一個(gè)平衡的一個(gè)子集。 這就是問(wèn)題稱為弱分區(qū)是大衛(wèi)約翰遜的 NP 完全列 10，其中四分之三的 NP 完全獨(dú)立的證據(jù)被引用，最早在13。 我們希望工業(yè)亞群的平衡好包裝，但我們知道這是很難工業(yè)最佳包裝，的確是很難平衡的工業(yè)任何一個(gè)子集。自然啟發(fā)式的方法是反復(fù)尋找和刪除一個(gè)平衡的一個(gè)子集，最好是小的。其中尋求一個(gè)平衡的一個(gè)子集的方法是使用diferencing，這里我們?cè)俅稳〈?diference 絕對(duì)值兩個(gè)數(shù)字 - 參見(jiàn)5,12,15,17。這種方法目前正在調(diào)查中最小的格 局 16中。另一種方法是使用一個(gè)還算快速算法，保證工業(yè)均衡的子集或子集的最小平衡：我們會(huì)看到，我們可以使用一個(gè)簡(jiǎn)單的動(dòng)態(tài)規(guī)劃方法來(lái)測(cè)試，如果有一個(gè)平衡的子集，均衡和 IND一個(gè)最小的子集如果有一個(gè)，在偽多項(xiàng)式時(shí)間。最小的模式啟發(fā)式方法更普遍的情況下在降低庫(kù)存的問(wèn)題被認(rèn)為是 1,2,9,11。 該論文的其余部分計(jì)劃如下。在下一節(jié)中，我們建立的模式之間的平衡亞群的數(shù)量和包裝的關(guān)系。接下來(lái)，我們證明我們的主要結(jié)果，這個(gè)問(wèn)題最小化模式是強(qiáng) NP -難問(wèn)題。在此之后，我們認(rèn)為 briely 如何尋找平衡的子集， 并 inally我們做一些總結(jié)性發(fā)言。 4 2 模式，學(xué)位和平衡套 在這一節(jié)中，我們將證明引理 1，其中涉及的圖案編號(hào)，包亞群平衡 英格斯。最小化的問(wèn)題可以改寫(xiě)格局在圖上。一個(gè)模式，涉及卷軸 I型和 J型卷筒之間將對(duì)應(yīng)頂點(diǎn)頂點(diǎn) vi和 vj 的邊緣。我們將讓我們的圖，包含在任何頂點(diǎn)循環(huán)但不包含多個(gè)邊緣。 給定一個(gè)圖 G =（ V， E）對(duì)集 V = v1， .， v2的頂點(diǎn)，連同非負(fù)整數(shù)重量的邊緣 E，我們的家庭 W 時(shí)，頂點(diǎn)加權(quán)第六度過(guò)度的重量與我們六邊 事件的總和與任何循環(huán)，計(jì)數(shù)兩次。給定一個(gè)向量 d =（ d1. dn） 的正整數(shù)，我們呼吁 d如果每個(gè)頂點(diǎn) Vi 有兩人加權(quán)程度地代表公克 WA 網(wǎng)絡(luò)。考慮以下問(wèn)題。 學(xué)位 ： 輸入：積極 intergers d1. 甚至與 dn。 任務(wù)：工業(yè)用盡可能少的邊緣一個(gè)代表網(wǎng)絡(luò)。 給定一個(gè) d 組 =（ d1 . dn）的正整數(shù)，甚至與我二，有一個(gè)度之間的解決方案和模式 MINIMI SATION 這些自然的對(duì)應(yīng)，特別是最小的邊數(shù)前者的可能等于 （ d）項(xiàng)。 引理 1： 假設(shè) di是偶數(shù)。 設(shè) G w是任何代表工作，并考慮為 G的 K 個(gè)節(jié)點(diǎn)集 K 表的組成部分。這當(dāng)然必須有至少 k - 1條邊，如果它有這個(gè)數(shù)目，因此 是對(duì) K 樹(shù)，那么三分之二的頂點(diǎn)著色表明， K 是平衡的。因此，在 G 的邊數(shù)至少有 n 減去若干套組成部分的平衡。因此（ D） Jsn - 的 v（ d）。 為了證明反向不等式，考慮任何 V1.Vn（ Ki： i I），其中一個(gè)最不均衡。我們將證明，有代表 怨恨網(wǎng)絡(luò) G， W 使得圖 G有組件（ Gi： I i）如已設(shè)立文基頂點(diǎn)，這些組件是這樣，如果文是平衡的，然后是一樹(shù)基如果沒(méi)有則Gi是一加一樹(shù)循環(huán)。這將完成該引理的證明。 考慮平衡集 K，其中分區(qū) A U S 使得 YieA= igBdi國(guó)際能源署。我們必須表明，有對(duì) T邊緣 E對(duì) K和非負(fù)權(quán)重，我們一樹(shù) T，使得對(duì)于每一個(gè)節(jié)點(diǎn) v K 時(shí)，對(duì)事件邊的權(quán)重之和等于的 dv（其中雙回路數(shù)）。我們使用 K|表感應(yīng)。如果 A或 B 是空的，結(jié)果是微不足道的，因?yàn)槲覀儽仨殲槊總€(gè) V 光那假設(shè) A和 B都是非空的 dv = 0。選擇任何一個(gè)和 b 阿 B和不失一般性假設(shè)大 分貝。減少大的分貝?，F(xiàn)在 K 表 B的是平衡的，我們可以感應(yīng)工業(yè)適當(dāng)?shù)募訖?quán)樹(shù)。然后加入與體重分貝邊緣抗體。 最后，考慮一個(gè)集 K這是不均衡的，但就是這樣，相應(yīng)的要求和是偶數(shù)。如 5 上所述，我們可以隨時(shí)更換了使用成本的一個(gè)邊緣的 diference 兩 個(gè)要求。因此，我們能滿足所有，但一用邊緣形成一個(gè)對(duì) K樹(shù)需求，然后添加一個(gè)循環(huán)結(jié)束的組成部分。 6 3 最小化模式是強(qiáng) NP -難 在本節(jié)中，我們證明定理 1，這個(gè)問(wèn)題最小化模式是強(qiáng) NP -難問(wèn)題。總結(jié)三（或舒爾三）是三，這樣的兩個(gè)之和等于第三個(gè)不同的整數(shù)集合。下面的問(wèn)題可以得到更充分的描述，總結(jié)成獨(dú)特的整數(shù)分區(qū)的三倍作為。 總結(jié)三元 輸入： S1. S3n 不同的正整數(shù)。 問(wèn)：能否輸入三元分割成總結(jié)？ 這個(gè)問(wèn)題類似于數(shù)值匹配與目標(biāo)款項(xiàng)，加里和 Johnson 6，第 224，但額外的（令人驚訝的麻煩），條件是涉及的人數(shù)必須是不同的。 引理 2： 問(wèn)題總結(jié)三元是強(qiáng) NP -完全的。 本節(jié)的大部分將用于證明上述引理，但首先，讓我們看到，它會(huì)產(chǎn)生定理 1。 證明定理 1（假設(shè)引理 2） ： 我們給一個(gè)總結(jié)，學(xué)位 strightforward 三倍，多項(xiàng)式時(shí)間減少?？紤]一個(gè)總結(jié)三元上述實(shí)例。以 =作為學(xué)位實(shí)例（ 2s1 .2s 3n）。由于硅是不同的正整數(shù)，也有規(guī)模不小于 3套平衡。因此，（ dHence 由引理 1，第十章 x（ d） 2n與 x（ d）為 2n =當(dāng)且僅如果 s1 . .s3n可分為總結(jié)三倍 現(xiàn)在考慮的問(wèn)題總結(jié)三倍，這顯然是在 NP。我們將證明它是強(qiáng) NP -通過(guò)給從 NP -完全問(wèn)題限制 X3C 減少完成，下述，總結(jié)每個(gè)三元組在 O（ n3）的。 限制 X3C： 輸入：一組第三季度的 X元素和一個(gè)三元組集合 C在十，這樣每個(gè) X的 元素完全相同 3 三元載。問(wèn)：可以劃分為三元 X是在 C？ 引理 3： 限制 X3C 問(wèn)題是 NP完全的 。 證明 據(jù)了解，這個(gè)問(wèn)題是 NP 完全問(wèn)題，如果每個(gè)元素被限制在最多 3 三倍，而不是正好 3 - 見(jiàn)加里和 Johnson 6，第 221。這是很容易對(duì)注冊(cè)整潔 的實(shí)例 X， 使每個(gè)元素恰好是 3 的三倍。 很明顯，我們能堅(jiān)持，每個(gè)元素在 2或 3 的三倍。我們可以在分區(qū)中的元素正好兩個(gè)三元組分為三個(gè)區(qū)塊的大小。對(duì)于每個(gè)塊 x， Y， Z，添加新的元素三個(gè) x， y， z及 x， y， z， x， y， z， x1， y， z， x1， y， z。調(diào)用新的實(shí)例 X， C的。顯然，每個(gè) X的元素是完全相同三三元在 C；和 X 可以被劃分在 C到三倍，如果有僅當(dāng) X可以被劃分為三元在 C。 引理 2： 考慮一個(gè)實(shí)例 X， C的限制 X3C，其中 | X = = CI=3q。 7 季度全令 Y = X x 1 ,., 7。我們將建設(shè)一個(gè) 擴(kuò)大 在 Y D 的收集，包含三元使得 X可分為三元在 C分區(qū)，當(dāng)且僅當(dāng) y可劃分為 D中三元，接著我們將構(gòu)造一個(gè)實(shí)例（秒（ y）的：你們的 Y 總結(jié)三倍，其中每個(gè)尺寸 S（ y）的異 O（ n2），），這樣的總結(jié)恰恰三倍對(duì)應(yīng)的三元組在 D 形成一個(gè)二分圖 G =（ C， X， E）的頂點(diǎn) C 部及 X 和頂點(diǎn)窄隙室和 X GX的相鄰（即邊發(fā)射 GE）的正是由于當(dāng) x 噸 G 中的每個(gè)頂點(diǎn)度是三，我們可以在多項(xiàng)式時(shí)間內(nèi)找到一個(gè)合適的 3 邊染色 ： E - 1,2,3?，F(xiàn)在，我們每個(gè)元素x GX 的分割成三份（ x， 1），（ x， 2）和（ x， 3）。鑒于一特里普爾 T = x， y，z氣相色譜，令 T是三重 T= （ x， KTx），（ y， （ Ty），（ z， （ Tz） 觀察，在三 T的分子具有不同的第一坐標(biāo)（ X），以及獨(dú)特的第二個(gè)坐標(biāo)（必須是 1,2,3），而 C=（ T： TG）分區(qū)集 X x 1,2,3。 接著，每個(gè) X光霞，讓 Fx 的是集合組成的四個(gè)三元 （ x， 1），（ x， 4），（ x， 5） ， （ x， 3），（ x， 4）， （ x， 5） ， （ x， 2），（ x， 6），（ x，7） 和 （ x， 3），（ x， 6），（ x， 7） 。設(shè) D是由碳的收集與所有的 X 十，因此 D包含在集合在一起 Fx 的三元 | | +4 | x |= 5n 的三倍。 如果某些子集合 的 D 是 Y的分區(qū)，然后對(duì)每個(gè) x G X 的時(shí)候，恰恰的要素之一（ x， 1），（ x， 2），（ x， 3）不包括由三元組在 D東經(jīng)外匯，因此必須由在 D東經(jīng)企業(yè)所得稅三倍以下方便，這包括 X可以被劃分在 C到三倍，當(dāng)且僅當(dāng) y劃分可分為三元在 D這樣就完成了施工紅外警戒的一部分。 下一步，我們將看到如何分配尺寸 S（ y）對(duì)每個(gè)元素 y 戈瑞以便在 Y元素的總結(jié)三元正是在 D的三元組，我們將使用一個(gè)界定差不多的 K -明智的獨(dú)立隨機(jī)變量的家庭小樣本空間。 設(shè) 1 = 3 log2 n+10，令 t = 2n1，令 k = 91，讓 8 = 2。有 Q的一個(gè)子集 0,1，大小 2（ 1 + 0（ 1） K的：如果一個(gè)點(diǎn)的合作 =（ ro1 .,cot）是隨機(jī)挑選的統(tǒng)一 Q，則 ,., cot）的是 8距離的 K -明智的獨(dú)立，見(jiàn) 3。今后這類一套 Q可以（明確）在多項(xiàng)式時(shí)間建成北界 。 給定一個(gè)點(diǎn)合作賓館，對(duì)每個(gè) i = 1 ,., 2n 個(gè)，讓 $ = $（ co）是非負(fù)， teger 二進(jìn)制擴(kuò)展 coy。當(dāng)一個(gè)點(diǎn) co=（ co1,., cot）的采收有限公司。 從Q隨機(jī)均勻，然后 S1.,.S2n是隨機(jī)變量，以價(jià)值觀在 0,1 ,., N - 1 個(gè)，其中 N = 2Z，它們具有以下屬性。對(duì)于任何集成電路與 IC1 .2n 與 0| 11 69，和任何集合 0,1 ,., N - 我們： I I） G E） - |E| /NI/| 61 / 2：現(xiàn)在，我們可以定義元素的大小為我們總結(jié)三元原審（年）。為清楚起見(jiàn)，我們將寫(xiě)的（ X， 1），而不是秒（ X， 1）等。給定一個(gè)采樣點(diǎn)的合作賓館，對(duì)每個(gè) i = 8 1 ,., n 我們?cè)O(shè) S（ xi， 1） = 2S2i - 1（ co） + 2N 個(gè)和 S（ xi， 2） = 2S2i（ m） + 2N。設(shè) x G X，假設(shè)使（ x， 3）是在三 T Cwhere T 公司還包含（ X， 1）和（ x ，2）。然后我們?cè)O(shè) S（ x， 3） =s（ x， 1） + s（ x， 2）（ 4N）。這個(gè)定義的（ x， i）為每個(gè) X G X 和 iG1,2,3?，F(xiàn)在，對(duì)于每個(gè) x G X 的，設(shè) S（ x， 4） =（ s（ x， 1） +s（ x， 3） / 2s（ x， 5） =（ - S的（ x， 1） + S（ x）， 1） / 2s（ x， 6） =（ d（ x， 2） +s（ x， 3） / 2 和 S（ x， 7） =（ - S（ x， 2） +s（ x， 3）/ 2?，F(xiàn)在我們已經(jīng)定義了一個(gè)正整數(shù)的大小為每個(gè) Y 戈瑞的（ y）和 D中的每個(gè)三是始終總結(jié)。 讓 BCQ 公司是 壞 的情形，或者因?yàn)槟銈兊膬r(jià)值之（ y）的失敗是不同的，或一些較 D 組其他三是總結(jié)。我們將表明， P（ B）“ 1。它會(huì)跟有一個(gè)采樣點(diǎn)的合作 Q b，和我們能找到這樣一個(gè)由窮舉搜索多項(xiàng)式時(shí)間點(diǎn)。這將完成該引理的證明。 為了證明 P（ B）“ 1，它足以讓我們假設(shè)隨機(jī)變量的 S1， S2n正是 9 明智的每個(gè)獨(dú)立的均勻分布于 0， 1， N - 1，然后，以證明 P（ B）“ 1 / 2。觀察，從 s 的定義（ y）的，為每個(gè) Y 有一個(gè)向量 a（ y）的 e - 1， 0， 1， 2 2n個(gè)，大小為支持最多 3，使得 s（ y）的，保險(xiǎn)業(yè)監(jiān)督（ y）的 ；是一個(gè)常數(shù)（即不依賴于合作）。 讓 y1和 y2是 Y 的不同元素，讓 a=a(y1) a(y2)。這是很容易看到， a 是一個(gè)非零整數(shù)大小為支持最多 6 個(gè)載體，并有一個(gè)常數(shù) c 使得 s（ y1） =s（ y2）的當(dāng)且僅當(dāng)易 =角但是，這最后事件的概率至多為 1 /全因此，概率為你們的價(jià)值之（ y）的并不都是最明顯的是在 2N6 同樣，對(duì)于 我們可能會(huì)說(shuō)不需要的三倍。讓日 y1， y2 和 y3 的是不同的元素，形成一個(gè)不考慮在 D事件的 s（ y1） +s（ y2） =s（ y3）。設(shè) a =a（ y1） +a（ y2）=s（ y3）。然后，一個(gè)有規(guī)模的支持最多 9，并有一個(gè)常數(shù) c 使得 s（ y1） +s（ y2）=s（ y3）當(dāng)且僅當(dāng)易 =角我們斷言向量 a是非零。然后，它將按照三倍的概率并不一定是在 D總結(jié)至多（ ） 3 6 ；，因此 P（ B） 6（ 72i0nfn）“ 1 / 2，根據(jù)需要。 它仍然只是建立上述索賠。對(duì)于每一個(gè)元素 y =（ x i） e ，讓 n1（ y） = x和 7i2（ y） = i，記 Yia（ y） i 的由 c（ y）。假設(shè) a = 0 時(shí)：我們必須獲得矛盾。請(qǐng)注意：第一，如果 7i2（ y） = 3，那么 r（ y） = 4。因此，既不氮?dú)?，也?7i2（ y2）的可以等于 3，因?yàn)槲覀儾皇亲?Yiai“ 4 - ff（ y3） 0。 現(xiàn)在假設(shè)氮?dú)猓?y2）的 1,2，這是 ff（ y1） = 2。那么 C（ Y2）的必須是1或 2。我們認(rèn)為這兩種情況。 （一） 首先假設(shè)的 c（ y2） = 1。然后， cr（ y3） = 3?，F(xiàn)在 a（ y1的只有 9 一個(gè)非零統(tǒng)籌 2， a（ y2）的有 -1,1,1 和 a（ y3）有 1,1,1。然后的 n1（ y1） = n1（ y2） = n1 （ y2）和特里普爾 T =（ y1 y2 y3） isinD，矛盾。 （二） 現(xiàn)在假設(shè) r（ y2） = 2。然后， r（ y2） = 4。現(xiàn)在 a（ y1有一個(gè) 2，（ y2）的有 1個(gè) 2 和 a（ y3）有 2,2。同樣的三重性 T D，一個(gè)矛盾。 現(xiàn)在我們已經(jīng)表明， n2（ y1）的 e 1,2,3，同樣 y2。因此，這兩個(gè) n2（ y1）和7i2（ y2）在 4， 5,6,7。因此 ff（ y1）和 cr（ y2）的 are1or3， cr（ y2） is2 或4。 首先假設(shè) ff（ y1） = C（ y2） = 1，所以 C（ y3） = 2。然 后兩個(gè) a（ y1）和 a（ y2）的有非零統(tǒng)籌 -1 1 1 和 a（ y3）有 2。但接下來(lái) a（ y1）和 a（ y2）的必須具有相同的支持。接下去的 n1（ y1） = n1（ y2），這是不可能的。不失一般性，我們現(xiàn)在可以假設(shè) ff（ y1） = 1 和“ r（ y2） = 3。然后， r（ y1） = 4，和 a（ y1）的有非零協(xié)調(diào) -1,1,1， a（ y1）有 1,1,1，和 a（ y3）有 2， 2。然后，我們?cè)僖淮喂I(yè) a（ y1）和 a（ y2）的必須具有相同的支持，等的 n1（ y1） = n1（ y2） = 1（ y3）。但現(xiàn)在，三 T是在 D，一對(duì)矛盾。 10 4 尋找平衡的子集 這是一個(gè) NP 完全測(cè)試，如果一個(gè)家庭中格 A1 ,., 可持續(xù)的競(jìng)爭(zhēng)整數(shù)的POS 機(jī)一有一個(gè)平衡的一個(gè)子集，但我們?nèi)匀豢赡芟Ｍ麨閬喨浩胶獾母窬种兴阉鞯阶钚∧承﹩l(fā)式方法。在本節(jié)中，我們看到，一個(gè)簡(jiǎn)單的基于動(dòng)態(tài)規(guī)劃的方法就能解決的偽多項(xiàng)式時(shí)間等問(wèn)題。 紅外警戒看到我們?nèi)绾螠y(cè)試，如果有一個(gè)平衡的一個(gè)子集，如果這樣工業(yè)之一（另外兩個(gè)最小相應(yīng)的總和）在 O（ 5 iai）的步驟。之后，我們將看到如何找到一個(gè)平衡的最小的子集，在 O（ n2J iai）的步驟。這不是 明顯的，這些算法將在一個(gè)最小化的啟發(fā)式方法具有更好的模式。 讓 s0=5 0 / 2。對(duì)于每個(gè) S = 0,1 ,., S0 的，而且每個(gè) j = 0,1 ,., n，設(shè)集 f（ s， j）為 T。 如果有一個(gè)相應(yīng)和 S子集，讓集 f（ s， j）的平等 F， 否則。則 f（ 0， j）的每個(gè) j = T 為 = 0,1 ,., n，且集 F（ S， 0） =每次的 F = 1 ,., S0 的。我們可以計(jì)算所有的值集 f（ 0， j）在反過(guò)來(lái)，在 O（ 1）每個(gè)值的步驟，如下所示。 為 s = 1 ,.,對(duì)于 j = 1 . n s0 f（ s， j） f（ s， j - 1） V f（ s - aj， j - 1）。 （如果 s 0，我們解釋集 f（ s， j） a s F） 如果在上述復(fù)發(fā)，這是從來(lái)沒(méi)有的情況是，在右邊兩個(gè)術(shù)語(yǔ)是 T，那么就沒(méi)有平衡的一個(gè)子集。但假設(shè)這種情況確實(shí)存在，而且我們第一次見(jiàn)面是在 s0和j0。那么有兩種不同的亞群的相應(yīng)和 A 和 B（一 j0和一個(gè)不包含）。此外 A 和 B必須是不相交的，由 s0的極小。很明顯，我們可以發(fā)現(xiàn)這樣集合 A和 B 很快，他們的聯(lián)盟是需要平衡的設(shè)置。 現(xiàn)在假設(shè)我們希望工業(yè)一個(gè)最小的平衡，如果有一子。我們描述動(dòng)態(tài)規(guī)劃的需要 O（ n2J iai）的步驟為基礎(chǔ)的方法。 和以前一樣，讓 s0= iai / 2。對(duì)于每個(gè) s = 0,1 ,.,s0的，而且每個(gè) J型， K和 K = 0,1 ,., 6 ， 讓集 f（ s， j， k）為 T，如果有一個(gè)大小最多 K 表的一個(gè)子集與對(duì)應(yīng)和 s，讓集 f（ s， j， k），否則等于 F。然后再次發(fā)生 f（ s， j， k） =f（ s， j - 1， k） V f（ s - flj， j - 1， k - 1） 再加上適當(dāng)?shù)倪吔鐥l件，使我們能夠確定的所有值在 O集 f（ s， j， k） O（ 1） 每個(gè)值的步驟。 11 對(duì)于每個(gè) S = 1， s0的是讓作為一個(gè)子集最小尺寸 1， n的相應(yīng)和 S 如果有這樣的一個(gè)子集，讓為 as= 0，如果不是 ；，讓旅館是第二小的尺寸一個(gè)子集 1 . n s 如果至少有兩個(gè)這樣的子集，讓 bs= 0，如果沒(méi)有。我們已經(jīng)看到，我們可以計(jì)算出所有值集 f（ s， j， k） inO（ n2s0）步驟。從這些值集 f（ s， j， k），我們可以計(jì)算出在相同的約束，因?yàn)樗械膬r(jià)值和 BS，內(nèi)容如下。 要計(jì)算的，注意，如果 f = 0 的（ s， N組， n） = F 和如果沒(méi)有則因?yàn)槭亲钚〉?k，使得集 f（ s， n， k） =T 現(xiàn)在假設(shè) as= 0，考慮如何計(jì)算學(xué)士學(xué)位。 請(qǐng)注意，如果集 f（ s， j， k） = T 接著我們可以找到一個(gè)子集 1， j大小至多 k與相應(yīng)和 S透過(guò)回溯復(fù)發(fā)。我們也可以說(shuō)，如果有多個(gè)這樣的子集檢查，如果再發(fā)生在右側(cè)，如果過(guò)了相應(yīng)的集 f（ s， n， n）（我們知道的是 T）這兩個(gè)術(shù)語(yǔ)噸有一個(gè)獨(dú)特的解決方案，然后 bs= 0。否則， bs是最 K，使得相應(yīng)的 f（ s， n， k）有一個(gè)以上的解決方案。 如果 bs當(dāng)時(shí)的不可能有平衡的一個(gè)子集 0。假設(shè)現(xiàn)在至少有一個(gè)非零值學(xué)士學(xué)位，并設(shè) T是一個(gè)值之比達(dá)到最小為 + BS 上旅館所有的 S = 0。讓我們?cè)谂cBt是每個(gè) T 和相應(yīng)的金額，這樣獨(dú)特的套 裝 | AT= | 轉(zhuǎn) Bt =勝。 （我們可以找到這樣集快。）以下的索賠將完成我們的證明。 索賠：該套在與 Bt 是不相交的，并在 u =轉(zhuǎn) Bt CT 是最小的平衡設(shè)置 證明索賠 ： 假設(shè)在滿足不同的集合和 Bt。記的在 Bt 基因的總和美國(guó)那么這也是轉(zhuǎn) Bt和在。但現(xiàn)在金 +不 at+bt= | Ct|。 12 5 結(jié)束語(yǔ) 我們已經(jīng)看到，即使是在削減庫(kù)存問(wèn)題非常有限的情況下，它是強(qiáng) NP -難，盡量減少使用不同模式的數(shù)量，因此，我們不能期望能夠解決偽多項(xiàng)式時(shí)間等問(wèn)題，即使。關(guān)鍵的概念，是一個(gè)平衡的子集，我們被帶往亞群平衡的考慮包裝啟發(fā)式，從而考慮尋求這種子集 NP難問(wèn)題。 13 6 如需進(jìn)一步閱讀 以下參考，也是讀者所關(guān)心的： 14。 14 致 謝 我非常感謝其他參與 在紅外警戒中 討論 的研究組成員 。 15 參考文獻(xiàn) 1 C. Aldridge, J. Chapman, R. Gower, R. Leese, C. McDiarmid, M. Shepherd, H. Tuenter, H. Wilson, A.Zinober, Pattern Reduction in Paper Cutting, Report of the 29th European Study Group with Industry,University of Oxford, March 1996. 2 J.M. Allwood, C.N. Goulimis, Reducing the number of patterns in the 1-dimensional cutting stockproblem, Internal Report of Control Section, Electrical Engineering Department, Imperial College, 1988. 3 N. Alon, O. Goldreich, J. Hastad, R. Peralta, Simple constructions of almost k-wise independent randomvariables, Random Structures and Algorithms 3 (1992) 289-304. 4 V. Chvatal, Linear Programming, Freeman, San Francisco, 1983, pp. 195-212. 5 E.G. Coffman, G.S. Lueker, Probabilistic Analysis of Packing and Partitioning Algorithms, Wiley, New York, 1991. 6 M.R. Garey, D.S. Johnson, Computers and Intractability, Freeman, San Francisco, 1979. 7 P.C. Gilmore, R.E. Gomory, A linear programming approach to the cutting-stock problem, Oper. Res. 9 (1961) 849-859. 8 P.C. Gilmore, R.E. Gomory, A linear pr