Anordnung von verschiedenen Kreisen nach Vorgaben (Programm)?

Wissenschaft Mathematik
#1

Hallo zusammen
Ich habe für ein Projekt ca. 20 Namen von Orten, deren Beziehungen untereinander ich gerne graphisch darstellen würde.
Dabei habe ich aber nur die Werte 1 für „sicher in der Nähe“ und 0 für „unbekannt“.
D.h. man könnte die Namen als Kreise konstruieren, die sich bei einem Wert 1 tangieren oder schneiden müssen und bei einem Wert 0 nicht schneiden müssen (aber theoretisch können).

Könnte man so etwas mathematisch durch ein Programm lösen? Wie sollte man dabei vorgehen? Ich habe keine Ahnung von Mathematik oder Programmierung.

Besten Dank für eure Hilfe
Max

#2

Hi,

Ich habe für ein Projekt ca. 20 Namen von Orten, deren
Beziehungen untereinander ich gerne graphisch darstellen
würde.
Dabei habe ich aber nur die Werte 1 für „sicher in der Nähe“
und 0 für „unbekannt“.

Ok…

D.h. man könnte die Namen als Kreise konstruieren, die sich
bei einem Wert 1 tangieren oder schneiden müssen und bei einem
Wert 0 nicht schneiden müssen (aber theoretisch können).

Meinst du das so?: (1) = Ort 1 etc.

(1)(2) => =1 und (3) (4) = 0 ?

Könnte man so etwas mathematisch durch ein Programm lösen?

Joa, geht sicherlich.

Wie sollte man dabei vorgehen?

Kommt auf dein Programm darauf an. Du könntest z.b. eine Datenbank erstellen, wo die Eigenschaften der Orte gespeichert ist. Danach müsstest du nur eine Art algorithmische Reihenfolge der Anzeige definieren und die Größe der Kreise dann festlegen (wenn z.B. 12 Orte =1 sind zu einem bestimmten Ort, wird das ja unübersichtlich…). Wäre so ein „spontanes Gedankenspiel“ dazu.

Ich habe keine Ahnung von Mathematik oder Programmierung.

Dann rate Ich dir mit beidem anzufangen. Da dies aber dein Problem nicht löst gibt es verschiedene Varianten, die man auch mit ein bisschen „PC Gefühl“ und Geduld machen kann:

  • Paint oder andere Bildbearbeitungsprogramme => Kreise malen, Text einfügen = fertig
  • evtl. ein Blasen-Diagramm mit Excel/Openoffice Calc o.ä. => X-Y Koordinate für die Orte definieren und Kreisgröße bestimmen … mit ein bisschen einarbeiten könnte das auch gehen.
  • Zettel, Zirkel & Stift

Das wären so die Varianten, die mir einfallen würden.

Gruß,

Hanzo

#3

Moin, Max,

vielleicht lohnt es sich darüber nachzudenken, was die Darstellung vermitteln soll. Male Kreise, verbinde die Nachbarn mit Linien und lass den Rest weg - die Information, dass keiner weiß, wie benachbart 2 Orte sind, interessiert vernutlich keine Sau.

Dazu ein Programm zu suchen halte ich nicht für der Mühe wert. Es sei denn, in dem Modell steckten noch ein paar mehr Infos, die Du uns vorenthältst.

Gruß Ralf

#4

Hallo,

wenn das Problem tatsächlich so lautet, wie du geschrieben hast, ist die optimale Lösung immer, dass sich alle Städte im selben Punkt befinden. Man muss also sicher noch Zusatzbedingungen einführen (z.B. eine Mindestentfernung von Städten), damit das ganze Sinn ergibt.
Mir fällt kein Algorithmus ein, der das (modifizierte) Problem exakt in polynomieller Zeit lösen kann, allerdings kann man durch numerische Optimierung sicher gut vorankommen. Hier der Ansatz:
Betrachte die Positionen der Städte als Zufallsvariablen. Den 1en in der Abstandsmatrix kannst du für eine gegebene Anordnung der Städte Wahrscheinlichkeiten zuordnen. Sind die Städte nah beieinander, ergibt dieser Faktor eine große Wahrscheinlichkeit, andernfalls entsprechend niedriger. Je nachdem, wie genau „nah“ definiert ist, kann man diese Verteilung unterschiedlich gestalten, zum Beispiel als Normalverteilung der Entfernung.
Die Gesamtwahrscheinlichkeit einer Anordnung entspricht dann dem Produkt aller Faktoren. 0en spielen dabei keine Rolle, da diese keine Information tragen. Die Aufgabe ist dann, die Wahrscheinlichkeit zu maximieren - ein relativ häufiges Problem in der Numerik. Es gibt verschiedene Methoden, dieses Problem anzugehen, bspw. durch einen Gradientenabstieg. Ermittle den Gradienten der Wahrscheinlichkeit (Ableitung der Wahrscheinlichkeit nach den Stadtpositionen), z.B. mittels Zentraldifferenzen (verschiebe die Stadt leicht und berechne die Differenz der sich ergebenden Wahrscheinlichkeit). Der Gradient gibt dann die Richtung an, in der vermutlich das Maximum liegt. Um nicht zu sehr ins Detail zu gehen, würde ich dich hier an entsprechende Literatur verweisen (siehe Gradientenabstieg, Newton-Verfahren).
Wenn man von den ganzen Wahrscheinlichkeiten den Logarithmus bildet und das Ergebnis negiert (negative log space), bestünde die Aufgabe darin, die Summe der logarithmischen Faktoren zu minimieren (siehe Energieminimierung).
Insgesamt entspricht dieses Verfahren einem Maximum-Likelihood Ansatz. Man sucht die Anordnung der Städte, die am wahrscheinlichsten ist.

Nico

#5

Wahrscheinlich habe ich mir das zu einfach vorgestellt. Ich habe natürlich schon versucht das ganze irgendwie aufzuzeichnen, aber irgendwann stösst man an Grenzen, wenn dann plötzlich ein Ort nahe bei einem anderen sein soll, den man ganz woanders platziert hat. Deshalb dachte ich, es lasse sich irgendwie logisch errechnen, wo welcher Kreis hinkommt. Aber dafür sind meine Informationen wohl zu karg und zu ungenau. Dann bleib ich halt bei Zettel und Stift… Danke für die Mühe auf jeden Fall.

#6

Besten Dank für deine Antwort. Das klingt sehr interessant, auch wenn ich kaum die Hälfte davon verstehe. Angesichts meiner knappen Informationen ist es wohl schwierig und auch unnötig das ganze so detailliert zu machen. Wie oben erwähnt, habe ich es schon versucht das Ganze irgendwie aufzuzeichnen, aber das war nicht so von Erfolg gekrönt, und ich dachte lediglich, dass es vielleicht eine Möglichkeit gäbe, das Ganze logisch so anzuordnen, dass es dann stimmt. Aber das wäre dann ja auch nur tentativ (selbst wenn man eine Lösung für den Mindestabstand finden würde.)
Auf jeden Fall, Danke für deine Überlegungen.