Hallo zusammen,
ich habe ein Problem bei dem ich zuerst etwas weiter ausholen muss: Ich habe ein gegebenes Problem das aus mehreren Aufgaben mit einer bestimmten Arbeitsdauer und einer bestimmten Anzahl an Prozessoren besteht, die diese Aufgaben lösen sollen. Ich kann nun diese Aufgaben beliebig auf die Prozessoren aufteilen. Also zum Beispiel so: CPU0 : 0 ,4 ,8 = 350
CPU1 : 3 ,9 ,16 ,18 = 999
CPU2 : = 0
CPU3 : 7 ,10 ,13 ,14 = 993
CPU4 : 1 ,17 ,19 = 902
CPU5 : 2 ,11 ,12 = 550
CPU6 : 5 ,6 ,15 = 644
Gesamtlaufzeit: 999
D.h. der Prozessor mit der Nummer 0 bearbeitet die Aufgaben 0, 4 und 8, die zu bearbeiten 350 Zeiteinheiten brauchen. Woher die Zahlen genau eingelesen werden und wie so eine Loesung erstellt wird, das funktioniert schon ganz gut, daher will ich darauf nicht näher eingehen. Es gibt auf jeden Fall eine Klasse Problem und Klasse Loesung.
In der Klasse Loesung soll nun ein Iterator implementiert werden, der durch next() einen Nachbarn dieser Loesung liefert. Ein Nachbar ist dabei eine Loesung bei der einer beliebigen Aufgaben ein anderer beliebiger Prozessor zugeordnet wurde.
Da diese Zuweisung zufällig geschehen muss, ich später allerdings wissen muss ob ich alle Nachbarn durchlaufen habe ist habe ich dieser Klasse Loesung noch ein zweidimensionales Array zugewiesen, das dann so aussieht:
Dieses Array wird immer wieder wenn eine neue Loesung erstellt wird mit Nullen gefüllt bis auf die Stellen, die bereits durch die Loesung behandelt wurden, dort steht eine Eins.
Mein Iterator sieht jetzt so aus. bearbeitet ist hierbei ein Array das speichert welche Aufgabe durch welchen Prozessor bearbeitet wird. Also bearbeitet[2] = 3; heißt die Aufgabe 2 wird durch den Prozessor 3 bearbeitet. Es gibt auch einen Konstruktor, der dieses bearbeitet gleich festlegt.:
Das ist hier noch nicht zufällig. Aber das ist im Moment auch nebensächlich. Das Problem ist nur, dass später wenn ich den Nachbarn vom meiner Loesung lsg aufrufe durch:
Ist jedes Mal nachbar und lsg gleich. Und erst beim nächsten Durchlauf ist dann lsg ein neuer Nachbar. So ist das aber nicht gedacht. Kann mir da irgendjemand helfen.
mfg
quodlibet
ich habe ein Problem bei dem ich zuerst etwas weiter ausholen muss: Ich habe ein gegebenes Problem das aus mehreren Aufgaben mit einer bestimmten Arbeitsdauer und einer bestimmten Anzahl an Prozessoren besteht, die diese Aufgaben lösen sollen. Ich kann nun diese Aufgaben beliebig auf die Prozessoren aufteilen. Also zum Beispiel so: CPU0 : 0 ,4 ,8 = 350
CPU1 : 3 ,9 ,16 ,18 = 999
CPU2 : = 0
CPU3 : 7 ,10 ,13 ,14 = 993
CPU4 : 1 ,17 ,19 = 902
CPU5 : 2 ,11 ,12 = 550
CPU6 : 5 ,6 ,15 = 644
Gesamtlaufzeit: 999
D.h. der Prozessor mit der Nummer 0 bearbeitet die Aufgaben 0, 4 und 8, die zu bearbeiten 350 Zeiteinheiten brauchen. Woher die Zahlen genau eingelesen werden und wie so eine Loesung erstellt wird, das funktioniert schon ganz gut, daher will ich darauf nicht näher eingehen. Es gibt auf jeden Fall eine Klasse Problem und Klasse Loesung.
In der Klasse Loesung soll nun ein Iterator implementiert werden, der durch next() einen Nachbarn dieser Loesung liefert. Ein Nachbar ist dabei eine Loesung bei der einer beliebigen Aufgaben ein anderer beliebiger Prozessor zugeordnet wurde.
Da diese Zuweisung zufällig geschehen muss, ich später allerdings wissen muss ob ich alle Nachbarn durchlaufen habe ist habe ich dieser Klasse Loesung noch ein zweidimensionales Array zugewiesen, das dann so aussieht:
Code:
/**
* wir speichern die moeglichen Nachbarn in einem zweidimensionalen
* Array. Jeder dieser Array stellt genau eine neue Zuordnung einer
* Aufgabe zu einem Prozessor da. <code>int[i][j]</code> wuerde bedeuten, dass
* der Aufgabe i jetzt der Prozessor j zugewiesen wird
* Wenn diese Position den Wert 0 speichert bedeutet dies der
* Nachbar wurde noch nicht besucht. Falls er den Wert 1 speichert
* ist der schon besucht.
*/
private int[][] nachbarn;Mein Iterator sieht jetzt so aus. bearbeitet ist hierbei ein Array das speichert welche Aufgabe durch welchen Prozessor bearbeitet wird. Also bearbeitet[2] = 3; heißt die Aufgabe 2 wird durch den Prozessor 3 bearbeitet. Es gibt auch einen Konstruktor, der dieses bearbeitet gleich festlegt.:
Code:
public Iterator getNachbarn() {
return new Iterator() {
/**
* pruefen ob es eine weitere Loesung gibt
* @return entsprechenden Wahrheitswert
*/
public boolean hasNext() {
if(getLoesung() != next()) {
return true;
}else{
return false;
}
}
/**
* macht geht einen Schritt weiter und gibt das neue Ergebnis
* zurueck
* @return allerdings wird die Loesung als <code>Object</code>
* zurueckgegeben
*/
public Object next() {
Loesung neu = null;
/**
* wir durchsuchen nun das Feld und geben
* das Ergebnis zurueck sobald wir eine Null gefunden haben
*/
for(int i= 0; i < bearbeitet.length; i++) {
for(int j = 0; j < problem.getAnzahlCPUs(); j++) {
/**
* wir haben einen noch nicht besuchten Nachbarn
* gefunden
*/
if(nachbarn[i][j] == 0) {
// diese Loesung wird kopiert
neu = new Loesung(bearbeitet);
neu.problem = problem;
// nur mit einem vertauschten Wert
neu.bearbeitet[i] = j;
// nun ist dieser Nachbar besucht
nachbarn[i][j] = 1;
// wir geben diesen Nachbarn zurueck
return neu;
}
}
}
/**
* falls wir keine 0 gefunden haben wird der erste
* Wert von neu zurueckgegeben naemlich null
*/
return neu;
}
/**
* diese Methode ist nicht funktionsfaehig
* ist aber noetig um einen Iterator zum implementieren
*/
public void remove() {
throw new UnsupportedOperationException();
}
};
}Das ist hier noch nicht zufällig. Aber das ist im Moment auch nebensächlich. Das Problem ist nur, dass später wenn ich den Nachbarn vom meiner Loesung lsg aufrufe durch:
Code:
Loesung nachbar = (Loesung) lsg.getNachbarn().next();Ist jedes Mal nachbar und lsg gleich. Und erst beim nächsten Durchlauf ist dann lsg ein neuer Nachbar. So ist das aber nicht gedacht. Kann mir da irgendjemand helfen.
mfg
quodlibet
