2

A、B、C とラベル付けされた 3 つの異なる色のブロックがある部屋があるとします。 写真1

私の目標は、ロロに最も近い 3 つのブロックを見つけて、1 つの A、1 つの B、1 つの C を見つけることです。さらに、各ブロックとロロ自身は異なる行にある必要があります。 写真2

たとえば、Lolo が行 1 にあるため、行 1 のブロックは使用できません。 写真3

Lolo の上の A ブロックを選択すると、Row 0 の他のブロックは使用できません。 写真4

この例では、正解は次のブロックです。 写真5

ロロに最も近い 3 つのブロックを簡単に見つけることができます。ただし、追加の制約 (同じ行ではなく、各文字の 1 つ) を適用するのに苦労しています。これは、巡回セールスマン問題のバリエーションのように感じます。

これらのブロックを理解する効率的な方法は何ですか? （正しい方向へのポイントでも大歓迎です！）ありがとう！

4

2 に答える 2

1

貪欲な解決策:

以下のブロックの選択はすべて、行の制約に従うように行う必要があります。

  1. まだ選択されていない最も近いブロックを選択します (これが A であるとします)。
  2. 最も近い非 A ブロックを選択します (これが B であるとします)。
  3. 最も近い非 A、非 B (したがって C) ブロックを選択します。
  4. この距離を記録します。
  5. B と同じ行に近い C があった場合は、その C と次に近い B を選び、距離を記録します。
    • 3 つ以上の色の場合は、別の行で次に近い B を選択するだけです。
  6. 最も近い選択されていないブロックが よりも遠い場合は停止しbestDistanceSoFar/3、そうでない場合は 1 から繰り返します。
  7. 最適な距離を返します。

このために、色ごとにソートされたリストを用意することをお勧めします。

これが最適だと思いますが、なぜそれが最適なのかを考える必要があります。

前処理:

前述のように、Lolo と同じ行にあるすべてのブロックを削除できますが、同じ行にある同じタイプの別のブロックよりも Lolo から離れたすべてのブロックも削除できます。この場合はそれほど多くはありませんが、それでも削除できます。

ピック

追記:

3 色しかない場合、ブルート フォースの実行時間は O(n 3 ) になります。これは、TSPの O(n!) または O(2 n )よりもかなり短くなります。

ブルート フォースに対する明らかな最適化は、すべての色を分離することです。これにより、実行時間が O(n 1 n 2 n 3 ) になります。ここで、n iは i 番目の色のブロックの量です。

于 2013-06-02T10:30:32.597 に答える
1

DFSを使うべきだと思います

次の方法で G を作成します。

  1. 根本はロロ
  2. すでに訪れた色のない利用可能なブロックを選択し、ロロからの距離を重みで G に追加します
  3. 同じ行のすべてのブロックを使用不可にする
  4. 利用可能なブロックが他にある場合は 2 へ
  5. 利用可能なブロックがない場合は、ロロに戻り、ロロの直系の息子ではないブロックを選択します

グラフを作成したら、深さ 3 で DFS を実行し、最低コストのパスを選択できます。

これにより、最短距離が得られます。

他の制約はありますか? どのくらいの速度で実行する必要がありますか?

于 2013-06-02T10:27:50.750 に答える