ゲーム「トリプルタウン」に触発された問題に最適なアルゴリズムを見つけようとしています。ゲームは次のようになります。
オブジェクトをグリッドに配置し、3 つのセットを作成するたびに、最後に配置されたオブジェクトの位置で、より高いレベルの 1 つのオブジェクトに凝縮します。
さらに、これらの b オブジェクトを 3 つ一緒に配置すると、それらは再び圧縮されて、さらに高いレベルのオブジェクトが形成されます。
注: これらの図では、オブジェクトのレベルは a i 、b i 、および c i として表され、下付き文字は3 つのセットのオブジェクト数を示します。
物事を単純化するために、配置する必要のあるすべてのオブジェクトが最も低いレベルにある場合のみを考慮しています。
今私の質問は次のとおりです。
1: x が与えられた場合に、レベル x のオブジェクトを作成するために必要なグリッド領域の最小量を決定するアルゴリズムはありますか?
たとえば、レベル a には 1x1、レベル b には 1x3、レベル c には 1x5 が必要です。
2: グリッドの次元が与えられた場合、達成可能なオブジェクトの最大レベルと数を見つけることができますか?
たとえば、2x2 の場合、2 つのレベル 'a' と 2 つのレベル 'b' を取得できます。
3: 固定グリッドが与えられた場合、オブジェクトの最適な順序と位置を見つけて、可能な限り最高のレベルを得るアルゴリズムはありますか?
たとえば、2x2 の場合、(1,1)、(1,2)、(2,2) を取得できます。
4: 意図したレベル x オブジェクトの位置が与えられた場合、このオブジェクトを作成するために必要なスペースの量を最小限に抑える一連の動きは?
5:これらのアルゴリズムの最適な複雑さは?
アップデート：
解決策の発見で際立っていると思うことの 1 つは、レベル x のアイテムを任意の場所で取得することはできないということです。
たとえば[ _ _ _ _ c]、固定の 1 x 5 グリッドでは、最後の b が 5 位に必要であり、したがって最後の a が 5 位にあるため、達成することは不可能です。したがって、最初の b:[a _ _ _ _]->[a a _ _ _]->[_ _ b _ _]または[_ a _ _ _]->[_ a a _ _]->[_ _ _ b _]. どちらの場合も、c の最後の b を作成するために 3 つの 'a' を配置する十分なスペースがありません。
もう 1 つのことは、何かを 1 次元のグリッドに展開できると想定することはできません。これは次のポイントで明らかになります。
私が見つけた興味深いもの：
レベル c のオブジェクトが 1 次元グリッド内に存在できる境界には、最小の近さがあります。[_ _ a a a]->[_ _ _ b]->[_ a a a b]->[_ _ _ b b]->[a a a b b]->[_ _ c _ _]. したがって、1 x 5 (最適) グリッドのレベル c オブジェクトは、3 番目の位置でのみ作成できます。
これは、任意の数のグリッドで 1 で作成できる最高レベルであるということになります。無限グリッドによる 1 を取得します。
..._ a a a _ ... -> ... _ a a a b _ ... -> ... _ a a a b b _ ... -> ... _ c _ ...
次に、そのすぐ隣に別の c を取得しようとします。
..._ c a a a _ ... = ... _ c b _ ... or ... _ c _ b _ ... or ... _ c _ _ b _ ...
唯一のオプションは..._ c b _ ...、c と b の間に別の b を形成することが他のものによって不可能になるためです。唯一のオプションは、最後の c がそこに行くのをブロックするため、最初の c のすぐ隣に c を作成する唯一の方法を防ぎます。したがって、1 つの次元では、c は作成できる最高レベルです。つまり、問題は 2 次元で検討する必要があります。