課題：48x48の画像を取り、最も安価なレゴソリューションをもたらす隣接する領域を見つけて、その画像を作成してください！ [閉まっている
https://stackoverflow.com/questions/5307253
-
24-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
バックグラウンド
レゴが生成します X-Large Greyベースプレート, 、幅48のスタッド、高さ48個のスタッドの大きなビルディングで、総面積は2304個のスタッドです。レゴの狂信者である私は、これらのベースプレートに置くことができるモザイクスタイルのデザインをいくつかモデル化し、おそらく壁やディスプレイに掛けることができます（参照： アンドロイド, ドリームシアター, 銀河帝国, ポケットモンスター).
チャレンジ
私の課題は、これらのデザインを購入するために最低のコストを獲得することです。 2304個の個別の1x1プレートを購入すると、高価になります。使用 bricklink, 、本質的にはレゴのeBayです。私は、与えられた色の最も安い部分が何であるかを判断するためのデータを見つけることができます。たとえば、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コーナーピース. 。答えは必ずしも色を考慮に入れる必要はありませんが、そのシナリオをカバーするために拡張可能である必要があります。シナリオでは、すべてのプレートがすべての色で利用できるわけではないため、プレート、その色、およびそのプレートの平均コストを識別する要素の配列があると想像してください（例は以下です）。賞金を提供してくれたベンジャミンに感謝します！
1x1|white|.07
1x1|yellow|.04
[...]
1x2|white|.05
1x2|yellow|.04
[...]
このリストにはエントリがありません。
8x8|yellow|imaginarydollaramount
これは、8x8黄色のプレートが存在しないためです。リスト自体は些細なものであり、ソリューションの参照を提供するものとのみ考えるべきです。ソリューション自体に影響を与えません。
編集2
明確にするためにいくつかの文言を変更しました。
解決
カールのアプローチは基本的に健全ですが、さらに詳細を使用できます。最適なコストソリューションが見つかりますが、特定の入力には遅すぎます。特に大きなオープンエリアは、素朴に検索するにはあまりにも多くの可能性があります。
とにかく、私はここで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
}
サブエリアを埋める最も安い方法を見つけたら、結果をキャッシュします。サブエリアを非常に効率的に識別するために、64ビット整数を使用して使用します ゾブリスト ハッシュ。警告：ハッシュ衝突により、誤った結果が生じる可能性があります。ルーチンが戻ったら、キャッシュされた値に基づいて最適なソリューションを再構築できます。
最適化：この例では、41936ノード（再帰呼び出し）が検討されています（空の正方形の上部から底を検索）。ただし、左から右の空の正方形を検索すると、約900,000のノードが調査されています。
大きなオープンエリアの場合： 最も費用効率の高い作品を見つけて、その作品を前処理ステップとして多くのオープンエリアに記入することをお勧めします。別の手法は、画像をいくつかの地域に分割し、各領域を個別に最適化することです。
幸運を！私は3月26日まで利用できないので、うまくいけば何も見逃しませんでした！
他のヒント
ステップ
ステップ1：すべてのソリューションを反復します。
ステップ2：最も安いソリューションを見つけます。
ピースインベントリを作成します
可能なピースの配列（各色の単一のピースを含む）の場合、n = max（各色のボード＃/ピース＃）で、各ピースの少なくともnの複製を作成します。したがって、そのピースのせいぜいNは、ボード全体の色のすべてをエリアごとにカバーできます。
現在、このコレクションのサブセットがボードを完全に満たすことが保証されているため、境界を掲載した可能性のある作品の膨大なコレクションがあります。
次に、Subsetの問題になります。これは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 = color数）があります。
したがって、このアルゴリズムがいつでも完了するためには、検索ツリーの99％を最初の数百枚から剪定する必要があります。たとえば、これまでに見つかった最低コストのソリューションの集計を維持し、現在のコストプラス（空のボード位置x各色の平均コストが最も低い）>現在の最低コストソリューションの場合、すべての低いプライとバックトラックの検索を停止するだけです。
たとえば、ベースラインの最低コストソリューションをできるだけ早く削減し、できるだけ多くの将来のケースを剪定するために、常に最大のピース（または最も低い平均コストのピース）を常に支持することにより、さらに最適化します。
最も安いものを見つける
各ソリューションのコストを計算し、最も安いものを見つけてください！
コメント
このアルゴリズムは一般的です。ピースが同じ色であるとは想定していません（マルチカラーのピースを持つことができます！）。大きなピースが小さなピースの合計よりも安いとは想定していません。それは実際には何も想定していません。
いくつかの仮定を行うことができる場合、この情報を使用して、できるだけ早く検索ツリーをさらに剪定することができます。たとえば、単一色のピースのみを使用する場合、ボードの大きなセクション（間違った色で）を剪定し、セット（間違った色の）で多数のピースを剪定できます。
提案
一度に48x48を実行しようとしないでください。たとえば、8x8の小さなもので、かなり小さなセットのピースを試してみてください。次に、ピースとボードサイズの数を徐々に増やします。プログラムがどれくらい時間がかかるかは本当にわかりませんが、誰かが私に言ってくれるのが大好きです！
最初に、洪水詰めを使用して問題を分割して、レゴレンガの連続領域を埋めます。次に、それらのそれぞれについて、あなたが望むメモを備えたDFSを使用できます。洪水の詰め物は些細なものなので、私はそれをそれ以上説明しません。
検索ツリーを拡張して、状態を繰り返さないように右手ルールに従ってください。
私の解決策は次のとおりです。
- スタッドコストですべてのピースを並べ替えます。
- ソートされたリストの各ピースについては、プレートにできるだけ多くを配置してみてください。
- デザインの2D画像をラスターして、均一な色の画像の領域、現在のピースの形状、および各スタッドが使用する各スタッドのフリースタッドを探しています。
- その特定の部分に見つかった領域の色が存在しない場合は、継続的な検索を無視してください。
- 色が存在する場合：そのピースで使用されているスタッドにタグを付け、その種のピースとその色のカウンターを増やします。
- ステップ2は、正方形のピースに対して1回、長方形のピース（垂直、1回は水平）で2回、コーナーピースの場合は4回行われます。
- プレートがいっぱいになるか、それ以上の種類のピースが利用できないまで2を反復します。
最後に到着すると、各種類のピースの数と、最低コストで必要な各色が得られます。
スタブによるコストが色によって変更される可能性がある場合、元のソートされたリストには、色によってピースの種類だけではありません。
