我有一个需要打印的 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 routes delete from cities insert 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 Matching insert 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
唯一的问题是跑回原来的“城市”(起点和终点都返回黑色),我必须选择一个“起点城市”。如果选择了错误的路线,我最终不会得到最优化的路线。
最佳答案
它看起来像 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 求解器。只需格式化输入并让其他程序完成所有脏活。
关于algorithm - 找到元素的最佳排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16252745/