performance - Maximum efficiency

Question

Maximum efficiency problem

The are N cities and there is a wanderer.

The time it takes for him to go from a town to another town is known - Txy (from town x to town y).

From any town he can go to any other town so it is a complete graph.

In each town there is a an amount of money Mx the wanderer wants to collect.

It isn't enough time to pass through all cities.

Having the total available time T and the starting point i, the problem is to find the best route so that the money he collects will be maximum.

Input numbers range:

N is between 400 and 600
Mx(M1, M2, ...) are between 100 and 500, x between 1 and N
Txy are between 80 and 200, x and y are between 1 and N
Txy is the optimal time distance so that Txy < Txz + Tzy, for any x, y and z between 1 and N.
T is between 3500 and 5000

score 2 · Accepted Answer

動的に見える：

a [ x ] - 都市 x から収集するお金を示します。

dp[ x ][ t ]を、時間tを費やし、都市xで終了するときに収集できる最大の金額を意味するものとします。初期化と更新は次のとおりです。

開始点x0の場合、dp [ x0 ][ 0 ] := a[ x0 ] . 他の都市の場合 x dp[ x ][ 0 ] := -1 (無効);
1からTまでの各時間t :各都市x :各都市yに対して_ _ _ _ if dp[ y ][ p ] >= 0 // 時間 p で y に到達できる場合dp[ x ][ t ] = max( dp[ x ][ t ], dp[ y ][ t - edge[ x ][ y ]] + a[ x ] )
すべての dp[ x ][ t ] の最大値を返します。

全体の複雑さはO( T*N^2 )です。

score 1 · Accepted Answer

バックトラッキングベースのソリューションを考えています。最適なソリューション (より多くのお金を得るソリューション) を見つけるアルゴリズムを定義する必要があります。すべての都市に移動したとき、または制限時間を超えたときに、アルゴリズムを終了します。採算の取れない候補を無視するには、訪問する都市の最小数に基づいて、少なくとも現在の最適解と同じかどうかをテストする必要があります。また、1 つの都市から残りのすべての都市に移動するのにかかる最小時間を確認します。

獲得できる最低金額を知るには、1 つの都市に存在する最低金額に対して、まだ訪問していない都市の数を掛ける必要があります。

同じことが、残りのすべての都市を訪れるのに必要な最小時間にも当てはまります。

編集: このアルゴリズムのコストは O(a^n) であると言い忘れていました。ここで、aはグラフのアリストの数 (つまり N*(N-1)) であり、nは頂点の数 (つまりN)です。適切な関数を定義して、実際の候補が解にならない場合と、現在の最適な解よりも良くならない場合を知ると、コストが高くなる可能性があります (幸運にも最初に解を見つけることができた場合)。反復プロセス、これは実際に操作時間を短縮するのに役立ちます)。

score 0 · Accepted Answer

各町の金額は不明なので、町から町への最短ルートが最適なルートです。

再帰を使用して 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);

アルゴリズムについては申し訳ありませんが、興味深い挑戦だと思ったので、これはプログラミングの観点からです。上記は最適な心ではありません。

score -1 · Accepted Answer

これは、巡回セールスマン問題として通常知られているよく知られた問題の変形です。この問題と同様の問題の詳細な説明、およびウィキペディアの詳細なリンクは、次の場所にあります：http: //en.wikipedia.org/wiki/Travelling_salesman_problem

performance - Maximum efficiency

4 に答える 4

Related

Reference