0

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

假设我们有一组对象 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 个对象在可用位置的位置，以使上述所有可能的对象对的总成本最小化！

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

那么我们如何才能放下这些 ppl 以使两个 ppl 之间的每个距离成本最小化。这意味着在夜间，客人步行的总距离接近最低限度。

贪婪搜索是……好吧，算了吧！我很想知道是否有这样的问题的标准公式，我可以找到一些文献，以及不同的搜索方法（例如组合优化领域的动态规划、禁忌搜索、模拟退火等）。

期待听到你的想法。

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

4

3 回答 3

1

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

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

QAP 已经发表了很多文章。更现代的算法将遗传搜索能力与局部搜索启发式结合起来（例如 Stützle IIRC 的遗传局部搜索）。

于 2012-11-23T07:10:12.633 回答
0

让我用简单的排序方法来帮助（我自己的）线程。

1. 对相似度矩阵的上半部分进行排序。
2. 从具有最高相似度权重的对象对开始，将它们放在中心位置。

3. 下一个对象可以放在它们的左侧或右侧。因此，每次您都可以选择放在左侧或右侧时对预先放置的对象具有最高成本的对象。转到第 2 步。

选择第 3 步是因为如果您离开此对象并稍后放置，则此成本将再次成为剩余的最大成本，甚至更多（距离预先放置的对象更远）。因此，昂贵的展示位置应该尽早完成。

这太简单了，当然没有找到好的解决方案。

另一种方法是

1. 从以某种方式生成的完整排序开始（随机或来自其他算法）

2.尝试使用对象对的“交换”来改进它。

我相信局部最小值将是一个巨大的威慑。

于 2012-11-22T14:14:11.453 回答
0

这是已经发布的方法的变体。我认为这不是最佳选择，但它可能是一个开始。

Create a list of all the pairs in descending cost order.
While list not empty:
  Pop the head item from the list.
  If neither element is in an existing group, create a new group containing
     the pair.
  If one element is in an existing group, add the other element to whichever
     end puts it closer to the group member.
  If both elements are in existing groups, combine them so as to minimize
     the distance between the pair.

组组合可能需要在组中颠倒顺序，并且数据结构应该被设计为支持这一点。

于 2012-11-22T17:08:22.047 回答