So finden Sie minimale Anzahl von Unterteilungen

Question

Stellen Sie sich vor Sie haben eine Leinwand und in dieser Leinwand gibt es bereits einige Objekte. Wie können Sie den minimalen Weg finden, den "unbedeckten" Bereich mit Quadraten zu bedecken, die sich nicht überlagern und die Leinwand vollständig ausfüllen.

In meinem Fall ist die "Leinwand" ein HTML-Div-Container und die Objekte sind verschachtelte Div-Container. könnte wie folgt aussehen: http://www.encodechain.com/demo/200908_optimize.png Auf der linken Seite des „Start“ es gibt und auf dem rechten Seite gibt es auf möglichen ersten „Schritt“ ...

Ich weiß, dass ein Algorithmus dafür da ist, aber zur Zeit kann ich mich nicht erinnern, der Name.

Answer 1

Das Beste, was ich war dieses Papier finden konnte: Tiling a rectangle with the fewest squares. Das Papier ist eine interessante Lektüre, obwohl es manchmal tief in das Gebiet der Theorie eindringt mit der Rede von "universellen Konstanten". Ich bin mir nicht sicher, ob die Frage "Kann ein Rechteck der Größe m mal n mit k Quadraten belegt werden" NP-vollständig ist. Wie in einer anderen Antwort erwähnt, ähnelt Ihre Frage Packproblemen, die NP-vollständig sind. Und natürlich ist Ihr Problem eine Verallgemeinerung des hier behandelten, da es sich um nicht rechteckige Bereiche handelt. Sie könnten damit beginnen, Ihren Bereich in die Mindestanzahl von Rechtecken aufzuteilen, ein weiteres interessantes Problem für sich. Und schließlich, selbst wenn Sie das effizient machen könnten, bin ich mir nicht sicher, ob diese Rechtecke optimal gedeckt werden würden, was zu einer insgesamt optimalen Kachelung führen würde.

Wie der Autor bemerkt, ist ein Greedy-Algorithmus ein guter Anfang: Legen Sie einfach das größte Quadrat ab, das Sie können, bis der Bereich voll ist.

Answer 2

Packing Problem

Knapsack Problem

Und ein article auf die Lösung 2d Packungsproblem