0

これはアルゴリズムの問​​題だと思いますが、C++ でもやりたいと思っています。例を挙げて質問を説明しましょう。

N 個のオブジェクト (プログラミング オブジェクトではない) があり、それぞれ重みが異なるとします。そして、私はそれらを運ぶために2台の車を持っています。車両は、すべてのオブジェクトを 1 つずつ運ぶのに十分な大きさです。これらの 2 つの車両には、独自の走行距離と、タンク内の異なるレベルの燃料があります。また、走行距離は、それが運ぶ重量によって異なります。

目的は、これらの N 個のオブジェクトを可能な限り遠ざけることです。そのため、N 個のオブジェクトを特定の方法で 2 台の車両に分配する必要があります。それらを「同じ」距離にする必要はありませんが、可能な限り遠ざけることに注意してください。たとえば、1 台が 2km でもう 1 台が 7km ではなく、2 台の車両が 5km と 6km を移動するようにします。

各車両にどの重量を搭載するかを決定するための理論的な閉じた形式の計算は考えられません。固定値である N 個のオブジェクトをすべて運ぶ必要があることを思い出してください。

考えられる限り、すべての組み合わせを試す必要があります。

すべての組み合わせを試すための効率的なアルゴリズムについて誰かがアドバイスできますか?

たとえば、次のようになります。

int weights[5] = {1,4,2,7,5}; // can be more values than 5
float vehicelONEMileage(int totalWeight);
float vehicleTWOMileage(int totalWeight);

weights[] と 2 つの関数のすべての組み合わせを効率的に試すにはどうすればよいでしょうか?

線形関数として 2 つの関数を仮定できます。つまり、2 つのマイレージ関数の戻り値は、(異なる) 負の勾配と (異なる) オフセットを持つ線形関数です。

だから私が見つける必要があるのは次のようなものです：

MAX(MIN(vehicleONEMileage(x), vehicleTWOMileage(sum(weights) - x)));

ありがとうございました。

4

2 に答える 2

1
  • これは cs または math サイトにあります。
  • 単純化: オブジェクトの配列の代わりに、重みを線形に分配できるとしましょう。

最適化したい関数は、両方の移動距離の最小値です。最小値の最大値を見つけることは、積の最大値を見つけることと同じです (証明なし。ただし、これを確認するには、長方形の周囲と面積の関係を考えてください。周囲が与えられた最大の面積を持つ長方形は正方形です。たまたま最大の最小辺の長さも持っています)。

以下では、すべての重みの合計を にスケーリングし1ます。したがって、 のような分布(0.7, 0.3)は、すべての重量の 70% が車両 1 に搭載されていることを意味します。車両 1 の負荷を車両 1 の負荷と呼びましょxう1-x。

2 つの線形関数f = a x + bおよびg = c x + dが与えられた場合f、 は車両 1 に重量 を積載したときの走行距離でありx、g車両 2 についても同様です。

(a*x+b)*(c*(1-x)+d)

Wolfram Alpha に難しい作業を依頼してみましょう: www.wolframalpha.com/input/?i=derive+%28%28a*x%2Bb%29*%28c*%281-x%29%2Bd%29%29

に極値があることを示しています。

x_opt = (a * c + a * d - b * c) / (2 * a * c)

問題を効率的に解決するために必要なのはそれだけです。

完全なアルゴリズム:

  • a、、、を見つけるb_cd

    b = vehicleONEMileage(0)

    a = (vehicleONEMileage(1) - b) * sum_of_all_weights

    cと についても同じd

  • 上記のように計算x_optします。

    • の場合x_opt < 0、車両 2 にすべての重量を載せます
    • の場合x_opt > 1、すべての重量を車両 1 に積載します
    • それ以外の場合は、tgt_load = x_opt*sum_of_all_weights車両 1 に積み込み、残りを車両 2 に積み込みます。

  • 残りはナップザックの問題です。http://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_Knapsack_Problemを参照してください。

    これを適用する方法は？そこで説明されている動的計画法のアルゴリズムを 2 回使用します。

    • までの負荷を最大化するためtgt_load
    • sum_of_all_weights - tgt_load( )までの負荷を最大化するため

  • 最初のものは、車両 1 に搭載されている場合、車両 1 で予想されるよりもわずかに少ない分布を示します。

  • 2 番目のものは、車両 2 に搭載された場合、車両 2 で予想されるよりもわずかに多い分布になります。
  • そのうちの 1 つが最適なソリューションです。それらを比較して、より良いものを使用してください。

C++ の部分はあなたに任せます。;-)

于 2013-09-04T09:03:42.397 に答える
1

次の解決策を提案できます。

組み合わせの総数は 2^(重みの数) です。ビット ロジックを使用して、すべての組み合わせをループし、maxDistance を計算できます。組み合わせ値のビットは、どの重量がどの車両に割り当てられるかを示します。

アルゴリズムの複雑さは指数関数的でintあり、ビット数が限られていることに注意してください!

float maxDistance = 0.f;

for (int combination = 0; combination < (1 << ARRAYSIZE(weights)); ++combination)
{
    int weightForVehicleONE = 0;
    int weightForVehicleTWO = 0;

    for (int i = 0; i < ARRAYSIZE(weights); ++i)
    {
        if (combination & (1 << i)) // bit is set to 1 and goes to vechicleTWO
        {
            weightForVehicleTWO += weights[i];
        }
        else // bit is set to 0 and goes to vechicleONE
        {
            weightForVehicleONE += weights[i];
        }
    }

    maxDistance = max(maxDistance, min(vehicelONEMileage(weightForVehicleONE), vehicleTWOMileage(weightForVehicleTWO)));
}
于 2013-09-04T06:52:13.333 に答える