什么是二次分配问题 (QAP)？
二次分配问题 (Quadratic Assignment Problem, 简称 QAP) 是一个著名的优化难题，它的核心在于如何将一组设施分配到一组位置上，同时我们要考虑到设施之间的两两距离以及它们之间的流量。
我们的目标是找到一种最优的分配方案，使得在综合考虑距离和流量的情况下，总成本或总距离最小化。
为了将 QAP 形式化为一个二次目标函数，我们可以利用距离矩阵和流量矩阵，并施加相应的约束条件：每个设施必须恰好分配到一个位置，且每个位置只能容纳一个设施。
计算复杂度与解决思路
QAP 是一个典型的 NP-hard 问题 的例子。这意味着，随着问题规模（设施数量）的增加，计算出最佳解的难度会呈指数级增长。因此，为了在实际应用中快速找到足够好的解，许多算法和启发式方法应运而生。
针对不同的问题结构，我们通常使用以下几类算法：
- 精确算法 (Precise algorithms)
- 近似算法 (Approximation algorithms)
- 元启发式算法 (Metaheuristics)：如遗传算法和模拟退火
- 专用算法 (Specialized algorithms)
实例演示
题目：假设我们有四个设施 (F1, F2, F3, F4) 和四个位置 (L1, L2, L3, L4)。
- 我们有一个设施成本矩阵，表示设施之间的两两距离或成本。
- 此外，我们还有一个流量矩阵，表示位置之间的交互或流量。
任务：我们需要找到一种分配方案，使得基于设施和位置之间交互的总成本最小化。约束条件是：每个设施必须恰好分配到一个位置，且每个位置只能容纳一个设施。
设施成本矩阵：
L1
L3
—
—
0
3
2
1
3
0
1
2
流量矩阵：
F1
F3
—
—
0
2
1
4
2
0
3
1
为了解决这个 QAP 问题，我们可以使用各种优化技术，例如数学规划、启发式算法或元启发式算法。这些技术的目的是在搜索空间中进行探索，以找到最优解或接近最优的解。
最终，QAP 的解将为我们提供一个设施到位置的分配方案，该方案能使整体成本最小化。
—
C++ 代码实现
让我们来看看如何用 C++ 实现这个解决方案。我们将使用 std::next_permutation 来遍历所有可能的分配情况，并计算每种情况下的总成本，从而找出最小值。
#include
#include
#include
using namespace std;
int calculateTotalCost(const vector<vector>& facilities, const vector<vector>& locations, const vector& assignment) {
int totalCost = 0;
int n = facilities.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int facility1 = assignment[i];
int facility2 = assignment[j];
int location1 = i;
int location2 = j;
totalCost += facilities[facility1][facility2] * locations[location1][location2];
}
}
return totalCost;
}
int main() {
// Facilities cost matrix
vector<vector> facilities = {
{0, 2, 3, 1},
{2, 0, 1, 4},
{3, 1, 0, 2},
{1, 4, 2, 0}
};
// Flow matrix
vector<vector> locations = {
{0, 1, 2, 3},
{1, 0, 4, 2},
{2, 4, 0, 1},
{3, 2, 1, 0}
};
int n = facilities.size();
// Generate initial assignment (0, 1, 2, 3)
vector assignment(n);
for (int i = 0; i < n; i++) {
assignment[i] = i;
}
// Calculate the initial total cost
int minCost = calculateTotalCost(facilities, locations, assignment);
vector minAssignment = assignment;
// Generate all permutations of the assignment
while (next_permutation(assignment.begin(), assignment.end())) {
int cost = calculateTotalCost(facilities, locations, assignment);
if (cost < minCost) {
minCost = cost;
minAssignment = assignment;
}
}
// Print the optimal assignment and total cost
cout << "Optimal Assignment: ";
for (int i = 0; i < n; i++) {
cout << "F" << (minAssignment[i] + 1) <L" << (i + 1) << " ";
}
cout << endl;
cout << "Total Cost: " << minCost << endl;
return 0;
}
Java 代码实现
同样，我们也可以在 Java 中实现相同的逻辑。这里我们需要手动实现类似 next_permutation 的功能来遍历所有排列。
// Java code for the above approach
import java.util.*;
class GFG {
static void swap(List assignment, int left, int right)
{
// Swap the data
int temp = assignment.get(left);
assignment.set(left, assignment.get(right));
assignment.set(right, temp);
}
// Function to reverse the sub-list
// starting from left to the right
// both inclusive
static void reverse(List assignment, int left, int right)
{
// Reverse the sub-list
while (left < right) {
swap(assignment, left, right);
left++;
right--;
}
}
// Function to find the next permutation
// of the given integer list
static boolean next_permutation(List assignment)
{
// If the list is empty or contains only one element
// there is no next permutation
if (assignment.size() = 0 && assignment.get(i) >= assignment.get(i + 1))
i--;
// If i is the first index of the list, that means the entire list is sorted in decreasing order
if (i < 0)
return false;
// Find the rightmost successor to the pivot
int j = assignment.size() - 1;
while (assignment.get(j) <= assignment.get(i))
j--;
// Swap the pivot with the successor
swap(assignment, i, j);
// Reverse the suffix
reverse(assignment, i + 1, assignment.size() - 1);
return true;
}
static int calculateTotalCost(int[][] facilities, int[][] locations, int[] assignment) {
int totalCost = 0;
int n = facilities.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int facility1 = assignment[i];
int facility2 = assignment[j];
int location1 = i;
int location2 = j;
totalCost += facilities[facility1][facility2] * locations[location1][location2];
}
}
return totalCost;
}
public static void main(String[] args) {
// Facilities cost matrix
int[][] facilities = {
{0, 2, 3, 1},
{2, 0, 1, 4},
{3, 1, 0, 2},
{1, 4, 2, 0}
};
// Flow matrix
int[][] locations = {
{0, 1, 2, 3},
{1, 0, 4, 2},
{2, 4, 0, 1},
{3, 2, 1, 0}
};
int n = facilities.length;
// Generate initial assignment (0, 1, 2, 3)
List assignment = new ArrayList();
for (int i = 0; i i).toArray();
int minCost = calculateTotalCost(facilities, locations, currentArr);
int[] minArr = currentArr.clone();
// Generate all permutations of the assignment
while (next_permutation(assignment)) {
currentArr = assignment.stream().mapToInt(i -> i).toArray();
int cost = calculateTotalCost(facilities, locations, currentArr);
if (cost < minCost) {
minCost = cost;
minArr = currentArr.clone();
}
}
// Print the optimal assignment and total cost
System.out.print("Optimal Assignment: ");
for (int i = 0; i L" + (i + 1) + " ");
}
System.out.println();
System.out.println("Total Cost: " + minCost);
}
}