Mathematisches Problem?

[Jan]

Ich bin in Mathe nie sehr gut gewesen. Nur das, was ich praktisch verwenden konnte, das habe ich richtig gut hinbekommen. Und nun rächt sich meine Unwissenheit. Vielleicht kann mir jemand auf die Sprünge helfen.

Ich versuche, das Problem möglichst eindeutig zu erläutern. Und hoffe, das funktioniert.

• Gegeben ist ein Punkt.
• Dieser Punkt kann Verbindungen zu anderen Punkten in zwei Richtungen aufbauen.
• In eine Richtung n Verbindungen. n ist immer 0 oder 1.
• Ist n = 1 gibt es am Ende der Verbindung zwei weitere Punkte, die miteinander verbunden sind. Alle drei ergeben dann sozusagen ein T, mit dem Ausgangspunkt am unteren Ende des Aufstriches und den beiden Punkten am Ende der Verbindung an den beiden Enden des Querstriches.
• In die andere Richtung m Verbindungen mit m >= 0. Diese Punkte sind direkt mit dem Ausgangspuntk verbunden, also sozusagen sternförmig.
• Jeder Punkt ist eindeutig bezeichnet.
• Es besteht die theoretische Möglichkeit, das die Verbindungen zweier Punkte sich in unbekannter Entfernung auf genau einem Punkt treffen.

Soweit alles noch klar?

Alle Punkte und Verbindungen sind in dbf gespeichert.

• Es gibt zwei dbf.
• In einer sind alle Punkte gespeichert. Also die Ausgangspunkte und auch die Punkte am anderen Ende einer Verbindung.
• In der anderen die exakt 2 Endpunkte der waagerechten T-Linie, die ja ebenfalls eine direkte Verbindung aufweisen.

• Ich benötige die kürzeste Verbindung zwischen zwei gewählten Punkten, mit Angabe aller Verbindungspunkte.
• Schön wäre es zusätzlich, alle möglichen Verbindungen darzustellen.

Ich habe mal eine einfache Variante skizziert. Gesucht würde hier die Verbindung zwischen den beiden roten Punkten. Natürlich ist das hier recht einfach, da ja immer nur die Verbindungspunkte auf der Verbindung zwischen den beiden roten Punkten dargestellt sind. Real haben natürlich mehr doer weniger alle Punkte weitere Verbindungen, in der Berechnung zwar überprüft werden müssten, aber letztendlich ohne Belang sind.

Gibt es für so eine Aufgabenstellung eine mathematische Lösung? Oder sonst eine?
Jan

[AUGE_OHR]

hi,

in deiner Skizze verstehe ich, links unten, nicht wieso 3 Punkte in der waagerechten Line liegen ... 2 Väter ?

Grundsätzlich sieht das ganze ja wie ein Baum aus ... also ein Treeview.
nun will ich es gar nicht als Treeview darstellen, ich denke mehr an die Parent / Child Verbindungen deren Class Methoden man vielleicht nutzen könnte ?

wenn ich mir deine Skizze ansehe, wie komme ich von einem roten Punkt zu anderen, dann müsste man vom Child zurück zum Parent bis man einen gemeinsamen Vorfahren findet ... was ganz am Anfang sein könnte.

wenn ich aber die Generation ( waagerechte Ebene ) als Info habe dann könnte man direkt die Generation von Vorfahren prüfen wer in Frage kommt.

[Jan]

Jimmy,

ganz so einfach ist das nicht. Es könnte auch umgekehrt sein, das die beiden Punkte über einen Weg nach unten miteinander verbunden sind. Das weiß ich aber vorher nie. Ich muß also nach allen Richtungen offen sein.

Es könnte von beiden Punkte auch weiter nach unten gehen, ohne das die sich da irgendwo treffen. Im Pronzip stehen die beiden Punkte, deren Verbindung ich suche, jeweils irgendwo mitten in einer Wolke. Und ich suche die Schnittpunkte der beiden Wolken.

Und wegen der drei statt zwei Punkte links unten: Es könnten auch 1 oder 10 sein. Das ist komplett variabel. Es könnten auch 0 sein, die drei Punkte links unten haben ja keine Verbindungen nach unten. Wie auch viele andere. Nur nach oben ist es relativ einfach: Keiner oder zwei. Was anderes geht da nicht.

Jan

[georg]

Hallo, Jan -


mein Sohn Raphael rief mir folgenden Begriff zu: Breitensuche

https://de.wikipedia.org/wiki/Breitensuche

Vielleicht schaust Du da mal rein.

[Lewi]

Dein geschildertes Problem ist ein Anwendungfall der "Graphentherorie". Die entsprechende Mathematik dürftest Du unter dem Stichwort "Minimum-Cost Flow Problem" im Internet finden. Ansonsten sollte diese Seite einen ersten Einstieg liefern: http://www.tinohempel.de/info/info/prolog/graphen.htm

Gruß, Olaf

[Jan]

Hallo Georg und Olaf,

vielen Dank für Eure Stichworte. Ich werde mal versuchen, die Themen jeweils irgendwie zu verstehen.

Jan

[Helmut]

ich würde wohl einfach logisch vorgehen:

Jeder Punkt hat einen Namen und jeder Punkt besitzt eine oder mehrere Wegbeschreibungen zu einem oder mehreren Zentralpunkten oder -Ebenen oder auch Wolken:
Die waagerechte Ebene hat Buschstaben, die senkrechte Zahlen, Verbundene Punkte sind durch ein Komma getrennt, Ebenen durch Semikolon
A1,2 wäre die höchste Zentralebene

Die Schreibweise wäre Pn(Weg)
z.B. PJ3(a1,2; b1;c1,2;d1;E1,2;F1;H3,1,2;I1;J3)
PF2(a1,2;b1;c5,6;E8,9;F2)

Man kann jetzt den Klammerinhalt von rechts lesen, bis der erste gemeinsame Punkt oder Punktverbund gefunden ist oder aber auch von links bis kein gemeinsamer Punkt oder Punktebene mehr gegeben ist und dann einen Schritt zurück.
Der Weg des roten lk Punktes zum rechten wäre dann:
J3;I1;H3;F1;E1,2;D1;C1,2;b1;C5,6;E8,9;F2

steht der Punkt im Raum könnte dies durch eine geignete Syntaxregel dargestellt werden oder über mehrere Wegbeschreibungen in verschiedene Richtungen. Packt man die verschiedenen Richtungen in ein Array bin ich ziemlich unbegrenzt.

Gäbe es auch einen Verbindung über eine untere Vernetzung, bräuchte ich auch eine Wegbeschreibung über die dortige Wegstrecke.

Hätten die Punkte gar keine direkte Verbindung hätte ich Wolken und würde dort Verbindungspunkte definieren.

Sind die Punkte intelligent, könnte ich sie auch ähnlich dem Internet organisieren.


Ich denke soweit kein Problem. Das Regelwerk beginnt erst richtig, wenn nachträglich neue Ebenen eingezogen werden usw. und natürlich on the fly im laufenden Betrieb ohne kompletten Neuaufbau und Abstürzen.

L G

Helmut

[UliTs]

Hallo Jan,

was ist draus geworden?

Uli

[Jan]

Hallo Uli,

bislang noch nichts. Ich muß das im Kopf noch ein wenig sacken und arbeiten lassen, das ist alles (für mich) nicht so trivial. Und dann geh ich vermutlich Donnerstag daran, mal testweise das alles in ein wenig Code zu packen.

Jan