基于连续项目的相似性的双面项目
我正在寻找某种“Domino排序”算法，它根据后续项目的“相切”边的相似性对双侧项目列表进行排序。
假设以下列表项目由2元组表示：
>>> items
[(0.72, 0.12),
(0.11, 0.67),
(0.74, 0.65),
(0.32, 0.52),
(0.82, 0.43),
(0.94, 0.64),
(0.39, 0.95),
(0.01, 0.72),
(0.49, 0.41),
(0.27, 0.60)]
目标是对该列表进行排序，使得每两个后续项目（损失）的正切结尾的平方差的总和最小：
>>> loss = sum(
... (items[i][1] - items[i+1][0])**2
... for i in range(len(items)-1)
... )
对于上面的例子，这可以通过仅仅处理所有可能的排列来计算，但对于具有更多项目的列表来说，这变得很快不可行（ O(n!) ）。
在此处勾画逐步选择最佳匹配的方法
def compute_loss(items):
return sum((items[i][1] - items[i+1][0])**2 for i in range(len(items)-1))
def domino_sort(items):
best_attempt = items
best_score = compute_loss(best_attempt)
for i in range(len(items)):
copy = [x for x in items]
attempt = [copy.pop(i)]
for j in range(len(copy)):
copy = sorted(copy, key=lambda x: abs(x[0] - attempt[-1][1]))
attempt.append(copy.pop(0))
score = compute_loss(attempt)
if score < best_score:
best_attempt = attempt
best_score = score
return best_attempt, best_score
给出以下结果，损失0.1381 ：
[(0.01, 0.72),
(0.72, 0.12),
(0.11, 0.67),
(0.74, 0.65),
(0.49, 0.41),
(0.39, 0.95),
(0.94, 0.64),
(0.82, 0.43),
(0.32, 0.52),
(0.27, 0.6)]
然而，这不是最好的解决方案
[(0.01, 0.72),
(0.82, 0.43),
(0.27, 0.6),
(0.49, 0.41),
(0.32, 0.52),
(0.39, 0.95),
(0.94, 0.64),
(0.72, 0.12),
(0.11, 0.67),
(0.74, 0.65)]
亏损0.0842 。 显然，上述算法对前几个项目表现良好，但最后一项算法的差异变得如此之大，以至于它们主宰了损失。
是否有任何算法可以在可接受的时间依赖性下执行这种排序（对于数百个项目列表可行）？
如果不可能以小于O(n!)方式进行这种排序，是否有任何可能返回好分数（小损失）的近似方法？
一般来说，这个问题是关于找到一个与着名的旅行商问题（TSP）密切相关的最小长度的哈密尔顿路径。 它看起来不像这个问题的特殊情况，可以在多项式时间内解决。
有大量的启发式算法和近似算法来解决TSP问题。 这个维基百科文章可能是一个很好的开始。
稍微更高效的使用平分法的朴素方法。
（实现荣誉：https：//stackoverflow.com/a/12141511/6163736）
# Domino Packing
from bisect import bisect_left
from pprint import pprint
def compute_loss(items):
return sum((items[i][1] - items[i+1][0])**2 for i in range(len(items)-1))
def find_nearest(values, target):
"""
Assumes values is sorted. Returns closest value to target.
If two numbers are equally close, return the smallest number.
"""
idx = bisect_left(values, target)
if idx == 0:
return 0
if idx == len(values):
return -1
before = values[idx - 1]
after = values[idx]
if after - target < target - before:
return idx # after
else:
return idx - 1 # before
if __name__ == '__main__':
dominos = [(0.72, 0.12),
(0.11, 0.67),
(0.74, 0.65),
(0.32, 0.52),
(0.82, 0.43),
(0.94, 0.64),
(0.39, 0.95),
(0.01, 0.72),
(0.49, 0.41),
(0.27, 0.60)]
dominos = sorted(dominos, key=lambda x: x[0])
x_values, y_values = [list(l) for l in zip(*dominos)]
packed = list()
idx = 0
for _ in range(len(dominos)):
x = x_values[idx]
y = y_values[idx]
del x_values[idx]
del y_values[idx]
idx = find_nearest(x_values, y)
packed.append((x, y))
pprint(packed)
print("loss :%f" % compute_loss(packed))
输出 ：
[(0.01, 0.72),
(0.72, 0.12),
(0.11, 0.67),
(0.74, 0.65),
(0.49, 0.41),
(0.39, 0.95),
(0.94, 0.64),
(0.82, 0.43),
(0.32, 0.52),
(0.27, 0.6)]
loss :0.138100
这个理论问题已经在其他答案中讨论过了。 我试图改进你的“最近的未访问邻居”算法。
在进入alogrithms之前，请注意，你可以明显地用pop(min_index)替换sorted + pop(0) pop(min_index) ：
min_index, _ = min(enumerate(copy), key=lambda i_x: abs(i_x[1][0] - attempt[-1][1]))
attempt.append(copy.pop(min_index))
方法1：改进基本方法
我以一个非常简单的想法为指导：不仅仅考虑下一个多米诺骨牌的左侧，以确定它是否与当前序列的右侧相匹配，为什么不在右侧添加约束呢？
我尝试过：检查候选人右侧是否接近剩余的多米诺骨牌的左侧。 我认为找到“接下来的”多米诺骨牌更容易，右侧靠近剩余左侧的平均值。 因此我对你的代码做了如下修改：
mean = sum(x[0] for x in copy)/len(copy)
copy = sorted(copy, key=lambda x: abs(x[0] - attempt[-1][1]) + abs(x[1]-mean)) # give a bonus for being close to the mean.
但这不是一个改进。 100个随机系列的100个项目（所有值在0和1之间）的累计损失为：
经过一些调整后，我试图将奖金转化为罚分：
mean = sum(x[0] for x in copy)/len(copy)
copy = sorted(copy, key=lambda x: 2*abs(x[0] - attempt[-1][1]) - abs(x[1]-mean)) # note the 2 times and the minus
这一次有了明显的改善：
但为什么？ 我做了一点研究。 显然，原始算法在开始时表现更好，但新算法“消耗”了大的多米诺骨牌（左右之间有很大的差距），因此表现更好。
因此我专注于差距：
copy = sorted(copy, key=lambda x: 2*abs(x[0] - attempt[-1][1]) - abs(x[1]-x[0]))
这个想法很清楚：在其他人之前消耗大的多米诺骨牌。 这工作得很好：
方法2：改进给定的顺序
好吧，现在是一个更复杂的启发式。 我从Lin-Kernighan启发式中获得灵感。 我尝试构建满足以下条件的交换序列：在最后一次交换导致交换的多米诺骨牌之一的局部损失减少后立即停止序列。 估计每个交换序列都会找到最好的。
代码将比一个长的解释更清晰：
def improve_sort(items, N=4):
"""Take every pair of dominos and try to build a sequence that will maybe reduce the loss.
N is the threshold for the size of the subsequence"""
ret = items
ret = (items, compute_loss(items))
for i in range(len(items)):
for j in range(i+1, len(items)):
# for every couple of indices
r = try_to_find_better_swap_sequence(ret, [i, j], N)
if r[1] < ret[1]:
ret = r
return ret
def try_to_find_better_swap_sequence(ret, indices, N):
"""Try to swap dominos until the local loss is greater than in the previous sequence"""
stack = [(indices, ret[0])] # for an iterative DFS
while stack:
indices, items = stack.pop()
# pop the last indices
j = indices.pop()
i = indices.pop()
# create a copy and swap the i-th and the j-th element
items2 = list(items)
items2[i] = items[j]
items2[j] = items[i]
loss = compute_loss(items2)
if loss < ret[1]:
ret = (items2, loss)
if len(indices) <= N-3: # at most N indices in the sequence
# continue if there is at least one local improvement
if local_loss(items2, i) < local_loss(items, i): # i was improved
stack.extend((indices+[i,j,k], items2) for k in range(j+1, len(items2)))
if local_loss(items2, j) < local_loss(items, j): # j was improved
stack.extend((indices+[j,i,k], items2) for k in range(i+1, len(items2)))
return ret
def local_loss(items, i):
"""This is the loss on the left and the right of the domino"""
if i==0:
return (items[i][1] - items[i+1][0])**2
elif i==len(items)-1:
return (items[i-1][1] - items[i][0])**2
else:
return (items[i-1][1] - items[i][0])**2+(items[i][1] - items[i+1][0])**2
结论
第二种方法仍然不理想（在原始items上尝试）。 它显然比第一个慢，但结果更好，甚至不需要预先排序。 （考虑使用shuffle来避免退化的情况）。
你也可以看看这个。 对下一个可能的多米诺骨牌进行评分的方法是将剩下的多米诺骨牌洗牌多次，并对每次洗牌进行总结。 最低累积损失可能会给你一个很好的下一个多米诺骨牌。 我没有尝试......
链接地址: http://www.djcxy.com/p/40183.html上一篇: sided items based on the similarity of consecutive items
下一篇: What is difference between different asymptotic notations?