30

バックグラウンド

レゴはX-LargeGrayBaseplateを製造しています。これは、幅48スタッド、高さ48スタッドの大きなビルディングプレートで、総面積は2304スタッドになります。レゴマニアなので、これらのベースプレートに置いて、壁やディスプレイに掛けることができるモザイクスタイルのデザインをいくつかモデル化しました（Android、Dream Theater、The Galactic Empire、Pokemonを参照）。

チャレンジ

私の課題は、これらのデザインを購入するための最低コストを取得することです。2304個の1x1プレートを個別に購入すると、高額になる可能性があります。基本的にレゴのeBayであるBrickLinkを使用して、特定の色で最も安価な部品を特定するためのデータを見つけることができます。たとえば、0.10ドル（またはスタッドあたり0.025ドル）の1x4プレートは、2.16ドル（またはスタッドあたり0.06ドル）の6x6プレートよりも安価です。また、画像の組み立てに使用できるすべての可能なプレートのリストを決定することもできます。

1x1
1x2
1x3
1x4
1x6
1x8
1x10
1x12    
2x2 corner!    
2x2
2x3
2x4
2x6
2x8
2x10
2x12
2x16    
4x4 corner!    
4x4
4x6
4x8
4x10
4x12    
6x6
6x8
6x10
6x12
6x14
6x16
6x24    
8x8
8x11
8x16    
16x16

問題

この問題について、すべてのプレート、それらの色、および各プレートの「重量」またはコストのリストがあると仮定します。簡単にするために、コーナーピースを削除することもできますが、それは取り組むべき興味深い課題です。48x48イメージを作成するための最も安価なコンポーネントをどのように見つけますか？最も少ないコンポーネント（必ずしも最も安いとは限らない）を使用するソリューションをどのように見つけますか？コーナーピースを許容ピースとして追加する場合、どのように説明しますか？

BrickLinkにクエリを実行し、特定の色の特定のブリックの平均価格を取得し、それをリストの要素として追加することで取得されるマスターリストがあると想定できます。したがって、製造または販売されていないという理由だけで、黒い16x16プレートはありません。ただし、16x16ブライトグリーンプレートの値は3.74ドルで、現在利用可能な平均価格で計算されます。

私の問題の記述が十分に簡潔であることを願っています。それは私が数日間考えていたものであり、皆さんがどう思うかについて興味があります。面接で得たのではなく、やりがいがあるので「面接質問」とタグ付けしました（楽しい質問だと思いますが！）。

編集

これが2x2コーナーピースと4x4コーナーピースへのリンクです。答えは必ずしも色を考慮する必要はありませんが、そのシナリオをカバーするために拡張可能である必要があります。シナリオでは、すべてのプレートがすべての色で利用できるわけではないため、プレート、その色、およびそのプレートの平均コストを識別する要素の配列があると想像してください（例を以下に示します）。賞金を提供してくれたBenjaminに感謝します！

1x1|white|.07
1x1|yellow|.04
[...]
1x2|white|.05
1x2|yellow|.04
[...]

このリストにはエントリがありません：

8x8|yellow|imaginarydollaramount

これは、8x8の黄色いプレートが存在しないためです。リスト自体は些細なものであり、ソリューションの参照を提供するものとしてのみ考えるべきです。ソリューション自体には影響しません。

EDIT2

わかりやすくするために、いくつかの表現を変更しました。

4

4 に答える 4

7

カールのアプローチは基本的に健全ですが、もう少し詳細を使用することもできます。最適なコストソリューションが見つかりますが、特定の入力には遅すぎます。特に広いオープンエリアは、素朴に検索するにはあまりにも多くの可能性があります。

とにかく、私はここでC ++で簡単な実装を行いました：http： //pastebin.com/S6FpuBMc

これは、4種類のレンガで、空きスペース（ピリオド）を埋めることを解決します。

0: 1x1 cost = 1000
1: 1x2 cost = 150
2: 2x1 cost = 150
3: 1x3 cost = 250
4: 3x1 cost = 250
5: 3x3 cost = 1

..........       1112222221
...#####..       111#####11
..#....#..       11#2222#13
..####.#..       11####1#13
..#....#..       22#1221#13
..........       1221122555
..##..#...  -->  11##11#555
..#.#.#...       11#1#1#555
..#..##...       11#11##221
..........       1122112211
......#..#       122221#11#
...####.#.       555####1#0
...#..##..       555#22##22
...####...       555####444  total cost = 7352

したがって、アルゴリズムは特定の領域を埋めます。再帰的（DFS）：

FindBestCostToFillInRemainingArea()
{  
  - find next empty square
  - if no empty square, return 0
  - for each piece type available
    - if it's legal to place the piece with upper-left corner on the empty square
      - place the piece
      - total cost = cost to place this piece + FindBestCostToFillInRemainingArea()
      - remove the piece
  return the cheapest "total cost" found
}

サブエリアを埋める最も安価な方法がわかったら、結果をキャッシュします。サブエリアを非常に効率的に識別するために、 Zobristハッシュを使用して64ビット整数を使用します。警告：ハッシュの衝突により、誤った結果が生じる可能性があります。ルーチンが戻ったら、キャッシュされた値に基づいて最適なソリューションを再構築できます。

