Verzweigen und beschränken SS09

Aus ProgrammingWiki

Autoren

• Stefan Bradl(sistbrad@stud.hs-zigr.de )
• Sebastian Rudolf (siserudo@stud.hs-zigr.de)

Vorlesungsfolien:

Branch_and_Bound.pdf (0.3 MB)

Inhaltsverzeichnis 1 Motivation 2 Ziel 3 Einführung Branch and Bound 3.1 Schranke, Expandierung und Prioritätenliste 4 Rucksackproblem 5 Rundreiseproblem 5.1 Naiver Algorithmus 5.2 Mögliche Bewertungsfunktionen 5.3 Lösung mit Branch and Bound 6 Übung

Motivation

Wie bekannt kann die Lösungssuche bei Problemen als Baum visualisiert werden. Wir wissen auch, dass die Lösungsbäume bei der systematischen und vollständigen Suche enorm groß werden. Es ergibt sich also ein exponentieller Aufwand. Betrachten wir den folgenden Baum.

Angenommen jede Kante und jeder Knoten benötigt eine Grundoperation, dann würde die Erstellung des Baumes bei vollständiger Suche 33 Grundoperationen benötigen (17 Knoten + 16 Kanten). Wenn nun mit Hilfe von Branch and Bound der komplette rechte Teilbaum entfällt, so werden nur noch 13 Grundoperationen benötigt. Auch wenn wir nichts am exponentiellen Aufwand ändern können, so haben wir in dem Beispiel einen deutlichen praktischen Nutzen bemerkt.

Ziel

Unser Ziel ist es diesen exponentiellen Aufwand zu verringern.

zu mit und/oder . Wir wollen also die Aufwandsfunktion so beeinflussen, dass sie unterhalb der Aufwandsgleichung ohne Verzweigen und Beschränken liegt.

Ein Ansatz das zu erreichen besteht darin, Teilbäume, die nicht zum gewünschten Ergebnis führen, zu entfernen, den Baum also auszuästen.

Einführung Branch and Bound

Für das eben beschriebene Ausästen gibt es ein Hilfsmittel namens Branch and Bound (Verzweigen und Beschränken). Bei diesem Verfahren werden die Knoten des Lösungsbaumes bewertet. Je nach Bewertung der Knoten können nun diejenigen Knoten weiter verfolgt werden, welche die für das Problem beste Lösungsaussichten bieten. Im Idealfall muss also in jedem Schritt nur ein einziger Knoten verfolgt werden.

Zur Bewertung der Knoten wird die so genannte Bewertungsfunktion benötigt. Das Finden einer guten Bewertungsfunktion stellt die größte Schwierigkeit bei Branch and Bound dar. Es gibt kein Verfahren welches das Finden der Bewertungsfunktion ermöglicht. Die Bewertungsfunktion ist immer von der konkreten Problemstellung abhängig, die Güte dieser in aller Regel von der Erfahrung des Suchenden. Das Finden einer guten Bewertungsfunktion ist Grundlage für die Optimierung der Schranke (engl.: bound) und somit zur Lösungsfindung, dem Optimum.

Das Vorgehen beim Verzweigen (engl.: branch) wird deutlich wenn man die Verfahrensweise bei der Expandierung und den Expandierungskandidtaten genauer betrachtet.

Schranke, Expandierung und Prioritätenliste

Je nach Problem und Bewertungsfunktion kann man zwischen Minimierungs- und Maximierungsproblemen unterscheiden. Handelt es sich um ein Minimierungsproblem, so wird der Knoten mit der niedrigsten Bewertung expandiert. Als Beispiel für ein klassisches Minimierungsproblem wäre die Suche nach dem kürzesten Weg zwischen mehreren Stationen bzw. Orten zu nennen.

Analog dazu wird bei einem Maximierungsproblem der Knoten mit der höchsten Bewertung expandiert. Ein Beispiel hierfür ist die Auslastung der Produktionskapazität einer Fabrik, wo es darum geht die Produkte in der Kombination zu produzieren, das die Auslastung nicht überschritten wird und der maximale Gewinn mit den produzierten Gütern erzielt werden kann.

