1

印刷する必要があるロゴ (最大 4 色) のリストがあります。各ロゴには、そのロゴに必要な塗料を混合するためのセットアップ時間が必要です。同じ色を使用する 2 つのロゴが背中合わせになるようにデータを並べ替えることができれば、多くの色を混ぜる必要がなくなり、お金と時間を節約できます。塗料は、一度混ぜ合わせると寿命があります。

私はこのようなデータセットを見ています...

赤 | 赤 | (その他の色)
赤 | 赤 | 黒
(その他の色) | 黒

それはその順序で終わる必要があります。それは、私が作った赤と黒を1つずつ許可する唯一の注文です. 各共通色に値を割り当てるなど、いくつかのことを試しましたが、何があっても正しく順序付けられないようです。

TSPの問題に基づいて誰かが書いた次のSQL手順を使用しました。( http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=172154 )

次のテストデータを使用して、正しい出力を受け取りました

ルートから削除
都市から削除
都市の値に挿入 ('Black|Red')
都市の値に挿入 ('赤')
都市の値に挿入 ('青')
都市の値に挿入 ('Black')
都市の値に挿入 ('Blue|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

1

これには遺伝的アルゴリズムが適していると思います。ロゴがたくさんある場合、ブルート フォース ソリューションにはかなりの時間がかかる可能性があり、貪欲では良い結果が得られない可能性があります。

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

于 2013-04-27T19:46:04.467 に答える
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 に答える