Algorithmen: Knoten?

[ethrandil]

[überholt, siehe unten]

[Trap]

Das Thema nennt sich Graphenalgorithmen.

Kannst du die Aufgabenstellung nochmal anders formulieren? Aus der werd ich im Moment nicht schlau...

[ethrandil]

Also, man hat diverse Knoten die einen bestimmten Wert einnehmen sollen.
Für die Werte gibt es Bedingungen!
Die Werte von zwei benachbarten Knoten müssen sich z.b. um mindestens '3' unterscheiden!

Und der Algorithmus soll nun optimale gültige Werte für die Knotenpunkte finden.
Optimal sind sie z.B. wenn es möglichst wenig verschiedene Werte gibt oder die Summe der Beträge der Werte minimal sind, o.ä.

[DocEW]

Wahrscheinlich kommt es zu sehr darauf an, wie genau die "Bedingungen" sind und wie am Ende "optimal" definiert ist. So ganz allgemein kann man glaube ich nicht viel zu sagen. Sicher, das ganze wird am Ende ein Algorithmus auf einem Graphen sein...
Vor allem die Optimalitätsbedingungen werden deinen Algorithmus bestimmen. Soll z.B. die Summe der Beträge der Knotenwerte minimiert werden, wirst du vielleicht versuchen eine Art Mittelwert der Kantenwerte zu finden, um die Knotenwerte irgendwie möglichst um Null herum zu platzieren. Sollen es andererseits möglichst wenig verschiedene Werte sein, wirst du vielleicht versuchen, auch bei den Kantenwerten irgendwie "Gruppen" zu bilden.
Das ganze ist natürlich komplizierter... aber man sieht halt, daß der Algorithmus stark von den Vorgaben abhängt.

Was auf jeden Fall wichtig ist: Was genau ist fest vorgegeben? Die Knoten und die Verbindungen (also welcher Knoten mit welchem verbunden ist)? Ist denn wirklich jeder mit jedem verbunden? Die C_(i,j) sind auch vorgeben, ja? Das heißt du legst letzendlich nur noch die V_i für i=1,...,n fest?

Deine Frage war natürlich auch nicht "Wie löse ich dieses Problem", sondern "Wo finde ich Informationen", ich weiß... aber ich glaube nicht, daß man das Problem auf ein Standardproblem (z.B. kürzester Weg, Matching, Färbung oder Spannenden Baum finden...) zurückführen kann. Das ist doch sicher aus diesem Informatikwettbewerb, oder? Da werden die sich schon was sehr spezielles ausgedacht haben! ;)

[ethrandil]

Original geschrieben von DocEW Was auf jeden Fall wichtig ist: Was genau ist fest vorgegeben? Die Knoten und die Verbindungen (also welcher Knoten mit welchem verbunden ist)?
Ja
Ist denn wirklich jeder mit jedem verbunden?
Nein.
Die C_(i,j) sind auch vorgeben, ja? Das heißt du legst letzendlich nur noch die V_i für i=1,...,n fest?
Ja.

Das ist doch sicher aus diesem Informatikwettbewerb, oder? Da werden die sich schon was sehr spezielles ausgedacht haben! ;)
Ja, :P haben sie, desshalb frag ich ja auch nicht nach der Lösung ;-)

Naja, vielleicht findet ja noch jemand allgemeine Informationen ;-)

Achja, das ganze ist auch noch planar...

EDIT:
Alle Informationen, die ich finde haben immer nur Werte für die Kanten, nicht für die Knoten selber!

[Stone2001]

Interessante Aufgaben! Das muß man denen lassen, kreativ sind sie. ;)

Jetzt mal kurz was zu deinem Problem:
Das nur die Verbindungen gewichtet sind ist normal, mir fällt auch spontan kein Problem ein, bei dem die Knoten gewichtet sind und die Kanten nicht.

Und, ich bin mir gar nicht mal so sicher, ob dein Problem unter 'Algorithmische Graphentheorie' fällt. Ich würde es eher unter 'Optimierungsproblemen' einordnen. (So wie es aussieht, ist das Problem NP-Vollständig)

Aber wie wär es mit einem Brute-Force-Algorithmus? Probiere jede mögliche Kombination (an Knotengewicht) durch und nimm dann die beste Lösung heraus. (gegebenfalls vorher auf Korrektheit überprüfen)

[ethrandil]

Original geschrieben von Stone2001
wie wär es mit einem Brute-Force-Algorithmus? Probiere jede mögliche Kombination (an Knotengewicht) durch und nimm dann die beste Lösung heraus. (gegebenfalls vorher auf Korrektheit überprüfen)
Hmmm...
Möglich.
Allerdings müsste ich dazu erstmal die Menge der Möglichen Knotenwerte Festlegen, dann brute-force.
Dann das ganze mit der nächst schlechteren Knotenmenge ...

Wird auch schwierig und rechenaufwändig.