Es ist dennoch möglich, wenn auch nicht unbedingt sinnvoll, beispielsweise die kürzesten Distanzen mit den höchsten Bewertung zu wichten, je nach Bewertungsfunktion, diese Differenzierung ist essentiell für das Verständnis. Es geht primär um das bewerten des Knotens mit der besten Erfolgsaussicht.

Die Schranken werden bei Minimierungsproblemen als untere und bei Maximierungsproblemen als obere Schranken angegeben.

Die Knoten eines Baumes dienen als Bewertungsziel und werden, je nach Güte, expandiert, dabei beginnt die Expandierung immer bei der Wurzel des Baumes. In jedem Schritt wird nur ein Knoten, jener mit der besten Erfolgsaussicht, expandiert.

Es kann vorkommen das die Expandierung eines Knotens nicht zum Ziel führt. Aus diesem Grund sind auch die übrigen Knoten des Baumniveaus potentielle Expandierungskandidaten. Die Knoten müssen also gespeichert werden. Da die Bewertung der Knoten bei der Weiterverarbeitung eine Rolle spielt, bietet sich eine so genannte Prioritätenliste (engl.: priority queue) an. In dieser sind die Expandierungskandidaten je nach Optimierungsproblem nach ihrer Bewertung geordnet.

Welcher Knoten expandiert wird entscheidet das Verfahren also anhand der Prioritätenliste, welche nach jeder Knotenbewertung aktualisiert wird. Expandiert wird immer das erste Element dieser Liste. Ist ein Knoten nicht mehr expandierbar wird er aus der Prioritätenliste entfernt. Damit ist die Position eines Knotens im Baum, für das Verfahren, irrelevant.

Expandierungsablauf: Wurde die Wurzel bewertet wird dieser Knoten mit seiner Bewertung in der Priotitätenliste eingeordnet. Als erstes und bisher einzigstes Element der PL wird dieser Knoten nun weiter expandiert. Der entstehende Kindsknoten wird bewertet und in die PL eingeordnet. Es wird nun geprüft ob der Elternknoten, der Knoten von dem aus expandiert wurde, noch Expandierbar ist. Ist dies nicht der Fall so wird dieser aus der PL entfernt. Erneut wird das erste Element der PL expandiert, dieses muss nicht zwangsweise der Elternknoten des zuletzt expandierten sein da die Prioritätenliste selbstverständlich sortiert ist. Ist eine Bewertung des aktuell expandierten Knotens identisch mit der des Elternknoten wird der Kindknoten hinter diesem in der PL eingeordnet, da der Kindknoten nur gleichwertig ist.

Im worst-case-Szenario ist der Zielknoten der letzte Expandierungsschritt wobei alle Knoten des Baumes expandiert werden musten.

Rucksackproblem

Ein Mittel zur Beschreibung eines Sachverhaltes ist die Formulierung eines Problem. Das 0/1-Rucksackproblem ist ein solches Problem und dient in der Komplexitätstheorie als weit verbreitetes Beispiel-Problem welches es zu lösen gilt. Der Kontex ist das Entscheidungs-/Auswahl-Problem für eine Menge von Objekten welche je einen Wert und je ein Gewicht besitzen wenn eine Kapazität (Gewichts- oder Wert-Grenze) die Kombinationsmöglichkeit dieser Objekte beschränkt und die optimale Objektkombination gefunden werden soll. Diese Obejkte können weitere Eigenschaften besitzen die für dessen Wichtung von Bedeutung sind aber nicht direkt im Zusammenhang mit dem eigentlichen Wert stehen. Um einen eindeutigen Wert zu erschaffen an dem sich alle Objekte vergleichen lassen wird ein spezifische Wert gebildet.

Das Optimum kann mit Hilfe von Branche and Bound mit geringem Aufwand gefunden werden. Das Ergebnis wird in Form eines Vektors dargestellt. Es ergibt sich aus dem Kontex folgende mathematische Formulierung:

für alle Elemente
Der gesuchte Ergebnisvektor ist dabei , mit sodass dessen Werte und genügen.

