[科普中国]-分配问题

分配问题

分配问题是一类古典概型问题.即古典概型计算中的分房问题。假设有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

基本条件分配问题的基本条件是:

1.物可辨(相异)或不可辨(相同).

2.盒子可辨或不可辨.

3.分到盒子里的物是有序的或无序的.

4.允许有空盒，或不许有空盒.

物和盒子都是不可辨分配也称为分拆。