Kann gut sein, dass es ein Optimierungsproblem ist, informationen? ;-)

[Stone2001]

Original geschrieben von ethrandil
Kann gut sein, dass es ein Optimierungsproblem ist, informationen? ;-)
Zu was? Optimierungsproblemen?
Original geschrieben von ethrandil
Wird auch schwierig und rechenaufwändig.

hmm, das Problem liegt aufjeden Fall in NP! Wenn ich recht habe, wirst du keinen Polynomialen Algorithmus finden. ;)

[ethrandil]

Original geschrieben von Stone2001
hmm, das Problem liegt aufjeden Fall in NP! Wenn ich recht habe, wirst du keinen Polynomialen Algorithmus finden. ;)
Und einen näherungsweise perfekten?
;-)

EDIT: Ich hab da mal was gefunden

Ein lineares Optimierungsproblem besteht in der Aufgabe, das absolute Maximum oder Minimum einer linearen Funktion endlich vieler Variablen zu bestimmen. Diese Variablen unterliegen dabei endlich vielen Nebenbedingungen, welche die Gestalt linearer Gleichungen oder Ungleichungen besitzen.

passt ja ...

[Stone2001]

Durch Optimierung wirst du eine näherungsweise perfekte Lösung finden. Nur kann dir niemand garantieren, das du die beste Lösung findest und in welcher Zeit du eine Lösung findest, die unterhalb einer gewissen Fehlerschwelle liegt.

P.S.: Man kommt mit 4 Frequenzen aus! ;)

[DocEW]

Wegen linearer Optimierung:
Das wäre wohl der ziemliche Overkill! Da gibt es verschiedene Algorithmen, der bekannteste ist wohl der Simplex- bzw. der Netzwerksimplex. Die haben in der Praxis meist sogar polynomielle Laufzeit, sind aber nicht gerade trivial. Der Simplex ist sowieso kniffelig, da man schnell numerisch instabil wird, aber auch der Netzwerksimplex lässt sich wohl kaum unter 200 Zeilen machen (habe ich schonmal gemacht).

Insofern sind diese Ansätze zu allgemein. Würde zwar funktionieren, keine Frage, aber du solltest eher die Gegebenheiten dieses speziellen Problems ausnutzen, um zu einem speziellen Algorithmus zu kommen.

@Stone2001: Was meinst du mit 4 Frequenzen? War das eine andere Aufgabe (ich nehme nicht teil)?

[ethrandil]

Original geschrieben von Stone2001 P.S.: Man kommt mit 4 Frequenzen aus! ;)
Du und deine Landkartenfärbungsvermutung ;D [das musst du erstmal beweisen ;) ]

Außerdem muss ich dir da widersprechen.... Was wenn 5 Punkte so nah aneinanderliegen, dass sie untereinander alle unterschiedlich sein müssen? (also doch nicht immer planar ...)

@Doc
Da hat sich jemand wohl den Aufgabentext genauer angesehen ...

[Stone2001]

Original geschrieben von DocEW
@Stone2001: Was meinst du mit 4 Frequenzen? War das eine andere Aufgabe (ich nehme nicht teil)?
Ich nehme auch nicht teil! (Bin dafür zu alt)
Aber Eth wird wissen was gemeint ist. ;)

Du kannst dir ja auch mal die Aufgaben anschauen. Dadurch wurde mir klarer, was Eth eigentlich braucht.

[Stone2001]

Original geschrieben von ethrandil
Du und deine Landkartenfärbungsvermutung ;D [das musst du erstmal beweisen ;) ]
Landkartenfärbungsvermutung? ??? ;)
Original geschrieben von ethrandil
Außerdem muss ich dir da widersprechen.... Was wenn 5 Punkte so nah aneinanderliegen, dass sie untereinander alle unterschiedlich sein müssen?
OK, hast recht, ich vergas den Randfall zu berücksichtigen, dadurch bekomme ich keine 100% Abdeckung hin.

[ethrandil]

Also, ich hab mir mal die Mühe gemacht das ganze als Optimierungsproblem darzustellen:


Fn(x) = { wenn x = n => 0
{ wenn x != n => |x-n| + 1


Es gibt für jeden Knoten eine solche Funktion.
Dabei ist n der 'Wert' des Knotens und 'x' die 'Basisfrequenz'.
Unter einbehaltung der Differenz-Regeln (also z.B. n1 + 3 < n2) muss folgendes minimiert werden:
(Summe aller F(x)) + 1

Das ganzs dürfte schwer linear zu optimieren sein ;(

[Stone2001]

hmm, ich würde sagen, das die zu optimierende Funktion weit, weit komplexer ist!

[ethrandil]

Hmm, stimmt ;(

Summe aller F, bei denen n unterschiedlich ist + 1.

Aber immernoch zu schwer ;)

[peecee]

hat jemand einen Link zu der Aufgabenstellung ?

[ethrandil]

http://www.bwinf.de/aufgaben/runde2/aufgaben222.pdf

[ethrandil]

Hab einen ersten BruteForce-Algorithmus.
Laufzeit bei 9 Verbindungen und
7 Knoten: 100 ms
8 Knoten: 731 ms
9 Knoten: 5257 Knoten
10 Knoten: OutOfMemoryError

hmmmmmmmmmmmmm...
okay, optimierungswürdig ;-)

Leicht optimiert:
7 : 100
8 : 681
9 : 4496
10: 32516

;(

[zeckensack]

Original geschrieben von ethrandil
Hmm, stimmt ;(

Summe aller F, bei denen n unterschiedlich ist + 1.

Aber immernoch zu schwer ;) Hmmmm :grübel:
"Divide and conquer"?

[ethrandil]

Original geschrieben von zeckensack
"Divide and conquer"?

7 : 90ms
8 : 170ms
9 : 830ms
10: 5578ms

Durchaus eine Verbesserung ;)
Aber immernoch viel zu langsam.
Ich möchte mindestens 16 in akzeptabler Zeit schaffen, und das wird so nix.

Diese neuen Knoten (8-10) haben übrigens garkeine Verbindungen, d.h. ihr Wert ist beliebig.
Mein erster gedanklicher Ansatz war ohnehin 'unabhängige Gruppen' gesondert zu behandeln....
:grübel:

[ethrandil]

.Anmerkung:
Ist das ganze nicht eigentlich eine leicht modofizierte Knotenfärbung?

Das Problem einen Graphen zu färben zählt damit zu den schwersten NP-Problemen überhaupt.

;(

EDIT:

Habt ihr konkret Informationen zu folgenden Problemen:
T-Färbungsproblem
Mindestabstandsfärbungsproblem
?

[DocEW]

Es gibt zwei Zusammenhänge, die dir vielleicht helfen, obwohl sie eher theoretisch sind:

Um einen Graphen zu färben brauchst du mindestens so viele Farben, wie die größte Clique im Graphen groß ist. Eine Clique ist eine Menge von Knoten, die alle paarweise miteinander verbunden sind.

Andererseits brauchst du höchstens so viele Farben, wie der höchste Knotengrad in G ist. Der Knotengrad ist die Anzahl der von einem Knoten ausgehenden Kanten.

Ein einfacher Greedy-Algorithmus sollte also auf jeden Fall mit ( maximaler Knotengrad von G ) + 1 Farben zum Ziel gelangen und dabei ziemlich schnell sein, er muß ja nur alle Knoten durchgehen und eine noch gültige Farbe auswählen. Die Lösung ist dann allerdings nicht unbedingt optimal.

Ich habe mir die Aufgabe noch nicht durchgelesen, sorry... vielleicht geht ja aus den speziellen Umständen hervor, daß ein solcher Greedy-Algorithmus immer eine optimale Lösung liefert.

Hoffe das hilft dir ein bißchen weiter...

DocEW

P.S.: Um Divide and Conquer zu nutzen, mußt du gucken, ob das "Optimalitätsprinzip" gilt, also ob alle Teillösungen einer optimalen Lösung auch optimal sind.

Edit: Diese Sachen gelten alle für "normale" Färbungen, ich weiß nicht wie es sich mit den Mindestabstandsfärbungen usw. verhält. Dürfte aber ähnlich bzw. genauso funktionieren.

[ethrandil]

EDIT: Unfug

Naja, ich werde wohl einen suboptimalen algo nehemn, und den dann nachträglich optimieren.

[DocEW]

Na, hast du dein Programm fertig bekommen? Vorgestern war ja Abgabeschluß... Was übrigens lustig ist: Ich habe mich für die Bewertung der Lösungen beworben und bin auch genommen worden. Also: Vielleicht kriege ich ja deine Lösung vorgesetzt, hehe... =)

[ethrandil]

Nö, ich hab bei der 2. Runde nicht mehr mitgemacht.

Ich hab das Programm für das Problem fertig, aber kein zweites. und ich hatte keinen Bock mehr mir da Stress zu amchen.

Ich kann dir meins mal schicken dann kannst du es bewerten ;)

Ist dann aber ohne Doku.....

Ich benutze u.A. Tabu-Search ein interessantes, recht neues, Heuristisches Verfahren.

- Eth

[DocEW]

Ja cool, schick mal! Dann habe ich schonmal eine "Referenz" an der sich die anderen messen lassen müssen! :D

[ethrandil]

Original geschrieben von DocEW
Ja cool, schick mal! Dann habe ich schonmal eine "Referenz" an der sich die anderen messen lassen müssen! :D
Findest du nicht du bist den anderen gegenüber ein bisschen unfair? ;D;D

- Eth

[DocEW]

Öhhhmmmmm.... NÖ! :D
Würde mich echt interessieren, schick mir mal bitte (Mailadresse habe ich als PN geschickt).