Vorgehen:
Die Wertepaare werden in eine Tabelle einordnen.
Der spezifischen Wertes wird () für jedes Wertepaar ermittelt.
Die Tabelle wird geordnet, absteigende Ordnung der Spalten nach dem spezifischen Wert.
Das Objekt mit dem höchsten spezifischen Wert wird durch die Bewertungsfunktion bewertet und als Wurzelknoten verwendet. Das weitere Verfahren ist anhand des Beispiels noch einmal verdeutlicht.

Partielles Beispiel:
Vier Beispiel-Objekte mit folgenden Eigenschaften:
Die Gewichten: 1, 3, 9, 7 sowie die Werte: 3, 5, 10, 11 , die Kapazität ist auf 12 beschränkt.
Damit ergibt sich eine Objektmenge mit Wertepaaren Obj = {(1, 3), (3, 5), (9, 10), (7, 11)} und .

Die Bewertungsfunktion sei: Bewertung = aktuelle Wertsumme + (Kapazität - aktuelle Gewichtssumme) * spezifischer Wert des einzupackenden Objektes.

Ziel ist es den Ergebnissvektor mit maximaler Wertesumme zu finden, beim einhalten der Kapazitätsgrenze.

Ermittelt man nun den spezifischen Wert und ordnet alle zugehörigen Werte in eine Tabelle entsteht folgende Darstellung:

i	1	2	3	4
	3	5	11	10
	1	3	7	9
	3	1.7	1.6	1.1

Somit wird sichergestellt das das Objekt mit dem besten spezifischen Wert als Wurzelknoten verwendet wird.

Bewerten des Wurzelknotens: 0 + (12 - 0) * 3 = 36 Prioritätenliste PL=(36), erstes Element ist expaniderbar da es noch weitere ungenutzte Objekte gibt. Expandierung des ersten Elementes der PL. Bewertung: 3 + (12 - 1) * 1.7 = 21.7
Prioritätenliste PL=(36, 21.7) -> Expandierung 36
Bewertung: 5 + (12 - 3) * 1.6 = 19.4
Prioritätenliste PL=(36, 21.7, 19.4) -> Expandierung 36
Bewertung: 11 + (12 - 7) * 1.5 = 18.5
Prioritätenliste PL=(36, 21.7, 19.4, 18.5, 10) -> Expandierung 36
Bewertung: 10 + (12 - 9) * 0 = 10 -> 0 da kein nächstes Objekt mit einem spezifischem Wert nach dem letzten Obejkt der Tabelle existiert
Prioritätenliste PL=(36, 21.7, 19.4, 18.5, 10) -> 36 ist nicht mehr expandierbar, streiche 36

Prioritätenliste PL=(21.7, 19.4, 18.5, 10) -> Expandierung 21.7
Bewertung: (3+5) + (12 - (1+3)) * 1.6 = 20.8
Prioritätenliste PL=(21.7, 20.8, 19.4, 18.5, 10) -> Expandierung 21.7
Bewertung: (3+11) + (12 - (1+7)) * 1.5 = 20
Prioritätenliste PL=(21.7, 20.8, 20, 19.4, 18.5, 10) -> Expandierung 21.7
Bewertung: (3+10) + (12 - (1+9)) * 0 = 13
Prioritätenliste PL=(20.8, 20, 19.4, 18.5, 13, 10) -> da 21.7 nicht mehr expandierbar wird nun 20.8 expandiert

Diese Verfahrensweise wird bis zum erreichen der Kapazitätsgrenze fortgeführt, bereits gestrichene Objekte stehen nicht mehr zur Expandierung zur Verfügung. Ist K erreicht ergibt sich die Reihenfolge und Verwendung der Objekte die zu diesem Knoten führen den Ergebnisvektor und damit das Optiumum.

