裝填問題:裝填問題(packing problem)是一類典型的組合最佳 -百科知識中文網

裝填問題

裝填問題(packing problem)是一類典型的組合最佳化問題。設I=v1，v2，…，vm是一個有限集，E=E1，E2，…，En為I的子集所形成的一個集簇，若E的一個子族E′=Ej1，…，Ejs使得I中的每個元素包含在E′的至多一個元素之中，則稱E′為I的一個裝填，求I的一個裝填E′使得所含的元素數為最多就是所謂裝填問題。一般地，賦E中每個元素以一個權，而將E中的元素最多改為其中元素的權和為最大，當每個元素的權均為1時，即這裡所說的裝填問題，若將E′中的每個元素視為一個車廂，這時的裝填問題也被稱為裝箱問題，若E′使得I中的每個元素包含在E′的至少一個元素之中，則稱E′為I的一個覆蓋，求I的一個覆蓋E′使得E′含E中的元素最小就是所謂覆蓋問題，也可以將它推廣到帶權的情形，若E′使得I中的每個元素包含在E′的恰好一個元素之中，則稱E′為I的一個劃分，求I的一個劃分E′使得E′中含的元素數為最少就是劃分問題，同樣可以有帶權情形下之推廣，這裡所述的裝填問題、覆蓋問題，以及劃分問題均是NP完全問題，因此，要想用好的算法解這些問題是不現實的。

基本介紹

圖論中有兩類相互有一定聯繫然而又是性質不同的問題，一類是研究用某種類型的子圖去覆蓋圖G的點集或邊集(即，或)，這就是所謂覆蓋問題。例如正常邊染色是用邊不交的邊無關集覆蓋E(G)；團覆蓋集是用團去覆蓋V(G)等等。一般說來，我們希望用最少個數的子圖去完成覆蓋，這就是最小覆蓋問題。另一類問題是研究從給定圖中，能取出多少個不交的某類子圖，或者反其意而說成是可以往給定圖中裝填多少個不交的某類子圖，這就是 裝填問題。一般說來，我們希望裝填的子圖個數儘可能地多，這就是 最大裝填問題。例如有向圖中弧形式的Menger定理所研究的是往D中裝填弧不交的()路。Menger定理是以最大最小定理的形式研究了能裝填k個弧不交的()路的充分必要條件。