A、B、Cという3つの異なる色のブロックがある部屋があるとしましょう。
私の目標は、Loloに最も近い3つのブロックがA、B、Cがそれぞれ1つであることを発見することです。さらに、各ブロックとLolo自身が異なる行になければなりません：
たとえば、行1のブロックは使用できません.Loloはその行にあるためです。
Loloより上のAブロックを選択すると、Row 0の他のブロックは使用できません。
この例では、正解は次のブロックです。
最も近い3つのブロックを簡単に見つけることができますロロ;しかし、私は追加の制約（同じ行にない各文字の1つ）を適用するのは苦労しています。これは旅行セールスマン問題のバリエーションのように感じます。
これらのブロックを把握する効率的な方法は何ですか？ （正しい方向の一点でさえ大いに感謝されるでしょう！）ありがとう！
回答：
回答№1は1欲張りな解決策：
以下のブロックのすべてのピッキングは、行の制約に従うように実行する必要があります。
- まだ選択されていない最も近いブロックを選択します（これはAです）。
- 最も近い非Aブロックを選択します（これはBです）。
- 最も近い非A、非B（したがってC）ブロックを選択します。
- この距離を記録する。
- Bと同じ行にCが近い場合は、その次の最も近いBと一緒にCを選んで距離を記録します。
- 3色以上の場合は、別の行にある次の最も近いBを選びます。
- 最も近いunpickedブロックが
bestDistanceSoFar/3そうでなければ1から繰り返す。 - 最高の距離を返します。
これについては、各色のソートされたリストを持つことをお勧めします。
私はこれが最適だと信じていますが、それはなぜ考えられるのでしょうか。
前処理：
同じ行にあるすべてのブロックを削除することができますあなたが言及したようにロロだけでなく、同じ行の同じタイプの別のブロックよりもロロからのすべてのブロックがあります。
追加の注意：
あなたは3色しか持っていないと仮定すると、ブルートフォースの実行時間はO（n3）、これはO（n！）またはO（2n）をTSPの。
ブルートフォースに対する明白な最適化は、すべての色を分離することであり、結果として実行時間はO（n1n2n3）ここで、n私 i番目の色を持つブロックの量です。
回答№2の場合は1
あなたはDFSを使うべきだと思います
あなたは次の方法でGを構築します：
- ロロは根です
- 既に訪問している色を持たない利用可能なブロックを選択し、Gを追加する。重みはLoloからの距離である
- 同じ行にあるすべてのブロックを使用不可能にする
- 利用可能なブロックが2つ以上ある場合
- 使用可能なブロックがLoloに戻っていなければ、Loloの直接の息子ではないブロックを選択します
グラフを作成した後、深さ3のDFSを実行し、最もコストの低いパスを選択することができます。
これはあなたに最も低い距離を与えるでしょう。
他にも制約がありますか？どのくらい速く走る必要がありますか？