按顺序排序

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).

有更复杂的多项式时间算法达到3/2近似值.