计算科学 - 数字表的最优解 - 吾爱随笔录

数字表的最优解

计算科学优化

2021-12-15 00:16:41

我想最大化下表的分数，从每一列/行中选择一个项目，所以没有两个项目在同一行或列上。最大化分数只是将所有选择加在一起。

* A B C D E

$*\quad A\quad B\quad C\quad D\quad E$

α 16 16 18 18 18

$\alpha\quad 16\quad 16\quad 18\quad 18\quad 18$

β 20 18 16 12 10

$\beta\quad 20\quad 18\quad 16\quad 12\quad 10$

γ 20 18 18 16 16

$\gamma\quad 20\quad 18\quad 18\quad 16\quad 16$

δ 18 18 16 16 8

$\delta\quad 18\quad 18\quad 16\quad 16\quad 8$

ϵ 10 12 14 14 14

$\epsilon\quad 10\quad 12\quad 14\quad 14\quad 14$

例子：（ $^{C}$ 表示选择）

* A B C D E

$*\quad A\quad B\quad C\quad D\quad E$

α 16^{C} 16 18 18 18

$\alpha\quad 16^{C}\quad 16\quad 18\quad 18\quad 18$

β 20 18 16 12 10^{C}

$\beta\quad 20\quad 18\quad 16\quad 12\quad 10^{C}$

γ 20 18^{C} 18 16 16

$\gamma\quad 20\quad 18^{C}\quad 18\quad 16\quad 16$

δ 18 18 16^{C} 16 8

$\delta\quad 18\quad 18\quad 16^{C}\quad 16\quad 8$

ϵ 10 12 14 14^{C} 14

$\epsilon\quad 10\quad 12\quad 14\quad 14^{C}\quad 14$

给出一个分数 $16+10+18+16+14=74$

现在有几种方法可以做到这一点，但首先，有人可以告诉我是否 $88$ 确实是最好的结果，如何通过计算来完成。注意：我是一名数学专业的学生，通常会用图论来解决这样的问题，但想看看计算方法。

4个回答

这称为分配问题。解决它的最常用算法称为匈牙利算法，运行于 $O(n^3)$ 时间。

另一个有趣的观察是它对应于计算热带（最大加）半环中矩阵的永久值。不幸的是，谷歌搜索“热带永久”由于这些词的非数学含义而变得复杂。

这可以表述为线性规划问题。由于您想在每一行和每一列上选择正确的位置，您可以将其表述为找到一个矩阵 $X$ 条目为零和 $1$ 使得每一行和每一列的总和等于 $1$ 和之间的点积 $A$ 和 $X$ 被最大化。

由于我们希望最大化具有线性约束的线性函数，并且我们希望变量取值 $\{0,1\}$ 我们可以放宽这个以允许变量属于 $[0,1]$ . 这是因为线性函数总是在计算域的顶点处达到它们的极值。这就是单纯形算法在这种情况下起作用的原因。

单纯形算法的复杂性显然不是多项式的，但对于一些小例子来说，它确实很有效。

这是使用 linprog 和单纯形算法的 Matlab 实现：

function sci_comp1_mat

A = [16 16 18 18 18; 
     20 18 16 12 10;
     20 18 18 16 16;
     18 18 16 16 8;
     10 12 14 14 14];

n = size(A,1);
f = double(A(:)); % coeffs matrix
% constraints
% sum on lines

C = zeros(2*n,n^2);
for i=1:n
   C(i,linspace((i-1)*n+1,i*n,n))=1;
   C(n+i,linspace(i,n^2-n+i,n))=1;
end
b = ones(2*n,1);

lb = zeros(size(f));
ub = ones(size(f));

options.Algorithm = 'simplex';
x = linprog(-f,C,b,[],[],lb,ub,[],options);
dot(x,f)
x = reshape(x,n,n);
round(x)


Res = A.*x

Res(Res==0) = '';
Res(:)

我同意 88 看起来是最好的分数。

你可能会使用一棵树。根节点包含5个子节点（16 16 18 18 18），每个子节点包含4个子节点（不包括父节点的列）等。

递归遍历树并搜索最高分（广度优先或深度优先）。我实际上不会构建树，只是假装它在那里，并在需要比较它们时查找单元格值。递归函数将传递一个行索引和当前分数，然后为 1-5 个子节点中的每一个调用自身。

这具有 O(N!) 复杂性，因此无法扩展。

如果没有像这样的详尽搜索，要找到最高分听起来很棘手。如果您只想要一个相当好的猜测，那么您可以忽略每个级别得分最低的分支。

我忍不住尝试了匈牙利方法来证明 88 是可以达到的最大值。我在这里找到了一个描述：Bruff, Derek, "The Assignment Problem and the Hungarian Method"，没有任何解释为什么该方法终止了它的运行时间。该算法通过将数字添加到成本矩阵的行或列，将分配问题的成本矩阵转换为新的成本矩阵。文档中的一个定理说：“如果在成本矩阵的任何一行或一列的所有条目中添加或减去一个数字，则结果成本矩阵的最佳分配也是原始成本矩阵的最佳分配”。

这是因为一个数 $a$ 被添加到行或列的所有条目然后任何赋值的值增加 $a$ .

文档中描述的方法找到了最小值。为了找到最大值，我们将成本矩阵乘以 $-1$ 并找到该矩阵的最小值，

所以我们从

  16  16  18  18  18
  20  18  16  12  10
  20  18  18  16  16
  18  18  16  16   8
  10  12  14  14  14

并乘以 $-1$

 -16 -16 -18 -18 -18
 -20 -18 -16 -12 -10
 -20 -18 -18 -16 -16
 -18 -18 -16 -16  -8
 -10 -12 -14 -14 -14

为了避免负数，我们添加 $20$ 到每个元素。对于每一行，我们减去它的最小值。

   4   4   2   2   2   | -2
   0   2   4   8  10   |
   0   2   2   4   4   |
   2   2   4   4  12   | -2
  10   8   6   6   6   | -6

   2   2   0   0   0
   0   2   4   8  10
   0   2   2   4   4
   0   0   2   2  10
   4   2   0   0   0

现在对于每一行，应该减去最小值，但是对于每一行都是 0，所以没有什么可做的。

如果您还没有阅读链接文档，可以忽略以下矩阵。

   +----------------
   |   2   4   8  10
   |   2   2   4   4
   +----------------
   +----------------

我们继续变换矩阵：

   2   2   0   0   0   |
   0   2   4   8  10   | -2
   0   2   2   4   4   | -2
   0   0   2   2  10   |
   4   2   0   0   0   |
  ------------------
  +2

最后，到达

   4   2   0   0   0
   0   0   2   6   8
   0   0   0   2   2
   2   0   2   2  10
   6   2   0   0   0

现在我们选择以下包含的位置0并标记它们x

   4   2   0   x  0
   x   0   2   6   8
   0   0   x   2   2
   2   x   2   2  10
   6   2   0   0   x

这些- 位置在此成本矩阵中显示了可接受的分配，并且它是最小的，因为无法获得x小于的值。0

这种分配对于初始成本矩阵也是最优的。所以我们已经证明了

18+20+18+18+14=88

是最大值。

其它你可能感兴趣的问题

上一篇求解具有纯 Neumann 条件的线性方程组下一篇求解非线性抛物 PDE 的 Crank-Nicolson 方法