TU Wien:Algorithmen und Datenstrukturen 1 VU (Raidl)/Programmieraufgabe 2 SS10

Anmerkung von koDiacc: Ich habe mal angefangen, eine "Struktur" zu erstellen. Falls ihr anderer Meinung seid, könnt ihr sie gerne ändern.

Einführung

Man muss 1-3 Heuristiken programmieren, die das Problem lösen. Die Heuristiken sollen in heuristic1() heuristic2() und heuristic3() in der Klasse RegisterAllocator.java implementiert werden. Das Framework nimmt dann den Algorithmus mit der Besten Lösung.

Mit -d -t als Parameter lassen sich Debug- sowie Zeitmeldungen ausgeben.

Hilfreiches

Collections(Listen) Sortieren

Absteigend sortieren einer Collection mit Integern und Prioritäten (das Array prioritäten muss dazu eine Instanzvariable der Klasse sein, ansonsten ist sie für die anonyme Klasse nicht sichtbar!)

Collections.sort(collection, new Comparator<Integer>() {
  public int compare(Integer t, Integer t1) {
    return prioritäten[t1.intValue()] - prioritäten[t.intValue()];
  }
 });

Sehr hilfreiche Seite hierzu: damit schafft man es (jetzt auch noch, wenn man von vorne beginnt!!!):

https://web.archive.org/web/20180730215519/https://www.java-blog-buch.de/d-objekte-sortieren-comparator-und-comparable/

How To?

• Als erstes sollte man im Konstruktor alles initialisieren was man braucht, denke ich.
• Nachdem der Eingangsparameter ein Set<Edge> edges ist, empfiehlt es sich mit edges.iterator() oder einer for-each-Schleife darauf zuzugreifen (for(Edge e:edges){...}). Auf die einzelnen Variablen der Klasse Edge kann man bei einem iterator z.B. so darauf zugreifen:

Edge e = iterator.next();
int knoten1 = e.node1;
int knoten2 = e.node2;

Input Files

Brauchen uns nicht zu kümmern. Wir bekommen die wesentlichen Informationen fix und fertig eingelesen in den Konstruktor

RegisterAllocator(int numNodes, Set<Edge> edges, int[] priorities) 

übergeben. Crispy 12:33, 22. Mai 2010 (CEST)

Div. Heuristiken

Diese Heuristiken stammen aus dem Informatik-forum, ich gebe keine Garantie darauf, dass sie immer gute Bewertungen erzielen -- Archonius

Heuristik 1

Knoten sortieren
für alle Knoten{
  Knoten in bestbewertetsten Register einfügen (Summe der Prioritäten des Registers (eventuell noch + die Anzahl an Knoten im Register))
  Wenn der Knoten in kein Register passt neues Register erstellen und dort einfügen
}

Wie die Knoten sortiert werden hat auf die Güte dieser Heuristik hohen Einfluss, Möglichkeiten wären(aus dem Forum):

• absteigend nach Priorität, wenn gleich aufsteigend nach Knotengrad (schafft bei mir 0004 auf grün --Archonius)
• absteigend nach Priorität, wenn gleich absteigend nach Summe der Prioritäten der Nachbarn
• absteigend nach Priorität/Knotengrad
• absteigend nach Priorität*Faktor/Knotengrad
• absteigend nach der folgenden Funktion:

Wert[n] = Priorität[n];
für jeden Knoten m der Nachbar von n ist {
 Wert[n] -= (Priorität[m] / Faktor);
}
Wert[n] = Math.ceil(Wert[n] * 10000) / 10000;
Wert[n] *= Nachbaranzahl_von_n;

Heuristik 2

solange es freie Knoten gibt{
  knoten1 = freier Knoten mit höchste Priorität
  knoten2 = freier Knoten mit zweithöchster Priorität
  den Besten der beiden Knoten in einen Register einfügen sofern möglich
  Wenn Knoten in kein Register passt neues Register erstellen
}

• freie Knoten sind die Knoten die noch nicht in einem Register vorkommen
• Die Entscheidung welcher der beste Knoten ist, kann nach höherer Priorität oder nach einer selbst bestimmten Bewertungsfunktion erfolgen.

Brainstorming

• Es geht auf jeden Fall mal um einen Graphen, den man Traversieren muss :p
• Das Ganze kann auch als Graph-Einfärbe-Problem gesehen werden. (Wie viele Farben brauche ich mindestens, um einen Graphen einzufärben, ohne, dass zwei benachbarte Knoten die selbe Farbe haben.)
• Artikel mit einigen Algorithmen dazu in der engl. Wikipedia. http://en.wikipedia.org/wiki/Graph_coloring#Algorithms

Links

• Angabe
• Thread im Inf.-Forum.at