加油站变型算法的验证

Question

​

​

我正在研究这个问题，我认为这是加油站问题的一个变体。因此，我采用贪婪算法来解决这个问题。我想问是否有人帮助我指出我的算法是正确的或不正确的，谢谢。

我的算法

  var x = input.distance, cost = input.cost, c = input.travelDistance, price = [Number.POSITIVE_INFINITY];
  var result = [];

  var lastFill = 0, tempMinIndex = 0, totalCost = 0;

  for(var i=1; i<x.length; i++) {
    var d = x[i] - x[lastFill];
    if(d > c){ //car can not travel to this shop, has to decide which shop to refill in the previous possible shops
      result.push(tempMinIndex);
      lastFill = tempMinIndex;
      totalCost += price[tempMinIndex];
      tempMinIndex = i;
    }
    //calculate price
    price[i] = d/c * cost[i];
    if(price[i] <= price[tempMinIndex])
      tempMinIndex = i;
  }

  //add last station to the list and the total cost
  if(lastFill != x.length - 1){
    result.push(x.length - 1);
    totalCost += price[price.length-1];
  }

您可以在此链接https://drive.google.com/file/d/0B4sd8MQwTpVnMXdCRU0xZFlVRlk/view?usp=sharing上试用该算法。

Answer 1

首先，关于你的解决方案。

即使在最简单的输入中，也有一个bug破坏了它。当你决定距离变得太远，你应该在以前的某个时候实现，你不更新距离和加油站收费比它应该多。修复方法很简单：

if(d > c){ 
//car can not travel to this shop, has to decide which shop to refill
//in the previous possible shops
      result.push(tempMinIndex);
      lastFill = tempMinIndex;
      totalCost += price[tempMinIndex];
      tempMinIndex = i;
      // Fix: update distance
      var d = x[i] - x[lastFill];
    }

即使使用此修复，您的算法在某些输入数据上也会失败，如下所示：

0 10 20 30
0 20 30 50
30

它应该补充每一个汽油，以尽量减少成本，但它只是填补了最后一个。

经过一番研究，我想出了解决办法。我将尽量简单地解释它，使它独立于语言。

1. 想法

每一个加油站G，我们将计算最便宜的灌装方式。我们将递归地这样做:对于每个加油站，让我们找到所有的加油站，i，我们可以从那里到达G。对于每一个i计数，最便宜的灌装可能，并总结在G的填充成本，给出的汽油。开始加油站的成本是0。更正式地：

​

​

​

​

​

可以从输入数据中检索CostOfFilling(x)、Capacity和Position(x)。

所以，这个问题的答案就是简单的BestCost(LastGasStation)

1. 代码

现在，在javascript中使用解决方案来使事情更清晰。

function calculate(input)
{
    // Array for keeping calculated values of cheapest filling at each station
    best = [];
    var x = input.distance;
    var cost = input.cost;
    var capacity = input.travelDistance;

    // Array initialization
    best.push(0);
    for (var i = 0; i < x.length - 1; i++)
    {
        best.push(-1);
    }

    var answer = findBest(x, cost, capacity, x.length - 1);
    return answer;
}

// Implementation of BestCost function
var findBest = function(distances, costs, capacity, distanceIndex)
{
    // Return value if it's already have been calculated
    if (best[distanceIndex] != -1)
    {
        return best[distanceIndex];
    }
    // Find cheapest way to fill by iterating on every available gas station
    var minDistanceIndex = findMinDistance(capacity, distances, distanceIndex);
    var answer = findBest(distances, costs, capacity, minDistanceIndex) + 
        calculateCost(distances, costs, capacity, minDistanceIndex, distanceIndex);
    for (var i = minDistanceIndex + 1; i < distanceIndex; i++)
    {
        var newAnswer = findBest(distances, costs, capacity, i) + 
        calculateCost(distances, costs, capacity, i, distanceIndex);
        if (newAnswer < answer)
        {
            answer = newAnswer;
        }
    }
    // Save best result
    best[distanceIndex] = answer;
    return answer;
}

// Implementation of MinGasStation function
function findMinDistance(capacity, distances, distanceIndex)
{
    for (var i = 0; i < distances.length; i++)
    {
        if (distances[distanceIndex] - distances[i] <= capacity)
        {
            return i;
        }
    }
}

// Implementation of Cost function
function calculateCost(distances, costs, capacity, a, b)
{
    var distance = distances[b] - distances[a];
    return costs[b] * (distance / capacity);
}

完全可行的带有代码的html页面可用这里。