c# - 为运输问题优化生成一系列非等成本的算法

Question

我有一个优化器可以解决运输问题，使用所有可能路径的成本矩阵。

优化器运行良好，但如果其中两个成本相等，则解决方案包含的路径多于最小路径数。 (将其视为负载平衡路由器；如果两条路由的成本相同，您将同时使用它们。)

我想要最少数量的路线，为此我需要一个成本矩阵，其中没有两个成本在一定公差范围内相等。

目前，我正在通过一个烘焙函数传递成本矩阵，该函数测试每个条目是否与其他每个条目相等，如果匹配则将其移动一个固定的百分比。然而，这种方法似乎需要进行 N^2 次比较，如果起始值都相同，则最后的成本将大 r^N 次。 (r 是任意固定百分比)。还有一个问题是，通过乘以百分比，您最终会在另一个值之上。所以这个问题似乎有递归的元素，或者至少是重复检查，这会使代码膨胀。

目前的实现基本上不是很好(这里就不贴我的GOTO-using代码给大家mock了)，有待改进。 是否有我所追求的名称，是否有标准实现？

例子:{1,1,2,3,4,5}(公差 = 0.05)变为 {1,1.05,2,3,4,5}

Answer 1

与其将所有值相互比较，不如尝试更线性的方法:

危险!前面的伪代码...

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++