public void calcOpti(LinkedList vl, Double capac) { LinkedList citSeq = new LinkedList(); LinkedList citAva = new LinkedList(); HashMap hm = new HashMap(); Double vS =0.0; Double wS =0.0; Double sV =0.0; Double maxrate = 0.0; vl = this.calcSpecValSortList(vl); //key = verketter index-string aus vl value = knotenbewertung maxrate = this.rateKnot(0.0, 0.0, capac, vl.getFirst().get(2)); hm.put(Integer.toString(-1) , maxrate); //Verzweigung und Bewertung while(citSeq.size() < vl.size() && wS <= capac) { //Vergleichs-Key String seq = ""; for(int i=0; i < citSeq.size(); i++) seq += citSeq.get(i).toString(); citAva = new LinkedList(); boolean expandable = false; for(int i=0; i < vl.size(); i++) { if(!hm.containsKey(seq+Integer.toString(i)) && !citSeq.contains(i)) { citAva.add(i); expandable = true; } //wenn expandable false -> ein schritt zurück und mit nächsten knoten weiter (hashmap-check) if(i == vl.size()-1 && expandable == false) { citSeq.removeLast(); citAva = new LinkedList(); i=0; } } System.out.print("\n\nSequenz: "); for(int i=0;i<citSeq.size();i++) System.out.print(citSeq.get(i).toString()); System.out.println(""); //Verzweigen int index = 0; int pos=0; Double rate = 0.0; Double temprate = 0.0; while(index < citAva.size() && rate < maxrate) { vS =0.0; wS =0.0; sV =0.0; for(int i=0; i<citSeq.size();i++) { vS +=vl.get(citSeq.get(i)).get(1); wS +=vl.get(citSeq.get(i)).get(0); } wS += vl.get(citAva.get(index)).get(0); vS += vl.get(citAva.get(index)).get(1); System.out.println("Knotenwertsummen: valueSum:"+vS+" weightSum:"+wS+" "+citSeq.size()); if(wS <= capac) { if(index < vl.size()-1) sV = vl.get(citAva.get(index+1)).get(2); rate = this.rateKnot(vS,wS,capac,sV); System.out.println("Bewertung valueSum:"+vS+" weightSum:"+wS+" capac:"+capac+" specValue:"+sV+" rate:"+rate+"\n"); hm.put(seq+citAva.get(index).toString(), rate); //mit HashMap merken wo man bereits war if(Double.compare(rate.doubleValue(),temprate.doubleValue()) > 0) { temprate = rate; pos = index; } if(Double.compare(rate.doubleValue(),maxrate.doubleValue()) > 0) { citSeq.add(citAva.get(index)); index=citAva.size()+1; } index++; if(index==citAva.size()) { //System.out.println("POS "+pos); maxrate = rate; citSeq.add(pos); } } else { System.out.println("Wertsumme > Kapazität, Verfahren terminiert."); index++; } } } //Ergebnisvektorausgabe System.out.print("\n\n\n------------------\nDer ergebnisvektor lautet: ( "); for(int i=0;i<vl.size();i++) {if(i < citSeq.size()) { if(citSeq.get(i).compareTo((Integer)i)==0) System.out.print("1 "); } else System.out.print("0 "); } System.out.print(")"); } //Bewertung = aktuelle Wertsumme + (Kapazität - aktuelle //Gewichtssumme) * spezifischer Wert des einzupackenden Objektes. public Double rateKnot(Double valSum, Double weiSum, Double Capa, Double specVal) { return valSum + (Capa - weiSum) * specVal; } public LinkedList calcSpecValSortList(LinkedList vl) { double specVal=0; for(int c=0;c<vl.size();c++) { specVal = vl.get(c).get(1)/vl.get(c).get(0); vl.get(c).add(specVal); } for(int i=0;i<vl.size()-1;i++) { if(vl.get(i).get(2)<vl.get(i+1).get(2)) { Vector a = new Vector(); a = vl.get(i); vl.set(i, vl.get(i+1)); vl.set(i+1, a); } } return vl; }

LinkedList vlist = new LinkedList(); Vector i1 = new Vector(); i1.add(1.0); i1.add(3.0); Vector i2 = new Vector(); i2.add(3.0); i2.add(5.0); Vector i4 = new Vector(); i4.add(7.0); i4.add(11.0); Vector i3 = new Vector(); i3.add(9.0); i3.add(10.0); vlist.add(i1); vlist.add(i2); vlist.add(i3); vlist.add(i4); calcOpti(vlist, 12.0);

ausführen

Rundreiseproblem

Beim Rundreiseproblem (engl.: traveling salesman problem) handelt es sich um ein Optimierungsproblem, genauer gesagt ein Minimierungsproblem. Gesucht ist dabei die kürzeste Rundreise, wobei jede Stadt genau einmal besucht werden muss.

Es ist heute oft in der Logistikbranche anzutreffen. Es sind jedoch auch andere Anwendungsgebiete denkbar, wie zum Beispiel Maschinensteuerung.

Beispiel: Plotter

Angenommen wir wollen ein Viereck mittels eines Plotters zeichnen.

Weiter nehmen wir an, dass das Zeichnen jeder Strecke 10 ms und das Anheben/Absetzen 1 ms in Anspruch nimmt. Das bewegen des Schreibkopfes soll ebenfalls 10 ms für jede Strecke dauern.

Die Reihenfolge, in der die Seiten gezeichnet werden wählen wir zufällig:

Unter der Annahme, dass sich der Plotter bereits im Punkt befindet wird die Zeit, die zum Zeichnen des Vierecks benötigt wird folgendermaßen berechnet;

Daraus würde sich eine Gesamtzeit von 91 ms ergeben.

Würden wir die einzelnen Strecken allerdings in einer bestimmten Reihenfolge zeichnen, so würden einige unütze Bewegungen des Schreibkopfes entfallen. Unsere neue Zeichenreihenfolge sieht folgendermaßen aus: Mit dieser Reihenfolge konnte die Gesamtzeit auf 43 ms reduziert werden.

Für Privatanwender mag diese Zeitersparnis auf den ersten Blick kaum relevant sein. Allerdings haben wir in dem Beispiel nur ein kleines Viereck gezeichnet. In der Praxis (z.B. Ingenieurbüro) werden sehr viel komplexere Zeichnungen erstellt und ein Plottvorgang kann durchaus mehrere Minuten (im Extremfall sogar Stunden) dauern. Ein anderes Beispiel wären auch Fräsmaschinen. Da in Unternehmen häufig die Formel zutrifft (genau genommen kann man die Größen Zeit und Geld nicht gleichsetzen, da sie unterschiedliche Einheiten haben, besser wäre zu sagen, dass sich Zeit und Geld in einem proportionalem Verhältnis befinden) kommt es auf jede Zeitersparnis an. Nicht zuletzt wird durch die Optimierung der Maschinenwege auch deren Abnutzung verringert.

Naiver Algorithmus

Der offensichtlichste Ansatz das Rundreiseproblem zu lösen besteht darin, alle möglichen Rundreisen zu generieren. Daraus ergeben sich verschiedene Rundreisen. Die Anfangsstadt ist auch gleichzeitig die Zielstadt. Durch Anwendung der STIRLINGschen Formel ergibt sich allein für die Erstellung aller möglichen Rundreisen ein exponentieller Aufwand:

Die eigentliche Bestimmung der Lösung ist in diesem Aufwand noch nicht inbegriffen!

Nachdem alle möglichen Rundreisen erstellt wurden, können mit Hilfe der Entfernungsmatrix die einzelnen Längen der Reisen berechnet werden. Anschließend wird die Reise mit der kürzesten Entfernung als Ergebnis genommen.

Das eben beschriebene Verfahren sieht sehr einfach aus. Warum wird es also nicht in der Praxis genutzt? Dazu reicht ein Blick in die folgende Tabelle.

Anzahl der Städte	mögliche Rundreisen
3	2
5	24
10	362.880
15	87.178.291.200
20	121.645.100.408.832.000
50	608.281.864.034.267.560.872.252.163.321.295.376.887.552.831.379.210.240.000.000.000

Mögliche Bewertungsfunktionen

Wie wir gesehen haben ist der naive Ansatz zur Lösung des Rundreiseproblem zwar einfach zu verstehen, hat also eine geringe kognitive Komplexität, ist in der Praxis jedoch nicht anwendbar. Folglich müssen wir nach einem effizienteren Algorithmus zur Lösung des Rundreiseproblems suchen.

Unser erster Ansatz besteht darin, die Summe der Teilweglängen der bisherigen Teilstrecke zu nehmen und die Entfernung bis zum nächsten unbesuchten Knoten dazu zu addieren. Das Problem dieses Ansatzes besteht darin, dass zwar der bisherige Weg und der Weg zum nächsten Ort kurz sein kann, der Restweg dafür aber extrem lang.

Es wäre auch möglich, die Bewertung an Hand aller hinführenden und wegführenden Strecken zu ermitteln. Diese würde man addieren und durch zwei teilen, um eine Doppelzählung zu vermeiden. Man bekommt durch dieses Verfahren allerdings nur eine Näherungslösung.

Wir sind also immer noch nicht an unserem Ziel angekommen, eine Bewertungsfunktion zu finden, welche uns das optimale Ergebnis liefert.

Lösung mit Branch and Bound

Um das Problem mit Verzweigen und Beschränken lösen zu können benötigen wir eine Bewertungsfunktion. Eine Möglichkeit, die auch wirklich zur kürzesten Rundreise führt besteht in der Verwendung von Entfernungsmatrizen für die Distanzen zwischen den Städten. In dieser Matrix werden unzulässige Verbindungen mit \ markiert. Entfernungsmatrizen müssen nicht symmetrisch sein. Auf Grund von Einbahnstraßen etc. kann es durchaus sein, dass Hin- und Rückweg unterschiedlich sind.

Das Verfahren funktionert folgendermaßen:

Als Ausgangsmatrix kommt die gegebene Entfernungsmatrix zum Einsatz. Im ersten Schritt wird diese Ausgangsmatrix reduziert. Diese Reduktion geschieht so: Zuerst wird für jede Zeile das Minimum ermittelt. Dieses Minimum wird in eine extra Spalte rechts neben die Zeile geschrieben. Danach wird das Minimum von allen Zellen in der Zeile subtrahiert. Das Ergebnis wird dann in der entsprechenden Zelle als Fußnote an den Ausgangswert angefügt. Nachdem die Zeilenminima gebildet wurden, werden die Spaltenminima der eben berechneten Fußnoten gebildet. Die Spaltenminima werden in eine neue Zeile unterhalb der Matrix geschrieben. Um die konkrete Knotenbwertung zu erhalten werden nun alle Zeilen- und Spaltenminima addiert. An Hand der Bewertung wird der Knoten nun in die priority queue eingefügt.

Als nächstes ermittelt man die Matrix, die im Knoten () benötigt wird. Dazu wird in Zeile und Spalte der Wert aus der Ausgangsmatrix übernommen. Anschließend müssen einige Zellen mit markiert werden. Dies geschieht an Hand folgender Regeln:

1. Setze für alle , denn wird genau von aus besucht.
2. Setze für alle , denn ein Weg von zu einem anderen Knoten als ist verboten.
3. Setze , denn der Weg von nach steht nicht mehr zur Verfügung.

Hat man diese Modifikationen vorgenommen, kann wieder die Bewertung ermittelt werden. Der Knoten wird dann ebenfalls in die priority queue eingefügt. Der Vorgang wiederholt sich dann für jeden Knoten, der in der priority queue an vorderster Stelle steht. Kann ein Knoten nicht mehr expandiert werden, so wird er aus der priority queue entfernt.

An Hand der Übung 5 und der dazugehörigen Lösung kann der Algorithmus Schritt für Schritt nachfolzogen werden.

Der folgende Code stellt eine Javaimplementation zur Bewertung einer Entfernungsmatrix.

public Object NewDistanceMatrix() { double[][] matrix; double rating; void copyCtor(Object m) { matrix = new double[m.matrix.length][m.matrix[0].length]; for(int line = 0; line < m.matrix.length; ++line) { for(int column = 0; column < m.matrix[0].length; ++column) { matrix[line][column] = m.matrix[line][column]; } } } void ctor(double[][] m) { matrix = m; } void print() { for(int line = 0; line < matrix.length; ++line) { for(int column = 0; column < matrix[0].length; ++column) { if(matrix[line][column] == Double.MAX_VALUE) { System.out.print("INF" + "\t"); } else { System.out.print(matrix[line][column] + "\t"); } } System.out.println(""); } } double getRating() { return rating; } int getCities() { return matrix.length; } // i ... current node // j ... target node void modify(int i, int j) { i -= 1; j -= 1; // E[z,j] = INF for(int z = 0; z < matrix.length; ++z) { if(z != i) { matrix[z][j] = Double.MAX_VALUE; } } // E[i,s] = INF for(int s = 0; s < matrix.length; ++s) { if(s != j) { matrix[i][s] = Double.MAX_VALUE; } } // E[j,i] = INF matrix[j][i] = Double.MAX_VALUE; } void calculateRating() { rating = 0; double[][] clone = matrix; for(int i = 0; i < matrix.length; ++i) { clone[i] = matrix[i]; } // line reduction for(int i = 0; i < clone.length; ++i) { double lineMinimum = minimum(clone[i]); rating += lineMinimum; for(int j = 0; j < clone[i].length; ++j) { if(clone[i][j] != Double.MAX_VALUE) { clone[i][j] -= lineMinimum; } } } // column reduction for(int i = 0; i < clone[0].length; ++i) { double[] column = new double[clone.length]; for(int j = 0; j < clone.length; ++j) { column[j] = clone[j][i]; } rating += minimum(column); } } double minimum(double[] m) { double minimum = Double.MAX_VALUE; for(int i = 0; i < m.length; ++i) { if(m[i] != Double.MAX_VALUE) { if(m[i] < minimum) { minimum = m[i]; } } } return minimum; } return this; }

Im folgenden Eingabefenster kann eine Entfernungsmatrix eingegeben werden. Es können auch mehr als 4 Städte angegeben werden.

// Erzeugung der Entfernungsmatrix double[][] distanceMatrix = new double[4][4]; distanceMatrix[0][0] = Double.MAX_VALUE; distanceMatrix[0][1] = 20; distanceMatrix[0][2] = 15; distanceMatrix[0][3] = 10; distanceMatrix[1][0] = 8; distanceMatrix[1][1] = Double.MAX_VALUE; distanceMatrix[1][2] = 9; distanceMatrix[1][3] = 8; distanceMatrix[2][0] = 6; distanceMatrix[2][1] = 12; distanceMatrix[2][2] = Double.MAX_VALUE; distanceMatrix[2][3] = 13; distanceMatrix[3][0] = 5; distanceMatrix[3][1] = 10; distanceMatrix[3][2] = 9; distanceMatrix[3][3] = Double.MAX_VALUE; Object dm = NewDistanceMatrix(); dm.ctor(distanceMatrix); // modify(1, 4) bedeuted gehe von Stadt 1 zu Stadt 4 dm.modify(1, 4); System.out.println("1->4"); dm.print(); dm.modify(4, 2); System.out.println("1->4->2"); dm.print(); dm.modify(2, 3); System.out.println("1->4->2->4"); dm.print(); dm.calculateRating(); System.out.println("Distance: " + dm.getRating());

ausführen

Übung

1. Stellen Sie die Signatur und Axiome für den abstrakten Datentyp priority queue auf. (zur Hilfe: Wikipedia-ADT)
   
2. Gegeben ist folgender Baum mit Knotenbewertungen (Maximierungsproblem):
   

   
   Verinnerlichen Sie sich die Funktionsweise der priority queue, indem sie den Inhalt der priority queue in jedem Schritt aufschreiben!
   

3. Gegeben sind folgende 4 Gegenstände (Gewicht . Wert):
   (1 . 3)
   (3 . 5)
   (9 . 10)
   (7 . 11)
   
   Die Kapazität des Rucksacks beträgt 12.
   Die Bewertungsfunktion ist die Selbe wie die im Buch auf Seite 90 verwendete.
   (Bewertungsfunktion := Aktuelle Wertsumme + (Kapazität - Gewichtssumme) * spezifischer Wert des nächsten Gegenstandes)
   Finden Sie die optimale Gegenstandskombination. Stellen sie dazu zuerst wie auf Seite 89 im Beispiel 6.1 zu sehen eine Tabelle mit den spezifischen Werten auf.
   
4. Überprüfen Sie, dass die Lösung des TSP auf Seite 96 im Bild 6.2 auch wirklich das korrekte Ergebnis liefert.
5. Gegeben ist folgende Entfernungsmatrix:
   

   von\nach	Dresden	Zittau	Görlitz	Bautzen
   Dresden		108	109	63
   Zittau	114		37	46
   Görlitz	110	35		49
   Bautzen	65	46	51

   
   Ermitteln sie die kürzeste Rundreise zwischen den Städten. (kontrollieren Sie das Ergebnis mit Google-Maps)

Lösungen