Algorithmus Optimierung

[oetzi]

Hallo zusammen,

ich plane gerade den Eigenbau einer Theke für meinen Keller. Keine Sorge, ich habe mich nicht im Forum vertan 🙂
Die Zeichnung für die Unterkonstruktion ist fertig und ich habe jetzt eine Liste mit jeweils der Anzahl von verschiedenen langen Kanthölzer die ich benötige.
Beispiel - Stückverteilung

Anzahl | cm
2 | 100
1 | 40
2 | 25

Jetzt geht es darum die verschiedenen Stücke optimal auf die verfügbare Kantholzlänge die ich im Baumarkt kriege zu verteilen. Das könnte man natürlich jetzt auf die Schnelle grob auf Papier machen, aber mich hat gerade die Programmierwut ergriffen und ich möchte das per Algorithmus erledigen.

Mein Ansatz ist dabei folgender:
Zunächst muss ich alle möglichen Kombinationen bei einer möglichen gegebenen Kantholzlänge durchspielen.
Beispiel

Annahme: 
Kantholzlänge = 250 cm
Stückverteilung siehe oben

Mögliche Kombinationen:
1) 100 + 100 + 40 >> 10 cm Verschnitt + 2 x 25 cm für Kantholz 2
2) 100 + 100 + 25 + 25 >> Kein Verschnitt + 40 cm für Kantholz 2
3) 100 + 100 + 25 + 25 >> siehe 2) 
4) 100 + 40 + 100 >> siehe 1)
5) 100 + 40 + 25 + 25 >> 60 cm Verschnitt + 100 cm für Kantholz 2
usw.

Wenn ich also alle Möglichkeiten durchgegangen wäre, hätte ich in jeder Zeile die Angaben "Verschnitt" und "Rest für weitere Kanthölzer".
Ziel ist ja den Gesamtverschnitt zu minimieren.
Und hier hänge ich gerade gedanklich.

Der Ansatz den ich hier habe wäre, dass ich mir die erste Kombination wähle, die den minimalsten Verschnitt hat und dann mit den restlichen Stücken das gleiche Spiel von vorne beginne.
Das Vorgehen ist mir aber noch irgendwie zu zufällig. Vielleicht wähle ich dann als erstes eine Kombination, durch die ich Stücke wegnehme, die später in einer anderen Kombination den Verschnitt weiter verringern würden.

Puh, war das jetzt verständlich genug ausgedrückt? 🙂

Ich hätte also die Bitte an die Freunde des gepflegten Algorithmus ihre Ideen hier einzubringen.

Schönen Gruß
oetzi

 

[Kaibear]

Ayayay, da hast du dir eine (zugegeben sehr interessante) Aufgabe gestellt.

Ich hab ein wenig recherchiert und das Eindimensionale Zuschnittproblem ist anscheinend mal ne heiße Sache gewesen, wo sich ne Menge kluger Köpfe drangesetzt hat.

Ich hoffe der folgende Link hilft dir bei dem Problem weiter, ich hab noch nicht zuende gelesen.

Eindimensionales Zuschnittproblem ? Wikipedia

 

[kay73]

Ich kann nur eine naive Implementierung anbieten:

Für den Fall, dass im Baumarkt alle Kanthölzer dieselbe Länge haben:

- Bilde alle Permutationen der Menge der Schnitte, die nacheinander ausgeführt werden können. Für Deine Holzstückliste könnte diese so anfangen:
100, 100, 40, 25, 25
40, 100, 100,25, 25
100, 40, 100,25, 25
...

Da die Liste immer 5 Elemente hat, gibt es 5! = 120 Einträge. Etliche sind Duplikate, da 100 und 25 mehrfach vorkommen. Aber das ist erstmal egal.

- Fange an, Hölzer zu zersägen:
Für jedes Element aus [100, 100, 40, 25, 25], [40, 100, 100,25, 25], [100, 40, 100,25, 25], ...:

1. Erzeuge ein neues Holz und behalte es als Aktuelles.
2. Für jeden Einzel-Schnitt aus der Liste:.
3. Falls das aktuelle Holz zu kurz ist, füge es der Liste benutzter Hölzer hinzu, erzeuge ein neues Holz und behalte es als Aktuelles.
4. Zieh die Länge des Einzel-Schnittes vom aktuellen Holz ab und merke Dir (am Holz) den Einzel-Schnitt in einer Liste.

