Container-Pack-Algorithmus

[Evolver]

Ich benötige für mein Programm einen Algorithmus, um Rechtecke (Pakete) in einem größeren Rechteck (Container) anzuordnen. Ich hatte auch einen Algorithmus gefunden, der ganz nett funktioniert hat und den ich deswegen in mein Programm eingebaut habe. Leider ist er jetzt in der Praxis gähnend langsam. Die problematische Stelle habe ich schnell gefunden, und nun suche ich nach einer Lösungsmöglichkeit.

Es gibt eine Container-Klasse, die zum Anordnen der Pakete verwendet wird und zum Prüfen, ob eine Anordnung zulässig ist. Hauptbestandteil ist ein 2dimensionales boolean-Feld, das den Container repräsentiert und für jedes "Pixel" angibt, ob es belegt ist oder nicht. Ein Paket im Container wird dargestellt, in dem die Postionen im boolean-Feld, die dem Paketrand entsprechen, auf true gesetzt werden.
Für den Algorithmus gibt es zwei Funtionen, die ein Paket soweit wie möglich nach links bzw. unten schieben, also solange, bis der Containerrand erreicht ist oder ein anderes Paket im Weg ist. Und diese beiden Funktionen sind der Performance-Killer, denke ich.

class Container
{
	private boolean mStack[][];			
	// ...
	
	public Container(int pStackWidth, int pStackHeight)
	{
		// ...
		mStack = new boolean[pStackWidth][pStackHeight];
		for(int i=0; i<pStackWidth; ++i)
			for(int j=0; j<pStackHeight; ++j)
				mStack[i][j] = false;
		// ...
	}

	// ...
	
	public void moveLeft(Chromosome pChr) 
	{
		if(pChr.getTopY()>=mStackHeight) return;
		boolean tMoveLeft = true;
		while(tMoveLeft && (pChr.mPosition.x>0)) {
			for(int j=pChr.mPosition.y; j<=pChr.getTopY(); ++j)
				if(mStack[pChr.mPosition.x-1][j]) {		// Schieben nach links nicht mehr möglich ...
					tMoveLeft = false;				// ... (dort liegt bereits ein anderes Paket)
					break;
				}
			if(tMoveLeft)	// Verschiebe um eine Position nach links
				pChr.setPosition(pChr.mPosition.x - 1, pChr.mPosition.y);
		}
	}
	
	
	public void moveDown(Chromosome pChr)
	{
		if(pChr.getRightX()>=mStackWidth) return;
		boolean tMoveDown = true;
		while(tMoveDown && (pChr.mPosition.y>0)) {
			for(int i=pChr.mPosition.x; i<=pChr.getRightX(); ++i)
				if(mStack[i][pChr.mPosition.y-1]) {	// Schieben nach unten nicht mehr möglich
					tMoveDown = false; 
					break;
				}
			if(tMoveDown) // Verschiebe um eine Position nach unten; Links-Überprüfung aktivieren;
				pChr.setPosition(pChr.mPosition.x, pChr.mPosition.y - 1);
		}
	}
}

Wie könnte ich nun das Verschieben beschleunigen? Eine erste Idee war, nicht jedes Pixel der jeweiligen Kante zu Prüfen, da die Pakete eine gewissen Mindestgröße haben. Aber welche weitern Ansätze gibt es?

 

[Evolver]

Hier ist noch der Link zu einer Beispielimplementierung, nach der ich meine umgesetzt habe.
Genetischer Algorithmus für Packproblem
Unten auf der Seite finden sich die Quellcodes.

Mein erster Ansatz, beim verschieben einige Schritte zu überspringen, hat leider nicht wirklich viel gebracht. Aber im Moment bin ich dennoch der Meinung, dass die Container-Klasse der Flaschenhals ist.

 

[Evolver]

Also heute Mittag kam mir die Idee, den Container komplett umzubauen: Einfach eine Liste von Paketen (Rechtecken) machen und die Funktionen dann alle mittels einfacher Kollisionserkennung. Für meine auftretenden Verhältnisse von Paetgrößen und Paketanzahl dürfte das wesentlich schneller sein. Aber falls jemand Lust hat, kann er sich ja mal die Klasse Genotyp und den Algorithmus selbst anschauen, da kann man vielleicht auch noch einiges rausholen. Aber wie, das weiß ich eben nicht.

 

[Evolver]

Auch wenn ich in diesem Thread absoluter Alleinunterhalter bin, bringe ich trotzdem noch den Abschluss: Also der Umbau mit der Liste der Pakete und der einfachen Kollisionserkennung für Rechtecke hat den gewünschten Effekt gebracht und ich bin mit der Geschwindigkeit jetzt zufrieden.

 

[Marco13]

Zumindest einen Mitleser hast du :wink:
So ein Problem (das doch etwas komplizierter ist, als die vielen RTFM-Fragen, die hier gestellt werden) ist zwar ineteressant, aber die Zeit, sich dort so weit einzuarbeiten, dass man die "kritische Stelle" findet, und die dann auch noch verbessern kann (so dass es nachher noch genauso funktioniert wie vorher, und/oder(!) das macht, was es machen soll, findet eben nicht jeder 🙁