Meine letzte Optimierungs-Vorlesung ist schon eine Weile her, und ich weiß dabei ehrlich gesagt nicht weiter.

Folgendes Problem. Ich habe eine Menge von Punkten P = {p_1, ..., p_n} in der Ebene gegeben (z.B. im Einheitsquadrat). Diese Punktmenge induziert mir eine Graphenstruktur, d.h. zwei Punkte sind mit einer Kante verbunden, wenn ihr Abstand kleiner ist als eine gewisse Schranke (Stichwort: Unit-Disk-Graph).
Auf diesem Graphen lasse ich jetzt einen kürzeste-Wege-Algorithmus laufen, der mir zu jedem Punkt/Knoten die Länge des kürzesten Weges (= Anzahl der benötigten Kanten) zu allen anderen Knoten bestimmt. D.h. ich habe dann eine Kürzeste-Wege-Matrix KW, und der Wert KW(i, j) gibt mir die Länge des kürzesten Weges von p_i nach p_j an.

Aus dieser Matrix möchte ich nun möglichst gut auf die Koordinaten der Punkte schließen. Dabei reichen relative Koordinaten aus, d.h. das ganze System darf verschoben/gedreht/gespiegelt sein. D.h. ich suche eine Positionierung der Punkte, so dass die Summe

minimal wird. d(p_i, p_j) ist dabei der euklidische Abstand der beiden Punkte, also "Wurzel aus DeltaX^2 + DeltaY^2", Pythagoras eben. Also ein Minimierungsproblem. D.h. ich suche eine Verteilung der Punkte in der Ebene, so dass die Abstände der gesetzten Punkte möglichst gut den Abständen entsprechen, die mir durch die Graphenstruktur gegeben ist.

Frage an die Mathematiker: Wie löst man ein derartiges Minimierungsproblem? Wie lauten dafür die richtigen Stichworte? Wo kann ich mich über sowas schlau machen? Eine exakte Rekonstruktion ist nicht möglich (das dahinter liegende Entscheidungsproblem ist NP-vollständig), aber mir reicht eine Näherung, ggf. auch ein Verfahren, das nur eine "halbwegs vernünftige" Schätzung der Koordinaten liefert.

Wenns eine Komponente dafür gibt, sage ich natürlich auch nicht nein, aber bei torry finde ich dazu nichts.

Klingt entfernt nach OLSR und der ganzen Thematik, oder?
Ich weiß da jetzt nicht so viel, aber eventuell hat aus der Richtung schonmal wer sowas entwickelt?

Kurze Frage: sind alle Punkte irgendwie miteinander verbunden, also ergibt das genau einen Graphen, oder können die auch so weit auseinander liegen, dass Punkte/Teilgraphen frei stehen?
Oh, noch was: über welche Punkte die Wege gingen ist nicht bekannt, nur wie lang sie waren, richtig?

OLSR sagt mir erstmal nichts, aber wenn ich bei Wikipedia dazu schon im ersten Satz was von Ad-hoc-Netzen lese, dann muss ich sagen: Treffer, darum geht es. Zumindest kommt das dem Themengebiet recht nahe.
Allerdings kümmere ich mich nicht um dieses Routingverfahren, sondern um "geografisches Routen". D.h. das Ganze läuft nicht IP-basiert, sondern Koordinaten-basiert. D.h. Ein Teilnehmer im Netzwerk kann Anfragen stellen wie "Was ist denn da oben in der Ecke grade los?" Und dazu müssen die einzelnen Knoten erstmal wissen, wo sie selber sind, d.h. ein Knoten muss wissen, dass er "da oben in der Ecke ist", um entsprechend zu antworten. Und nein, GPS ist zu teuer, das geht nicht.

Prinzipiell kann man annehmen, dass der Graph zusammenhängend ist. Und wenn es der Lösung dient, könnte ich mir auch vorstellen, dass die Wege selbst auch bekannt sind - aber ich glaube nicht, dass das hilft, dieses Optimierungsproblem zu lösen.

Gausi hat folgendes geschrieben :

Und nein, GPS ist zu teuer, das geht nicht.

Schade *Antwort streich*

Gausi hat folgendes geschrieben :

Prinzipiell kann man annehmen, dass der Graph zusammenhängend ist. Und wenn es der Lösung dient, könnte ich mir auch vorstellen, dass die Wege selbst auch bekannt sind - aber ich glaube nicht, dass das hilft, dieses Optimierungsproblem zu lösen.

