3

对不起这个复杂的名字 - 这是当之无愧的。让我提出问题。

上下文：我有一种定位网络，我想用它做一些分区。

问题定义：我有一个无向加权图 G = {V,E,w}，其中包含一组顶点 V、边 E 和边权重 W。边存在于 V 中的所有顶点之间。

现在，我有大小为 |C1|...|CN| 的循环 C = {C1...CN} st |C1|...|CN| 的总和 等于顶点总数|V|。一个循环 Ci 的得分是路径中所有边的权重之和。

最后，这是目标：我想以这样一种方式拟合 G 中 C 的所有循环，即它们的组合分数在 C 中没有循环相互交叉的约束条件下是最大的。

所以用外行的话来说：我想用定义长度 st 的循环填充一个图形，全局权重是最优的。

我对这个问题的看法：这个问题至少是 NP 难的，因为它可以简化为诸如打包问题或哈密顿循环之类的问题。

最优解甚至可能不是伪多项式。我已经尝试以几种不同的方式（图表）来制定问题，它总是会导致状态爆炸，因此可能无法采用易于处理的 2D 动态编程方法（如果我错了，请纠正我）。

所以看来我可能不得不使用近似方法。想到的一件事是尝试使用其自己的近似方法找到整个图的哈密顿路径。然后下一步是找到“切割”局部最优哈密顿路径以产生循环的位置。有|C|!*|V| 安排这些“切割点”的方法。阶乘来自这些循环的排序和 |V| 的排列。来自起始位置的总数。即使有修剪（即有相同大小的循环），这对于大的|C| 仍然是难以处理的。我想说蛮力对于小的 |C| 是可以的，而对于较大的 |C| 则需要爬山方法来获得局部最优排列的近似值。

无论如何，你们怎么看？

4

1 回答 1

0

根据 David Speyer在此处的评论，我认为您正在研究（多项式可解|V|）线性分配问题。

如果我对您的理解正确，那么您正在尝试在划分节点的循环集空间上优化函数。据我了解，您没有固定周期数或任何单个周期的长度：您唯一的限制是它们是不相交的并且包括每个节点。

如果是这样，每个这样的循环集合都可以用一个节点排列来精确识别。因此，您似乎正在优化节点排列的空间。

让我们调用您的目标函数（当前排列中的边权重的总和）f。 f是节点排列的函数，但我们可以自由选择如何表示这些排列。如果我们选择一个分解为向量的矩阵，那么是点积之和，因此是线性的，符合分配问题的标准。|V|f|V|

编辑

通过回忆每对节点都有一条连接边，可以解决可能必须找到哈密顿循环的问题。完全图是该问题的退化情况：所有节点的任何排序都是哈密顿循环。

如果C是权重矩阵并且P是置换矩阵，则成本函数可以用 matlab/octave 语法写为f(P) = sum(sum(C .* P)). 这.*是成对乘积运算符，它产生一个矩阵，然后在两个维度上相加得到一个标量。由于.*在经典线性代数中没有名称（我知道），我们可以将其写为点积之和。每个点积将超过一行C和一行P（而不是一列。）

匈牙利算法是指派问题的维基百科页面上链接到的多时间算法之一。

于 2012-05-12T23:27:27.543 回答