Алгоритм генерации массива неравных затрат для оптимизации транспортной задачи

Question

У меня есть оптимизатор, который решает транспортную проблему, используя матрицу затрат всех возможных путей.

Оптимизатор работает нормально, но если две из этих затрат равны, решение содержит еще один путь, чем минимальное количество путей. (Думайте об этом как о маршрутизаторах с балансировкой нагрузки; если два маршрута стоят одинаково, вы будете использовать их оба.)

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

В данный момент я передаю матрицу затрат через функцию выпечки, которая проверяет каждую запись на равенство для каждой из других записей и перемещает ее на фиксированный процент, если он совпадает. Однако этот подход требует N ^ 2 сравнений, и, если все начальные значения одинаковы, последняя стоимость будет на R ^ N больше. (r - произвольный фиксированный процент). Также существует проблема, заключающаяся в том, что, умножая на процент, вы попадаете поверх другого значения. Таким образом, проблема, кажется, имеет элемент рекурсии или, по крайней мере, повторной проверки, который раздувает код.

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

Пример: {1,1,2,3,4,5} (tol = 0,05) становится {1,15,2,3,4,5}

Answer 1

Не слишком требователен, но я думаю, что вы описываете проблему кратчайшего пути.

«Транспортная проблема» в ИЛИ - гораздо более специфическая проблема с одним набором отправителей и одним набором мест назначения. В вашей задаче у вас есть пути через несколько точек, но иногда вы получаете два кратчайших пути, потому что затраты составляют в целом одну и ту же сумму. Правильно?

Вот хорошая статья о работе с избыточностью во всех парах задач кратчайшего пути.

Answer 2

вместо сравнения всех значений друг с другом попробуйте более линейный подход:

опасность! впереди псевдокод ...

seen = {}
for i=0:
  for j=0:
    if cost_matrix[i,j] in seen:
      cost_matrix[i,j] = cost_matrix[i,j]+percentage
    append cost_matrix[i,j] to seen
    j++
  i++