algorithm - 按相似度排序

Question

我有一个订单集合。

[a, b]
[a, b, c]
[a, b, c, d]
[a, b, c, d]
[b, c]
[c, d]

其中 a、b、c 和 d 是 SKU，并且有装满它们的大箱子。并且有数千个订单和数百个可能的 SKU。

现在想象一下，在打包这些订单时，如果一个订单缺少上一个订单中的商品，您必须将那个 SKU 的箱子收起来(同样地取出一个您没有的)。

您如何对其进行排序，以使框更改的数量最少？或者，用更编程的术语来说:如何最小化累积汉明距离/最大化集合中相邻项之间的交集？

我真的不知道从哪里开始。已经有一些算法了吗？有合适的近似值吗？

Answer 1

确实@irrelephant 是正确的。这是一个无向哈密顿路径问题。将其建模为一个完整的无向图，其中节点是 sku 集合，每条边的权重是各个集合之间的汉明距离。那么找到一个装箱顺序就相当于找到一条与每个节点恰好接触一次的路径。这是哈密顿路径 (HP)。你想要最小重量的 HP。

坏消息是找到最小权重 HP 是 NP 完全的，这意味着最优解通常需要指数时间。

好消息是有合理的近似算法。明显的贪心算法给出的答案不差于最优 HP 的两倍。它是:

create the graph of Hamming distances
sort the edges by weight in increasing order: e0, e1, ...
set C = emptyset
for e in sequence e0, e1, ...
   if C union {e} does not cause a cycle nor a vertex with degree more than 2 in C
      set C = C union {e}
return C

请注意，if 语句测试可以使用经典的不相交集联合查找算法和顶点中的事件边计数器在几乎恒定的时间内实现。

因此假设计算汉明距离是常数时间，对于 n 个 sku 集，这里的运行时间可以是 O(n^2 log n)。

如果图表不在您的词汇表中，请考虑一个三角形表格，每对 sku 集都有一个条目。表中的条目是汉明距离。您想要对表条目进行排序，然后将 sku 集对按排序顺序逐个添加到您的计划中，跳过会导致“ fork ”或“循环”的对。 fork 是一组像 (a,b)、(b,c)、(b,d) 这样的对。一个循环将是 (a,b), (b,c), (c, a)。

有more complex polynomial time algorithms得到 3/2 的近似值。