5

ここに私が遭遇した興味深い質問があります：

M長さ の数直線上で、 ( ) 個の点の整数ペアを0 < M <= 1,000,000,000指定したとしましょう。各ペアで、最初のポイントはオブジェクトが現在配置されている場所を表し、2 番目のポイントはオブジェクトを移動する必要がある場所を表します。(ポイントはよりも小さい場合があることに注意してください)。N1 < N <= 100,000secondfirst

ここで、その地点から始めて、オブジェクト0を保持できるカートを持っていると仮定し1ます。すべてのオブジェクトを最初の位置からそれぞれの最終位置に、数直線に沿って最小距離 (変位ではなく) 移動させたいと考えています。ポイントに到達する必要がありますM。

今、私はこの問題をより単純な問題に還元しようとしています。正直なところ、ブルートフォース（おそらく貪欲な）ソリューションは考えられません。しかし、私が最初に考えたのは、後方への動きを 2 つの前方への動きに退化させることでしたが、それはすべての場合にうまくいくとは限りません。

これらの3サンプル テスト ケースをここに画像の説明を入力

最初のテストケースの答えは12です。まず、redポイントでアイテムを受け取ります0。次に、ポイント6(距離 = 6) に移動し、アイテムを一時的にドロップしてから、redアイテムを拾いgreenます。次に、ポイント5(距離 = 1) に移動し、アイテムをドロップしgreenます。次に、ポイント6(距離 = ) に戻り、ドロップしたアイテムを1拾い上げ、ポイント 9 (距離 = ) に移動し、ポイント(距離 = ) に移動してシーケンスを終了します。red3101

総移動距離は でした6 + 1 + 1 + 3 + 1 = 12。これは可能な最小距離です。

他の 2 つのケースは の答えがある12と思います。しかし、それを解決するための一般的なルールが見つかりません。

誰でもアイデアはありますか？

4

3 に答える 3

0

問題を誤解しているかもしれませんが、次のことはどうでしょうか。

  1. 現在の場所であるペアの最初の番号でペアを並べ替えます
  2. 要素を適切な場所にスワップする行に沿って移動します（一時変数があります）

並べ替えられているという事実により、要素を適切な場所に配置するために要素を行ったり来たりしないことが保証されます (行が配列またはリストとして表されているかどうかに関係なく)。

@templatetypedef コメントの後の更新:
a を使用しHashTableてすべてのペアを保存します。各ペアの現在の場所をインデックス キーとして使用します。
ペアに対して 2 番目のインデックスを使用します。 

 1. Get next pair according to index from the line.
 2. If current pair exists in hashtable then place element to its target location.  
    2.a Remove pair from hashtable.  
    2.b Make current pair the target location. Then go to step 1  
 ELSE 
        Increment current index until you get a pair present in the hashtable. Go to step 2
于 2013-02-09T20:55:05.330 に答える
0

これが非対称巡回セールスマン問題です。これはグラフと考えることができます。エッジは、各 (開始、終了) のペア、各 (0、開始) のペア、および (終了、開始) の他のすべてのペアになります。

NP!=P と仮定すると、予想される実行時間は指数関数的になります。

于 2013-02-09T21:36:29.187 に答える
0

これらの動きが与えられた場合、移動する必要が(a, b), (c, d), (e, f), ...ある最小距離はabs(b - a) + abs(d - c) + abs(f - e) + ...であり、実際に移動する距離は ですabs(b - a) + abs(c - b) + abs(d - c) + abs(e - d) + ...。
基本的に、移動の配列が与えられた場合、ポイントは、要素を交換することによって「移動距離」関数を最小限に抑えることです。特定の組み合わせをノードと見なし、そこから到達できるすべての組み合わせをエッジと見なす場合、ヒューリスティックを利用する多くのグラフ検索アルゴリズムのいずれかを使用できます。その一例がビームサーチです。

于 2013-02-09T21:05:16.867 に答える