Ich denke doch: dann geht es ja nur noch darum, den Graphen so zu "entfalten", dass ungefähr das gleiche rauskommt. Ich würde aber fast sagen, dass man das nicht mal winkeltreu hinkriegen wird.

Ansonsten siehe dieses Video, Homepage dazu. Eventuell geht ja das, wenn man die Kräfte über die Distanz zu den direkten Nachbarn macht. "Signalstärke" quasi.

Hallo,

ich versuche mir gerade vorzustellen, wie man auf eine schlüssige ebene Anordnung kommen soll.
Man stelle sich eine Perlenschnur als Sinnbild vor.
Die Perlen haben den Abstand d. dist_krit/2 < d <= dist_krit , dass heisst das jede Perle mit genau zwei Nachbarn verbunden ist, ausser der ersten und der letzten.
Diese Perlenschnur kann ganz gerade liegen oder als ZickZack-Muster oder ähnlich einer archimedischen Spirale ( Tonband/Flachspule ) mit einem Abstand zwischen den Windungen derart, das dist_krit eingehalten wird.
Da kann man keine " Ecke" finden , in der was los ist.

Ich dachte zuerst daran, einen Punkt p_1 als Ursprung zu wählen und dessen direkt Nachbarn, haben ja einen Abstand < dist_krit.
Diese liegen nun auf jeweils einem Kreisring um p_1 mit Radius= Abstand.
Aus den Abständen , dieser Nachbarn untereinander müssten sich doch Anordnungen ableiten lassen, in welchem Winkelbereich auf dem Kreisring die Punkte liegen können.Dabei wird eine Verbindung p_1-p_Nachbar als y Achse festgelegt
Falls zwei von den direkten Nachbarn keine direkten Nachbarn sind, haben sie mindestens einen Abstand von dist_krit.

Wahrscheinlich ist es einfacher, drei Punkte zu finden, die jeweils direkte Nachbarn sind. Damit hat man ja ein eindeutiges Dreieck als Ausgangsbasis.

Ausserdem kann man ja herausfinden, welche Punkte über einen bestimmten Nachbarn erreicht werden, da deren
Abstand (p_1-p_x) = Abstand (p_1-p_direkterNachbar)+ Abstand (p_direkterNachbar-p_x)
Dieses p_x liegt auf einem Kreisring mit r = Abstand (p_x-p_direkterNachbar) um p_direkterNachbar, dessen Anteil innerhalb des Kreises mit r = dist_krit um p_1 nicht zulässig ist.Bei großen Abständen ist dies natürliche keine Einschränkung.
So erzeuge ich ständig Kreise um Punkte, mit Bereichen gültiger Positionen anderer Punkte oder im Dreicksfall eindeutigen Positionen.

Aber wie macht man das algorithmisch?

Gruß Horst

Da hier schon von der euklidischen Metrik gesprochen wurde gilt ja die Dreiecksungleichung?

Ich würde mich da Horst anschließen: Bei direkt zusammenhängenden 3er-Cliquen kann man die Position (bis auf Drehungen, Verschiebungen etc...) berechnen, wenn das nicht gegeben ist wird's schwierig, weil man die Positionen ja nicht mehr triangulieren kann.
Ist denn zumindest die feste Position von ein oder zwei Knoten bekannt?

Ich denke einmal, ein Knoten wird als Ausgangspunkt hergenommen werden und dient somit als "ursprung".

@Video: Ey, sowas hatte ich auch mal vor; nur halt 3D Vgl. meinen Thread damals; muss ich wohl mal weiter dran arbeiten ^^

Zum Problem: Hier könnten ggf. Kohonen-Netze für eine erste Annäherung helfen. Man lege die Punkte am Anfang beliebig und generiere dann einen Bewegungsvektor pro Knoten je nach Signalstärke\Abweichung.

Für TSP lässt sich mit Kohonen-Netzen bereits eine gute Annäherung finden; die Anpassung für OLSR dürfte aber möglich sein um die ungefähre Lage zu approximieren.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Was mir grade noch eingefallen ist... wie viele Knoten werden es denn, und wie sieht das Budget aus?

Wenn schon nicht jeder Knoten GPS kriegen kann... eventuell ein gewisser Anteil? Ein paar gleichmäßig verteilte Feste Punkte würden die Sache schon einfacher machen. Wäre zwar immer noch viel Spekulation drin, aber nicht mehr ganz so viel.

