好吧，这是一个抽象的算法挑战，它将保持抽象，因为这是我将要使用它的最高机密。
假设我们有一组对象O={O_1，…，O_N}和一个对称相似矩阵S，其中S i j是对象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）=1箱*0.8sim=0.8。
目标是确定n个对象在可用位置的位置，这样我们就可以最小化所有可能的对象对的上述总成本！
一个类似的设想是，我们只有一排桌子和椅子（像盒子一样）并排摆放，你需要安排N个人坐在椅子上现在那些PPL有一些关系，比如说，其中一个想要和另一个说话的可能性有多大。这是站起来经过几把椅子和那边的人说话。当人们连续坐在两张椅子上时，他们不需要移动就可以相互交谈。
所以我们怎样才能把ppl降下来，使两个ppl之间的每一个距离成本最小化。这意味着在夜间，客人步行的总距离接近最小。
贪婪的搜索是…好吧，算了吧！
我感兴趣的是，是否有一个标准的公式，我可以找到一些文献，以及不同的搜索方法（如动态规划，禁忌搜索，模拟退火等，从组合优化领域）。
期待听到你的想法。
另外，我的问题和这篇文章有一些共同点，但我认为这里最好把它作为问题来提出，可能会有点不同。
最佳答案
听起来像是二次分配问题的一个例子。这个特长是因为位置只放在一条线上，但我不认为这会使问题更容易解决。qap一般是np难的。除非我误解了你的问题，否则你找不到一个在多项式时间内解决问题而不同时证明p=np的最优算法。
如果实例很小，则可以使用分支和绑定等精确方法。如果问题比较困难，也可以使用禁忌搜索或其他元启发式方法。我们在HeuristicLab中实现了qap和一些元启发式。您可以在gui中配置问题，只需将相似度和距离矩阵粘贴到适当的参数中。试着从强烈的禁忌搜索开始这是一个旧的，但仍然很好的工作算法。如果你想自己实现的话，Taillard的网站上也有C代码。我们的实现基于该代码。
关于QAP的出版物已经有很多了。更现代的算法结合了遗传搜索能力和局部搜索启发（例如，来自Stützle IIRC的遗传局部搜索）。