4

例から直接始めましょう：

ゲームでは、プレイヤーがアイテムを保管するために使用するバッグがあり（アイテムのサイズは可変です）、バッグのサイズも可変です。

8x15スロットのバッグに、2x2スロットを占めるアイテムを挿入する必要があります。スペースを検索して、このアイテムを保管するのに十分なスペースがあるかどうかを実際に確認できます。これは簡単ですが、十分なスペースがない場合はどうなりますか。リクエストされたアイテムを保管するスペースはありますか？これが本当の問題です。

新しいアイテムのためのスペースを解放するために、現在のバッグ内の現在のすべてのアイテムを実際に再配置する方法を見つけようとしています。

それを行うのに役立つアルゴリズムはありますか？

編集

ルール：

  1. バッグの中の現在のアイテムを削除することはできません。十分なスペースがない場合は、新しいアイテムを保管するためにそれらを再配置するだけです。
4

1 に答える 1

1

残念ながら、これは NP 困難な問題だと思いますが、貪欲な近似アルゴリズムを使用できます。近似アルゴリズムは次のように機能します。

  • すべてのアイテムをアイテムのボリュームで降順に並べ替えます。
  • リスト全体を反復し、現在のアイテムをどこにでも配置しようとします
  • 現在のアイテムがどこにも収まらない場合は、そのアイテムをピックアップできないと判断します。
  • すべてのピースが取り付けられている場合は、アイテムをピックアップできると判断します。

これは、大きなピースは小さなピースよりも配置が「難しい」という直感的な考えに基づいています。ほとんどのアイテムが 1x1 である場合にできるもう 1 つのことは、ブルート フォース ソリューションです。これは、このような小さな在庫では非常に実現可能です。これは次のように機能します。

  • 現在のピースがまだ収まっているすべての位置と、そのようなすべての位置を試してください。
  • 次の配置されていないピースでこれを行います。

これは常に問題を解決しますが、かなり遅くなります (より正確ですが)。このアルゴリズムは、すべての 1x1 ピースを除外して後で配置することで改善できます。

于 2012-08-27T17:01:06.323 に答える