1

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

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

红色 | (其他颜色)
红色 | 黑色的
(其他颜色) | 黑色的

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


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

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

从路线中删除
从城市中删除
插入城市值('Black|Red')
插入城市值(“红色”)
插入城市值(“蓝色”)
插入城市值(“黑色”)
插入城市值('蓝色|红色')

-- 数值是颜色不匹配

插入路线值('Black|Red','Red',3)
插入路线值('Black|Red','Black',3)
插入路线值('Red','Black',4)
插入路线值('Blue|Red', 'Red', 3)
插入路线值('Blue|Red', 'Black', 4)
插入路线值('Blue','Red',4)
插入路线值('Blue','Black|Red',4)
插入路线值('Blue','Black',4)
插入路线值('Blue','Blue|Red',3)

exec getTSPRoute '黑色'

结果:
黑->黑|红->红->蓝|红->蓝->黑

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

4

3 回答 3

4

它看起来像旅行商问题(TSP)。让我解释。

首先,考虑一个示例,您的地图包含四个城市AB和。(我在示例中使用 4 但它与颜色数量无关)。您想找到城市之间的路线,因此您 (1) 每个城市只访问一次,并且 (2) 路线是最短的。可能会更短,你想要最短的。CD[D,C,A,B][B,A,D,C]

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

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

我要做的是创建一个颜色混合成本图表并将其提供给一些TSP 求解器

编辑

  • 澄清。并非每个徽标都是一个单独的点,但徽标中的每组颜色都是一个点。也就是说:如果您有两个具有相同颜色集的徽标,则将它们视为一个点,因为它们将被打印在一起。红色、蓝色、黑色的标志在一个点,红色、绿色的标志是另一个点。
  • 这更像是哈密顿路径问题而不是 TSP(你不需要以与开始时相同的颜色集结束),但它并没有太大变化
  • 如果您的徽标中可能没有匹配项,则首先将您的徽标分成不相交的组,它们之间没有匹配项,然后分别考虑每个组。如果您的任何徽标之间没有匹配项,那么您将无能为力:)
  • 实际上,我会使用 python 和networkx库将您的问题建模为图形,然后我会将它传递给一些 TSP 求解器。只需格式化输入并让其他程序完成所有肮脏的工作。
于 2013-04-27T14:52:19.273 回答
1

对于合理数量的徽标和颜色,一种简单的方法是蛮力方法,在这种方法中,您遍历所有组合并在每次需要混合时增加一个计数器。之后,您按该计数器对组合进行排序并选择具有最低值的组合。

伪代码

foreach combination
    foreach print
        foreeach color 
            if not previous_print.contains(color)
                cost++

order combination by cost (ascending)

您没有提及您是否正在使用(或即将使用)您打算在其中执行此类操作的任何类型的工具(电子表格、编程语言……)。

编辑:

这是 VB.NET 中的快速实现。请注意,为了便于阅读和理解,特意保留了代码。

Private Sub GoGoGo()
    ' Adds some logos 
    ' This is where you add them from the database or text file or wherever
    Dim logos() =
    {
        New String() {"Black", "Magenta", "Orange"},
        New String() {"Red", "Green", "Blue"},
        New String() {"Orange", "Violet", "Pink"},
        New String() {"Blue", "Yellow", "Pink"}
    }

    ' Used to store the best combination
    Dim minimumPermutation
    Dim minimumCost = Integer.MaxValue

    ' Calculate all permutations of the logos
    Dim permutations = GetPermutations(logos)

    ' For each permutation
    For i As Integer = 0 To permutations.Count() - 1
        Dim permutation = permutations(i)
        Dim cost = 0

        ' For each logo in permutation
        For j As Integer = 0 To permutation.Count() - 1
            Dim logo = permutation(j)

            ' Check whether the previous logo contains one or more colors of this logo
            For Each color In logo
                If (j > 0) Then
                    If Not permutation(j - 1).Contains(color) Then
                        cost += 1
                    End If
                Else
                    cost += 1
                End If
            Next
        Next

        ' Save the best permutation
        If (i = 0 Or cost < minimumCost) Then
            minimumCost = cost
            minimumPermutation = permutation.Clone()
        End If
    Next

    ' Output the best permutation
    For Each logo In minimumPermutation
        Console.Write(logo(0) + " " + logo(1) + " " + logo(2))
    Next
End Sub

Public Shared Iterator Function GetPermutations(Of T)(values As T(), Optional fromInd As Integer = 0) As IEnumerable(Of T())
    If fromInd + 1 = values.Length Then
        Yield values
    Else
        For Each v In GetPermutations(values, fromInd + 1)
            Yield v
        Next

        For i = fromInd + 1 To values.Length - 1
            SwapValues(values, fromInd, i)
            For Each v In GetPermutations(values, fromInd + 1)
                Yield v
            Next
            SwapValues(values, fromInd, i)
        Next
    End If
End Function

Private Shared Sub SwapValues(Of T)(values As T(), pos1 As Integer, pos2 As Integer)
    If pos1 <> pos2 Then
        Dim tmp As T = values(pos1)
        values(pos1) = values(pos2)
        values(pos2) = tmp
    End If
End Sub
于 2013-04-27T14:09:56.030 回答
1

我怀疑遗传算法会对此有好处。如果你有很多标志,一个蛮力解决方案可能需要相当长的时间,而且贪婪不太可能产生好的结果。

http://en.wikipedia.org/wiki/Genetic_algorithm

于 2013-04-27T19:46:04.467 回答