Seite 1 von 1

Aufgabe 4.3

Verfasst: 23. Aug 2008 18:07
von David
Hallo,

kann mir irgendwer erklären, was man bei Aufgabe 4.3 machen soll :?:
Super wäre, wenn jemand seinen Code postet!


Viele Grüße

David

Re: Aufgabe 4.3

Verfasst: 24. Aug 2008 11:40
von Ultr1
Hallo,

das Frequency Problem ist wie folgt zu verstehen: Du hast mehrere Knoten (Funkmasten), die jeweils mehrere Farben (Frequenzen) handeln müssen können. Zu jedem bestimmten Zeitpunkt hat also jeder Knoten eine bestimmt Zahl an Anfragen (Anrufen). Jeder Knoten muss jetzt seine Farben so vergeben, dass er nicht mit seinen Nachbarn in einen Konflikt kommt. Er darf also nicht ein einziges mal die gleiche Farbe wie einer seiner Nachbarn haben. Im Grunde genommen ist das das einfach Coloring-Problem, bei dem nun jeder Knoten aber eine Menge von Farben hat.

Nun soll das ganze auf das Online-Problem umgebaut werden. Es kommen also mehrere Chunks an, bei denen sich die Anfragen ändern. Bei jedem Knoten können Leute auflegen und neue Anrufe können hinzukommen. Wie woanders im Forum erwähnt ist es jetzt frei, ob man die vorhandene Lösung ändert oder wegwirft und das Problem neu löst.
Ich habe es mir ganz einfach gemacht:
Ohne Online-Problematik reicht als Input für jeden Knoten eine Zahl, nämlich die Zahl der Farben, die er vergen muss. Online kommen nun mehrere Chunks, also erhalte ich als Eingabe ein Array mit mehreren Zuständen. Ich sage nicht das Farben pro Knoten hinzukommen oder wegfallen. Ich erwarte einfach als Eingabe das neue Szenario, also die neue Anzahl an Requests pro Knoten. Ich löse das Coloring-Problem somit also mehrfach, ähnlich wie bei Aufgabe 3, als die EIngabe mehrere Anfragen an Zugverbindungen waren.

Das ist meine Idee, weiß aber nicht, ob das so schmeckt.

Gruß