Найти оптимальный порядок элементов

Question

У меня есть список логотипов (до 4 цветов), которые необходимо распечатать. Для каждого логотипа требуется время настройки для смешивания красок, необходимых для этого логотипа. Если я могу сортировать данные так, чтобы два логотипа, которые используют одни и те же цвета, вернулись назад, тогда нам не нужно будет смешивать столько цветов, сколько денег и времени. Краски имеют ограниченный срок службы после смешивания.

Я смотрю на наборе данных, как это ...

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

Она должна закончиться в этом порядке. Это единственный порядок, который позволит сделать 1 красный для меня и 1 черный. Я пробовал несколько вещей, таких как назначение значения для каждого общего цвета, но, несмотря ни на что, я не могу заставить его упорядочить правильно.

---

Я использовал следующую процедуру SQL, которую кто-то написал на основе проблемы с TSP. (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 

Единственная проблема бежит обратно в исходное «город» (Black вернулся как для начала и конца), и у меня есть выбрать «начальный город». Если выбрано неправильное, я не получаю наиболее оптимизированный маршрут.

Answer 1

Похож на travelling salesman problem (TSP). Позволь мне объяснить.

Во-первых, рассмотрите пример, где у вас есть карта с четырьмя городами A, B, C и D. (Я использую 4 в примере, но это не имеет никакого отношения к количеству цветов). Вы хотите найти маршрут между городами, чтобы вы (1) посещали каждый город только один раз и (2) маршрут был как можно короче. [D,C,A,B] может быть короче, чем [B,A,D,C], и вам нужен самый короткий.

Теперь, вместо городов, у вас есть четыре логотипа. Вы хотите найти такой порядок логотипов, который дает минимальную стоимость с точки зрения смешивания цветов. Если вы представляете, что каждый из ваших логотипов является точкой (городом), а расстояние между логотипами - это «стоимость» переключения между одним цветом, установленным на другое, то вам нужно найти кратчайший «маршрут» между точками. Когда у вас будет этот самый короткий маршрут, он расскажет вам, как вы должны заказать логотипы. «Расстояние» между двумя логотипами L1 и L2 можно определить, например, как количество цветов в L2, которые не находятся в L1.

TSP это хорошо известная алгоритмическая проблема. И это сложно (на самом деле, NP-hard). Если ваш вход небольшой, вы можете найти лучшее решение. В случае 4 логотипов у вас есть 24 возможных комбинаций. Для 10 логотипов у вас есть 3,6 миллиона комбинаций и для 20 логотипов вы получаете комбинации 2432902008176640000 (как читать это?). Поэтому для ввода более 10-15 вам нужно использовать некоторую эвристику, которая найдет приблизительное решение, которое, я уверен, достаточно для вас.

Что я буду делать то, что я хотел бы создать график затрат смешивания цветов и подачи его в каком-то TSP solver

EDIT:

• разъяснения. Не каждый логотип является отдельной точкой, но каждый набор цветов в логотипе - это точка. То есть: если у вас есть два логотипа с одинаковым набором цветов, вы считаете их единственной точкой, потому что они будут напечатаны вместе. Логотипы с красный, синий, черный находятся на точке и логотипы с красный, зеленый - еще один момент.
• Это довольно Hamiltonian path problem чем TSP (вы не должны заканчиваться тем же цветом, установленной в начале), но это не сильно изменится
• Если не может быть ни одного матча в ваших логотипов, то первый раскол ваши логотипы в непересекающиеся группы, которые не имеют совпадений между ними, а затем рассматривают каждую группу отдельно. Если между любыми вашими логотипами нет совпадений, то вы не можете сделать много :)
• Практически, я бы использовал библиотеку python и, возможно, networkx, чтобы смоделировать вашу проблему в виде графика, а позже я передам ее в какой-либо решатель TSP. Просто отформатируйте ввод и заставьте какую-нибудь другую программу выполнять всю грязную работу.

Answer 2

Для разумного количества логотипов и цветов простым способом может быть подход brute-force, в котором вы просматриваете все комбинации и увеличиваете счетчик каждый раз, когда требуется смешение. После этого вы сортируете комбинации с помощью этого счетчика и выбираете тот, который имеет самое низкое значение.

ПСЕВДОКОД

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

order combination by cost (ascending) 

Вы не упомянули, если вы используете (или собираетесь) любой вид инструмента (таблицы, язык программирования, ...), в котором вы предназначенный выполнить такого рода.

Edit:

Вот быстрое внедрение в 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 

Answer 3

Я подозреваю, что генетический алгоритм был бы хорош для этого. Если у вас много логотипов, решение грубой силы может занять довольно много времени, и жадные вряд ли приведут к хорошим результатам.

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