最適化： この例では、41936ノード（再帰呼び出し）が調査されます（空の正方形を上から下に検索します）。ただし、左から右に空の正方形を検索すると、約900,000ノードが探索されます。

大きなオープンエリアの場合：前処理ステップとして、最も費用効果の高いピースを見つけて、そのピースで多くのオープンエリアを埋めることをお勧めします。もう1つの手法は、画像をいくつかの領域に分割し、各領域を個別に最適化することです。

幸運を！3月26日までご利用いただけませんので、お見逃しなく！

于 2011-03-18T21:45:35.290 に答える
4

手順

ステップ1：すべてのソリューションを繰り返します。

ステップ2：最も安価なソリューションを見つけます。

ピースインベントリを作成する

可能なピースの配列（各色の単一のピースを含む）については、各ピースの少なくともn個の複製を作成します。ここで、n = max（各色のボード＃/ピース＃）です。したがって、その部分の最大n個が、領域ごとにボード全体の色をすべてカバーできます。

これで、このコレクションのサブセットがボードを完全に埋めることが保証されているため、可能なピースの膨大なコレクションができました。

次に、それはNP完全であるサブセット問題になります。

サブセット問題の解決

For each unused piece in the set
  For each possible rotation (e.g. for a square only 1, for a rectangle piece 2, for an elbow piece 4)
    For each possible position in the *remaining* open places on board matching the color and rotation of the piece
      - Put down the piece
      - Mark the piece as used from the set
      - Recursively decent on the board (with already some pieces filled)

最適化

明らかにO（2 ^ n）アルゴリズムであるため、検索ツリーを早期に枝刈りすることが最も重要です。長時間の実行を避けるために、最適化は早期に実行する必要があります。nは非常に大きな数です。48x48ボードを考えてみてください。単一のピースだけで48x48xc（c =色の数）があります。

したがって、このアルゴリズムをいつでも完了するには、検索ツリーの99％を最初の数百プライから削除する必要があります。たとえば、これまでに見つかった最低コストのソリューションの集計を維持し、現在のコストに加えて（空のボード位置の数x各色の最低平均コスト）>現在の最低コストのソリューションがあれば、すべての下位プライの検索を停止してバックトラックします。

たとえば、常に最大のピース（または最低の平均コストのピース）を最初に優先することでさらに最適化し、ベースラインの最低コストのソリューションをできるだけ早く削減し、将来のケースをできるだけ多く排除します。

最も安いものを見つける

各ソリューションのコストを計算し、最も安いものを見つけてください！

コメントコメント

このアルゴリズムは一般的です。ピースが同じ色であるとは想定していません（マルチカラーのピースを持つことができます！）。大きなピースが小さなピースの合計よりも安いとは想定していません。それは実際には何も想定していません。

いくつかの仮定を立てることができれば、この情報を使用して、検索ツリーをできるだけ早くさらに整理することができます。たとえば、単色のピースのみを使用する場合、ボードの大部分を（間違った色で）剪定し、セット内の多数のピース（間違った色）を剪定することができます。

提案

一度に48x48を実行しようとしないでください。適度に小さいピースのセットを使用して、たとえば8x8の小さなもので試してみてください。次に、ピースの数とボードのサイズを徐々に増やします。プログラムにどれくらいの時間がかかるかは本当にわかりませんが、誰かに教えてもらいたいです！

于 2011-03-22T13:22:21.703 に答える
2

まず、フラッドフィルを使用して、問題をレゴブロックの連続領域のフィルに分割します。次に、それらのそれぞれについて、必要なメモ化を含むdfsを使用できます。塗りつぶしは些細なことなので、これ以上説明しません。

状態を繰り返さないように検索ツリーを展開するときは、必ず右手の法則に従ってください。

于 2011-03-15T05:24:41.303 に答える
1

私の解決策は次のとおりです。

  1. スタッドコストですべてのピースを並べ替えます。
  2. ソートされたリストの各ピースについて、プレートにできるだけ多く配置してみてください。
    • デザインの2D画像をラスターして、均一な色、現在のピースの形状、およびピースが使用する各スタッドのフリースタッドを使用して画像の領域を探します。
    • 見つかった領域の色がその特定の部分に存在しない場合は、検索の続行を無視してください。
    • 色が存在する場合：そのピースで使用されているスタッドにタグを付け、その種類のピースとその色のカウンターをインクリメントします。
    • ステップ2は、正方形のピースに対して1回、長方形のピースに対して2回（垂直方向に1回、水平方向に1回）、コーナーピースに対して4回実行されます。
  3. プレートがいっぱいになるか、使用できるピースのタイプがなくなるまで、2まで繰り返します。

最後に到着すると、最小のコストで必要な各種類と各色のピースの数が得られます。

スタブごとのコストが色によって変わる可能性がある場合、元の並べ替えられたリストには、ピースのタイプだけでなく、色も含まれている必要があります。

于 2011-03-23T17:25:55.060 に答える