4

最大效率问题

有N个城市，有一个流浪者。

他从一个城镇到另一个城镇所花费的时间是已知的 - Txy（从城镇 x 到城镇 y）。

他可以从任何城镇去任何其他城镇，所以这是一个完整的图表。

在每个城镇都有流浪者想要收集的一定数量的货币 Mx。

穿越所有城市的时间不够。

有了总可用时间 T 和起点 i，问题是找到最好的路线，以便他收集的钱将是最大的。

输入数字范围：

  • N 介于 400 和 600 之间
  • Mx(M1, M2, ...) 介于 100 和 500 之间，x 介于 1 和 N 之间
  • Txy 介于 80 和 200 之间，x 和 y 介于 1 和 N 之间
  • Txy 是最佳时间距离，使得 Txy < Txz + Tzy，对于介于 1 和 N 之间的任何 x、y 和 z。
  • T 介于 3500 和 5000 之间
4

4 回答 4

2

似乎是动态的：

表示a[ x ] - 从城市 x 收取的钱。

令dp[ x ][ t ]表示他在城市x花费时间t并完成工作所能收集的最大金钱数量。初始化和更新如下：

  1. 对于起点x0，dp[ x0 ][ 0 ] := a[ x0 ]。对于其他城市 x dp[ x ][ 0 ] := -1 (无效);
  2. 对于从1到T的每个时间t：对于每个城市x：对于每个城市y st edge[ y ][ x ] <= t：表示p := t - edge[ y ][ x ]；if dp[ y ][ p ] >= 0 // 有可能在时间 p 到达 y then dp[ x ][ t ] = max( dp[ x ][ t ], dp[ y ][ t - edge[ x ][ y ]] + a[ x ])





  3. 返回所有 dp[ x ][ t ] 的最大值。

总复杂度为O( T*N^2 )。

于 2013-02-05T14:37:59.503 回答
1

我正在考虑基于回溯的解决方案。您应该定义一种算法来找到最佳解决方案（获得更多资金的解决方案）。当您旅行到所有城市或超过您拥有的时间时，您就结束了算法。忽略不赚钱的候选人：您必须根据仍待访问的最少城市数量来测试赚取的钱是否至少是当前的最佳解决方案；并检查从一个城市到所有剩余城市所需的最短时间。

要知道您将赚取的最低金额，您必须乘以每个城市中的最低金额仍需访问的城市数量。

这同样适用于您访问所有剩余城市所需的最短时间。

编辑：我忘了告诉你这个算法的成本是 O(a^n)，其中a是图的 arist 数（即 N*(N-1)），n是顶点数（即是 N)。如果您定义好的函数以了解您的实际候选人何时无法成为解决方案以及何时不能比当前的最佳解决方案更好（如果您幸运地在开始时找到解决方案），成本会更好迭代过程，这确实有助于减少操作时间）。

于 2013-02-05T14:54:41.567 回答
0

每个城镇的金额是未知的，所以最好的路线是从一个城镇到下一个城镇的最短路线。

如果我要使用递归在 Javascript 中对此进行编程，我会这样做：

http://jsfiddle.net/rd13/ShL9X/5/

c = ['london', 'manchester', 'liverpool']; //Cities

t = {
    'liverpool': {
        'manchester': 130,
        'london': 260
    },
    'london': {
        'manchester': 250,
        'liverpool': 260
    },
    'manchester': {
        'london': 250,
        'liverpool': 130
    }
} //Time between cities

cn = 'london'; //Current city

var shortestDistance = 500,
    allottedTime = 300,
    next_city,
    time = 0,
    totalTime = 0,
    path = [cn];

optimal = function (cn) {

    for (i in t[cn]) {
        //So as not to visit cities that we have already visited
        if(path.indexOf(i)===-1) {
            next_city = t[cn][i] < shortestDistance ? i : next_city;
            shortestDistance = t[cn][i];
            totalTime = Math.min(t[cn][i] , shortestDistance);
        }
    }
    time += totalTime;

    path.push(next_city);

    if(time > allottedTime){
        document.write("The most optimal route between cities is: " + path);
    } else {
        optimal(next_city);
    }

}

optimal(cn);

抱歉，对算法没有帮助，这是从编程的角度来看的，因为我认为这是一个有趣的挑战。以上不是最佳思想。

于 2013-02-05T15:09:08.713 回答
-1

这是一个众所周知的问题的变体，通常称为旅行商问题。您可以在此处找到有关此问题和类似问题的详细描述以及维基百科上的更多链接： http ://en.wikipedia.org/wiki/Travelling_salesman_problem

于 2013-02-05T14:42:28.017 回答