最大效率

Question

最大效率问题

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

他从一个城镇到另一个城镇所需的时间是众所周知的-- Txy (从x镇到y镇)。

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

在每个城镇都有一笔钱，流浪者想要收集。

没有足够的时间通过所有的城市。

有了总可用时间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之间。

Answer 1

似乎是动态的：

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

让dp x 表示他能收集到的最大数量的钱，t和在城市x中完成的。初始化和更新如下：

1. 对于startpoint x0 ，dp x0 := a x0 。对于其他城市，x dp x := -1 (无效)；
2. 每次t从1到T为每个城市的x： 每个城市的y s.t。边y <= t表示p := t-边y ； 如果dp y >= 0 //可以在时间p中到达y 然后dp x= max( dp，dp y t边x]+a x )

1. 在所有dp上返回最大值。

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

Answer 2

我正在考虑一个基于回溯的解决方案。您应该定义一个算法来找到最优解(获得更多金钱的算法)。当您已经到达所有城市或超过了您的时间时，您将终止该算法。要忽略无利可图的候选人:你必须根据至少还在访问的城市数量来测试赚到的钱是否是目前的最佳解决方案；还要检查从一个城市到所有剩余的城市所需的最短时间。

要知道你能挣到的钱的最低数量，你必须把每一个城市里的最低数量的钱乘以仍然需要访问的城市的数量。

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

编辑:我忘了告诉您这个算法的代价是O(a^ N)，其中a是图(即N*(N-1))的变化数，n是顶点数(即N)。如果您定义了好的函数来知道实际的候选方案何时不能成为解决方案，以及当它不能比当前的最佳解决方案更好时，成本可能会更高(如果您幸运地在迭代过程的要求中找到了解决方案，这确实有助于减少操作时间)。

Answer 3

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

如果我使用递归在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);

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