分配問題

分配問題是一類古典概型問題。即古典概型計算中的分房問題。假設有N個盒子，分別標有號碼1，2，…，N；此外有n個質點。所謂分配問題，就是如何將質點分配到各個盒子裏去，其中n≤N。假設每個質點分配到各個盒中是等可能的，其分配方式和各種分法的總數如下表：

例如，計算下列兩事件的概率：

1.A={某指定的n個盒子中各有一個質點}。

2.B={恰有n個盒子中各有一個質點}。

四種分配方式按上表順序編號：

1.第一種分配方式（又稱麥克斯韋-玻耳茲曼統計）：每盒可以容納任意個質點且質點可辨，有

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年Sahni和Gonzales證明了QAP不僅屬於NP-hard問題而且不存在近似度的多項式時間近似算法。QAP是很難求解的最優化問題，其主要原因是所謂的“組合爆炸”現象，求解時間隨問題規模呈指數增長。一般而言，當問題規模n>20時，很難在有效的計算時間內利用經典算法找到其最優解，如分支定界法、割平面法等。為了實際可行地解決QAP問題，人們退而求其次，許多啓發式算法不斷提出並被應用到QAP的求解，如模擬退火算法、遺傳算法、螞蟻算法、粒子羣算法、禁忌搜索算法和貪婪隨機自適應搜索算法等。然而，這些啓發式算法不能保證找到的解一定是最優解，他們僅可以在人們可接受的時間內給出較優解。

由於QAP問題高度的計算複雜性和具有代表性的求解難度，許多新的算法，理論和思想在被提出後也常常使用QAP作為測試其自身性能的標準，求解QAP問題已經成為優化技術成功的主要體現之一。 ^[1] 

分配問題的基本條件是：

1.物可辨（相異）或不可辨（相同）。

2.盒子可辨或不可辨。

3.分到盒子裏的物是有序的或無序的。

4.允許有空盒，或不許有空盒。

物和盒子都是不可辨分配也稱為分拆。