分配問題(distribution problem)一類組合問題.將n件物分到r個盒子裡，求不同的分配方法數，就構成了分配問題.所求方法數就是分配數.對於物和盒子給定不同的規定條件，可以構成不同的分配問題。
基本介紹
- 中文名：分配問題
- 外文名：distribution problem
- 類別：數學
- 別名：分派問題
- 類屬：最最佳化
- 基本條件：物可辨或不可辨等
分配問題,二次分配問題,基本條件,
分配問題
分配問題是一類古典概型問題.即古典概型計算中的分房問題。假設有N個盒子，分別標有號碼1，2，…，N;此外有n個質點.所謂分配問題，就是如何將質點分配到各個盒子裡去，其中n≤N.假設每個質點分配到各個盒中是等可能的，其分配方式和各種分法的總數如下表：
例如，計算下列兩事件的機率：
1.A={某指定的n個盒子中各有一個質點}.
2.B={恰有n個盒子中各有一個質點}.
四種分配方式按上表順序編號：
- 第一種分配方式(又稱麥克斯韋-玻耳茲曼統計)：每盒可以容納任意個質點且質點可辨，有
2.第二種分配方式(又稱為鮑澤-愛因斯坦統計)：每盒可以容納任意個質點且質點不可辨，有
3.第三種分配方式：每盒至多可以容納一個質點且質點可辨，有
4.第四種分配方式(又稱費米-狄喇克統計)：每盒至多可以容納一個質點但質點不可辨，有
二次分配問題
二次分配問題(quadratic assignment problem, QAP) 是最經典，最具有挑戰性的組合最佳化問題之一。自1957年Koopmans和Beckmann首次將QAP問題作為組合最佳化問題提出之後，其己被廣泛套用於諸多領域，許多問題象積體電路布線、工廠位置布局、打字機鍵盤設計、作業調度問題等等，都可形式化為二次分配問題。此外，QAP問題也被套用於統計數據分析、考古數據排序和接力賽跑隊的排序等。另外，一些NP-hard組合最佳化問題，如旅行商問題(the traveling salesman problem)，三角剖分問題(triangulation problem)和最大團問題(the max clique problem)等也可以轉化為二次分配問題。基於QAP問題理論和實際的重要性，過去幾十年己激發了許多學者對其理論，套用和最佳化技術的研究。
1976年S ahni和Gonzales證明了QAP不僅屬於NP-hard問題而且不存在近似度的多項式時間近似算法。QAP是很難求解的最最佳化問題，其主要原因是所謂的“組合爆炸”現象，求解時間隨問題規模呈指數增長。一般而言，當問題規模n>20時，很難在有效的計算時間內利用經典算法找到其最優解，如分支定界法，割平面法等。為了實際可行地解決QAP問題，人們退而求其次，許多啟發式算法不斷提出並被套用到QAP的求解，如:模擬退火算法，遺傳算法，螞蟻算法，粒子群算法，禁忌搜尋算法和貪婪隨機自適應搜尋算法等。然而，這些啟發式算法不能保證找到的解一定是最優解，他們僅可以在人們可接受的時間內給出較優解。
由於QAP問題高度的計算複雜性和具有代表性的求解難度，許多新的算法，理論和思想在被提出後也常常使用QAP作為測試其自身性能的標準，求解QAP問題己經成為最佳化技術成功的主要體現之一。
基本條件
分配問題的基本條件是:
1.物可辨(相異)或不可辨(相同).
2.盒子可辨或不可辨.
3.分到盒子裡的物是有序的或無序的.
4.允許有空盒，或不許有空盒.
物和盒子都是不可辨分配也稱為分拆。
