更新时间：2022-09-24 10:02
分配问题（distribution problem）一类组合问题。将n件物分到r个盒子里，求不同的分配方法数，就构成了分配问题。所求方法数就是分配数。对于物和盒子给定不同的规定条件，可以构成不同的分配问题。
分配问题是一类古典概型问题。即古典概型计算中的分房问题。假设有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.物可辨（相异）或不可辨（相同）。
2.盒子可辨或不可辨。
3.分到盒子里的物是有序的或无序的。
4.允许有空盒，或不许有空盒。
物和盒子都是不可辨分配也称为分拆。