algorithm - 对象的最佳放置 wrt 成对相似性权重

Question

好的，这是一个抽象的算法挑战，它将保持抽象，因为它是我将要使用它的地方的最高 secret 。

假设我们有一组对象 O = {o_1, ..., o_N} 和一个对称相似度矩阵 S，其中 s_ij 是对象 o_i 和 o_j 的成对相关。

还假设我们有一个一维空间，其中可以放置物体的离散位置(例如将 N 个盒子排成一排或为人们准备椅子)。

有了一定的位置，我们可以衡量从一个物体的位置移动到另一个物体的位置的成本，即在我们到达目标之前需要经过的盒子数量乘以它们成对的物体相似性。从一个位置移动到紧接在该位置之后或之前的盒子是零成本。

想象一个例子，对于三个对象，我们有以下相似度矩阵:

     1.0  0.5  0.8

 S = 0.5  1.0  0.1

     0.8  0.1  1.0

那么，树框中对象的最佳排序显然是:

 [o_3] [o_1] [o_2] 

此排序的成本是从一个对象移动到所有其他对象的成本(计数框)的总和。所以这里我们只计算 o_2 和 o_3 之间的距离等于 1box * 0.1sim = 0.1 的成本，与:

[o_3] [o_1] [o_2] 

另一方面:

[o_1] [o_2] [o_3] 

成本 = 成本(o_1-->o_3) = 1box * 0.8sim = 0.8。

---

目标是确定 N 个对象在可用位置的放置方式，使所有可能的对象对的上述总成本最小化!

一个类比是想象我们有一张 table 和椅子并排排成一排(像盒子一样)，你需要让 N 个人坐在椅子上。现在那些人有一些关系——可以说——他们中的一个人想和另一个人说话的可能性有多大。这是站起来经过一些椅子并与那里的人交谈。当人们坐在两把连续的椅子上时，他们就不需要移动来互相交谈。

那么我们如何才能降低这些人的数量，从而使两个人之间的距离成本最小化。这意味着在夜间，客人步行的总距离接近于最小值。

贪心搜索是……算了!我很想听听是否有此类问题的标准表述，我可以找到一些文献，以及不同的搜索方法(例如组合优化领域的动态规划、禁忌搜索、模拟退火等)。

期待听到您的想法。

附言。我的问题与此线程有一些共同点 Algorithm for ordering a list of Objects ，但我认为这里最好将其作为问题提出，并且可能略有不同。

Answer 1

这听起来像是二次分配问题的一个实例。特殊性是由于这些位置只放在一条线上，但我认为这不会使它更容易解决。 QAP 通常是 NP 难的。除非我误解了你的问题，否则你无法找到在多项式时间内解决问题而不同时证明 P=NP 的最优算法。

如果实例很小，您可以使用精确的方法，例如分支定界法。如果问题更难，您还可以使用禁忌搜索或其他元启发式方法。我们在 HeuristicLab 中实现了 QAP 和一些元启发式算法.您可以在 GUI 中配置问题，只需将相似度和距离矩阵粘贴到适当的参数中即可。尝试从强大的禁忌搜索开始。这是一种较旧但仍然运行良好的算法。如果您想自己实现它，Taillard 在他的网站上也有它的 C 代码。我们的实现基于该代码。

已经有很多关于 QAP 的出版物。更多现代算法将遗传搜索能力与本地搜索启发式相结合(例如 Stützle IIRC 的遗传本地搜索)。