Optimaler Triple-Town-Algorithmus

Um Dinge zu vereinfachen, überlege ich nur, wann jedes Objekt, das Sie platzieren müssen, auf der niedrigsten Ebene ist.

Jetzt sind meine Fragen:

1: Gibt es einen Algorithmus, um die kleinste Menge an Gitterfläche zu bestimmen, die benötigt wird, um ein Objekt der Ebene x mit x zu erstellen?

Zum Beispiel benötigen Sie für Stufe a 1x1, für Stufe b 1x3, für Stufe c 1x5.

2: Können wir anhand der Dimensionen eines Gitters die höchste erreichbare Anzahl und die höchste erreichbare Anzahl an Objekten finden?

Zum Beispiel können Sie für ein 2x2 zwei Level 'a's und zwei Level' b's bekommen

3: Gibt es einen Algorithmus, um die optimale Reihenfolge und Position von Objekten zu finden, um bei einem festen Gitter das höchstmögliche Niveau zu erreichen?

Beispielsweise können Sie für ein 2x2 (1,1), (1,2), (2,2)

4: Wenn eine Position eines beabsichtigten x-Objekts der Ebene gegeben ist, welcher Satz von Bewegungen minimiert den Platz, der benötigt wird, um dieses Objekt zu erstellen?

5: Was sind die optimalen Komplexitäten dieser Algorithmen?

Aktualisierung:

Eine Sache, die bei der Suche nach Lösungen wichtig ist, ist, dass das Abrufen eines Elements der Ebene x nicht an einem beliebigen Ort erfolgen kann .

Zum Beispiel: [ _ _ _ _ c] ist unmöglich in einem festen 1 zu 5 Raster zu erreichen, weil du dein letztes b auf dem 5. Platz brauchst und somit dein letztes a auf dem 5. Platz. Um also das erste b zu platzieren: [a _ _ _ _]->[a a _ _ _]->[_ _ b _ _] oder [_ a _ _ _]->[_ a a _ _]->[_ _ _ b _] . In beiden Fällen ist nicht genug Platz, um 3 'a' zu setzen, um das letzte b des c zu machen.

Eine andere Sache, können wir nicht davon ausgehen, dass alles zu einem 1-dimensionalen Gitter abgerollt werden kann . Das wird mit meinem nächsten Punkt klar.

Etwas Interessantes, das ich gefunden habe:

Es gibt eine minimale Nähe zur Grenze, die ein Level-c-Objekt in einem 1-dimensionalen Gitter haben kann. %Code%. So kann ein Level-c-Objekt in einem Raster von 1 mal 5 (optimal) nur an der 3. Position erstellt werden.

Daraus folgt, dass dies die höchste Stufe ist, die von einem beliebigen Zahlengitter in 1 gemacht werden kann. Nimm ein Gitter von 1 nach unendlich:

[_ _ a a a]->[_ _ _ b]->[_ a a a b]->[_ _ _ b b]->[a a a b b]->[_ _ c _ _]

Jetzt versuchen wir ein anderes c direkt daneben zu bekommen:

..._ a a a _ ... -> ... _ a a a b _ ... -> ... _ a a a b b _ ... -> ... _ c _ ...

Die einzige Option ist ..._ c a a a _ ... = ... _ c b _ ... or ... _ c _ b _ ... or ... _ c _ _ b _ ... , weil die anderen es unmöglich machen, ein weiteres b zwischen c und b zu bilden. Unsere einzige Option verhindert unsere einzige Möglichkeit, c direkt neben unserem ersten c zu erstellen, da es das letzte c davon abhält, dorthin zu gehen. Daher ist c in einer Dimension die höchste Ebene, die wir herstellen können. Mit anderen Worten, muss das Problem in zwei Dimensionen betrachtet werden .