Dann könnte man einfach Broadcast-Anfragen wie weit die nächsten GPS-könnenden Knoten weg sind, und dazwischen was interpolieren.

Ein paar Fragen sind grad mal noch aufgetaucht:
Können sich die Knoten bewegen? Ansonsten kannst du die auch einmalig einmessen
Welche Größenordnungen muss man sich da vorstellen?
Haben die Knoten Rechenleistung, man könnte ja auch die Topologie zentral erfassen, berechnen und wieder verteilen...

Hey,

ich bin mir nicht sicher ob das überhaupt was bringt...
Betrachte mal folgende Kürzeste-Wege-Matrix:

Sieht er Graph dann so aus:



oder so?



(oder halt eine Drehung/Spiegelung davon... )

So, hat hier etwas gedauert, aber das Problem ist quasi gelöst. Das Paper, wodurch ich auf diese Aufgabe gekommen bin, war etwas verwirrend, aber ich hab mich durch weiterführende Literatur darüber schlau gemacht. Eine kurze Zusammenfassung gibts bei Wikipedia, der/ein Algorithmus zur Lösung schimpft sich SMACOF. Und wenn man den ganzen Matrix-Krempel erstmal implementiert hat, und den Fehler in seiner Matrix-Multiplikations-Funktion gefunden hat, funktioniert das auch ganz gut.

Jetzt muss ich das nur noch hinkriegen, dass das auch mit ein paar Tausend Knoten funktioniert - nur leider werden dann die Matrizen so unangenehm groß. Aber für ein paar Knoten (bis ca. 100) sieht die Berechnung dann fast so schön aus, wie in dem Video weiter oben .

Bei der Matrixmultiplikation kann man ja auch noch einiges rausholen, Stichwort Blocking

Nö, das Problem bei der Multiplikation bei mir waren elementare Fehler wie Spalten und Zeilen vertauscht. Das Ergebnis hatte dann eine etwas alternative Struktur und hat für Programmabstürze gesorgt.

Einen Faktor n habe ich schon rausbekommen: A*B*x, wenn A und B quadratisch sind und x sehr schmal, dann rechnet man besser A*(B*x) anstelle von (A*B)*x. So läuft das auch mit 1000 Knoten recht gut, und mehr als 10.000 sind eh eine schlechte Idee (10.000x10.000 = 100.000.000 Einträge, das mal 4 Bytes, sind mal eben 400MB. Davon dann ein paar Stück, und es gibt ein kleines RAM-Problem. )

Ja gut, da hilft dann nur noch loop unrolling, oder?

Wobei das natürlich an der asymptotischen Laufzeit bzw. Speicherbedarf auch nichts ändern kann...

Vielleicht hat D.E. Knuth ja bzgl. Matrixmultiplikation da paar Vorschläge. Zudem könntest Du das bilden der Matrizzen ggf. dadurch vermeiden, dass du die "on-the-fly" ableitest; du hast ja immerhin die Knoten sortiert da - wo keine Knoten verbunden sind, steht ja sicherlich ne 0

Außerdem gibt's ja sicherlich auch noch Algo's, mit denen du in O(n^(5^.5)) multiplizieren kannst. Glaube sogar ein wenig niedriger ...

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Ich weiß, dass die Vorschläge gut gemeint sind, aber das brauche ich nicht. Ich weiß, dass es Algorithmen gibt, die in O(N^2.3_irgendwas) zwei N x N-Matrizen multiplizieren. Aber ob sich die in der Praxis auch lohnen, oder ob das theoretische Konstrukte für Matrizen mit Drölfmilliarden Zeilen/Spalten sind, weiß ich dagegen nicht.
Das ist aber auch nicht das Nadelöhr, da ich bei der Iteration jetzt nur noch Multiplikationen von NxN mit Nx2-Matrizen habe.

Die Matrizen sind aber schon sehr dicht besetzt - ich arbeite da nicht mit den Adjazenzmatrizen des Graphen, sondern eher mit einer kürzesten-Wege-Matrix. Und um die anfangs zu berechnen, nehme ich auch einen einfachen Algorithmus mit kubischer Laufzeit, nicht den schönen.

Wenn einer was spielen will, dann kann er das Programm im Anhang mal ausprobieren. Einfach auf "Init Network" klicken, der Rest geht dann von alleine.

Ist ganz nett anzusehen, wie sich der Graph so entfaltet, und sich auch ab und zu mal "verknotet". Dann läuft der Minimierungs-Algorithmus in ein lokales Minimum, das nicht das globale ist.