• Das Array

  permIndices

  in

  makeCuts()

  enthält alle Permutation von [0,1,2,3,4] und dient als Liste von Indices in das Array [100, 100, 40, 25, 25].
• Im Resultat von

  makeCuts()

  ist keine Sortierung, man könnte den Typ

  List<List<Wood>>

  leicht umbauen und sortieren.
• Der Gesamtverschnitt ist immer derselbe, das Hauptproblem ist die minimale Anzahl von Hölzern zu erreichen, in dem man jedes einzelne optimal zersägt. Alternativ könne man noch wollen, dass der Verschnitt pro Holzstück minimal ist und wenige aber sehr lange Hölzer übrigbleiben.

package perm;

import java.util.ArrayList;
import java.util.List;

public class Main {

	class Wood {
		List<Integer> cuts = new ArrayList<>();
		int remainingCm;
		
		Wood(final int length) {
			this.remainingCm = length;
		}

		@Override
		public String toString() {
			return "Wood [" + (cuts != null ? "cuts=" + cuts + ", " : "")
					+ "remainingCm=" + remainingCm + "]";
		}
	};
	
	public static void main(String[] args) {
		
		final List<List<Wood>> compute = new Main().makeCuts(250, 100, 100, 40, 25, 25);
		for (List<Wood> list : compute) {
			System.out.println(list);
		}
	}
	
	public List<List<Wood>> makeCuts(int length, int... sizes) {
		final int numComputations = factorial(sizes.length);
		final int[][] permIndices = quickPerm(sizes.length);

		final List<List<Wood>> result = new ArrayList<>(numComputations);
		for (final int[] perm : permIndices) {
			
			final List<Wood> currentWoods = new ArrayList<>();
			Wood w = new Wood(length);
			currentWoods.add(w);

			for (final int index : perm) {								
				
				final int currentLength = sizes[index];
				
				if( w.remainingCm < currentLength) {
					w = new Wood(length);
					currentWoods.add(w);
				}
				
				w.remainingCm -= currentLength;
				w.cuts.add(currentLength);
			}	
			result.add(currentWoods);
		}

		return result;
	}

	public int factorial(int i) {
		int f = i;
		while (--i > 0) {
			f *= i;
		}

		return f;
	}

	/**
	 * [url=http://www.freewebs.com/permute/quickperm.html]Counting QuickPerm - C++ Linear Array Permutations Without Recursion[/url]
	 */
	public int[][] quickPerm(final int N) {

		int i, j, tmp, index = 0;

		final int[][] result = new int[factorial(N)][N];
		final int a[] = new int[N];
		final int p[] = new int[N];

		for (i = 0; i < N; i++) {
			a[i] = i;
			p[i] = 0;
		}

		System.arraycopy(a, 0, result[index++], 0, N);

		i = 1;
		while (i < N) {
			if (p[i] < i) {
				j = i % 2 * p[i];
				tmp = a[j];
				a[j] = a[i];
				a[i] = tmp;

				System.arraycopy(a, 0, result[index++], 0, N);
				p[i]++;
				i = 1;
			} else {
				p[i] = 0;
				i++;
			}
		}

		return result;
	}
}

 

[oetzi]

@Kaibear: Danke für den Link. Ehrlich gesagt habe ich nach kurzem Lesen aufgehört. Leider findet man in solchen wiki Artikeln die rein akademische Lösung beschrieben. Ich hatte zwar auch Mathekurse in meinem Studium, aber das geht doch weit über meinen Horizont hinaus 🙂

@kay73:
Ich glaube grob verstanden zu haben, was du meinst.


Ich hatte in der Zwischenzeit ein bisschen weiter getüftelt.
Mittlerweile lasse ich eine Baumstruktur erstellen, die ausgehend von einer Startlänge alle weiteren Kombination darstellt und jeweils den Verschnitt ausgibt.
Das nächste große Problem ist aus den vielen Möglichkeiten die sinnvollste auszuwählen.
Oh man, hätte ich vorher gewusst, was da auf mich zukommt 🙂
Wenn ich mir nur die Komplexität des Wikiartikels angucke, wird es wohl schwer sein hier eine perfekte Lösung (zumindest auf die Schnelle) zu finden.
Vielleicht lasse ich es auch einfach gut sein. Der Holzhandel meines Vertrauens wird das schon hinkriegen ;-)