Aufgabe 4.3

Moderator: Algorithmische Modellierung

David
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 23. Jun 2005 15:28

Aufgabe 4.3

Beitrag von David » 23. Aug 2008 18:07

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

Benutzeravatar
Ultr1
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 13. Okt 2004 17:53
Wohnort: Dreieich
Kontaktdaten:

Re: Aufgabe 4.3

Beitrag von Ultr1 » 24. Aug 2008 11:40

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ß
Es ist nicht entscheidend, was der Mensch tut, sondern was er ist. (Henry Miller)

Antworten

Zurück zu „Algorithmische Modellierung“