从一个城市到另一个城市的最低成本

Question

假设数轴上有n个城市:1,2，…，n。定义一个函数c(i,j)，它返回从城市i到城市j的成本，并假设它需要常数时间来计算。我们想通过一组中间城市从1移动到n，但只向前移动。我们可以通过定义下面的递归式来计算这样做的最小代价:f(j)=min{1≤i

我认为这是旅行推销员问题的一个简单版本，但我觉得TSP的算法可能对这个问题太难了…有人能给点建议吗?

Answer 1

我们可以使用'动态规划'(基本上是记忆递归)来有效地解决这个问题。

//min_cost[i] denotes min cost to go from city i to city n
set all min_cost[i] to INF
int solve(int i){
    // base case
    if(i==n)
        return 0;
    // if we have already calculated the ans from city i just return it
    if(min_cost[i] != INF)
        return min_cost[i] ;
    else{
        ans = INF;
        for(int j=i+1;j<=n;j++)
            ans = min(ans, c(i,j) + solve(j));
        min_cost[i] = ans;
        return ans;
    }
}

时间复杂度O(n^2)

使用蛮力的方法是尝试从当前城市出发的所有可能的城市。它看起来像这样，

int solve(int i){
    if(i==n)
        return 0;
    ans = INF;      
    for(int j=i+1;j<=n;j++)
        ans = min(ans, c(i,j) + solve(j));
    return ans;
}

其中，如果你在城市i，你试着通过所有可能的路径找到最小路径，看看哪一条是最优的。

但是正如你所看到的，一个城市(比如j)的最小成本答案对它之前的所有城市(city i <j).因此，我们可以通过记忆解来使用动态规划优化解。>

如果您想在到达城市n后返回城市1，也可以轻松地修改代码。

Answer 2

这可以通过创建一个具有n顶点(作为城市)的图来解决，并且只在允许的方向上添加从城市i到j的有向边。

当我们完成创建图时，我们可以通过运行Dijkstra算法获得最小路径，其中源是节点1，目标是节点n。