algorithm - 找到元素的最佳排序

Question

我有一个需要打印的 Logo 列表(最多 4 种颜色)。每个 Logo 都需要设置时间来混合该 Logo 所需的颜料。如果我可以对数据进行排序，使两个使用相同颜色的 Logo 背靠背，那么我们就不必混合那么多颜色，从而节省金钱和时间。油漆混合后的使用生命周期有限。

我正在查看这样的数据集...

Red | (Other Color)Red | Black(Other Color) | Black

它需要按此顺序结束。这是唯一允许我制作 1 个红色和 1 个黑色的订单。我尝试了一些方法，例如为每种常见颜色分配一个值，但无论如何，我似乎无法正确排序。

---

我使用了以下有人根据 TSP 问题编写的 SQL 过程。 ( http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=172154 )

使用以下测试数据我收到了正确的输出

delete from routesdelete from citiesinsert into cities values ('Black|Red')insert into cities values ('Red')insert into cities values ('Blue')insert into cities values ('Black')insert into cities values ('Blue|Red')-- Numeric Value is Colors not Matchinginsert into routes values ('Black|Red', 'Red', 3)insert into routes values ('Black|Red', 'Black', 3)insert into routes values ('Red', 'Black', 4)insert into routes values ('Blue|Red', 'Red', 3)insert into routes values ('Blue|Red', 'Black', 4)insert into routes values ('Blue', 'Red', 4)insert into routes values ('Blue', 'Black|Red', 4)insert into routes values ('Blue', 'Black', 4)insert into routes values ('Blue', 'Blue|Red', 3)exec getTSPRoute 'Black'Results:Black->Black|Red->Red->Blue|Red->Blue->Black

唯一的问题是跑回原来的“城市”(起点和终点都返回黑色)，我必须选择一个“起点城市”。如果选择了错误的路线，我最终不会得到最优化的路线。

Answer 1

它看起来像 travelling salesman problem (TSP) .让我解释一下。

首先，考虑一个示例，其中您有一张包含四个城市的 map A、B、C 和 D。 (我在示例中使用了 4，但它与颜色数量无关)。你想找到城市之间的路线，这样你 (1) 只访问每个城市一次，并且 (2) 路线是最短的。 [D,C,A,B] 可能比 [B,A,D,C] 短，而您想要最短的。

现在，您有四个 Logo 而不是城市。你想找到这样的 Logo 排序，在颜色混合方面产生最低成本。如果你把你的每一个标志想象成一个点(城市)，而标志之间的距离是从一种颜色设置到另一种颜色设置之间切换的“成本”，那么你需要找到点之间的最短“路线”。一旦你有了这条最短路线，它就会告诉你应该如何订购标志。例如，可以将两个 Logo L1 和 L2 之间的“距离”定义为 L2 中不在 L1 中的颜色数量。

TSP 是一个众所周知的算法问题。这很难(实际上是 NP-hard )。如果您的输入很小，您可以找到最佳解决方案。如果有 4 个 Logo ，则有 24 种可能的组合。对于 10 个 Logo ，您有 360 万种组合，对于 20 个 Logo ，您有 2432902008176640000 种组合(怎么读？)。因此，对于大于 10-15 的输入，您需要使用一些启发式算法来找到近似解，我相信这对您来说已经足够了。

我会做的是创建一个颜色混合成本图并将其提供给一些 TSP solver

编辑:

• 澄清。并非每个 Logo 都是一个单独的点，但 Logo 中的每组颜色 都是一个点。也就是说:如果您有两个具有相同颜色集的 Logo ，您将它们视为一个点，因为它们将被打印在一起。带有红色、蓝色、黑色 的 Logo 是一个点，带有红色、绿色 的 Logo 是另一个点。
• 而是Hamiltonian path problem比 TSP(你不需要以与开始时相同的颜色集结束)，但变化不大
• 如果您的 Logo 中可能没有匹配项，则首先将您的 Logo 分成不相交的组，这些组之间没有匹配项，然后分别考虑每个组。如果您的任何 Logo 之间都没有匹配项，那么您将无能为力:)
• 实际上，我会使用 python，也许 networkx库将您的问题建模为图形，稍后我会将其传递给某个 TSP 求解器。只需格式化输入并让其他程序完成所有脏活。