 |
 |
 |
 |
 |
 |
Startseite » Forum » Minimaler Stammbaum mit mehreren "Akteuren"?
Minimaler Stammbaum mit mehreren "Akteuren"?
Universität / Fachhochschule
Graphentheorie
Tags: Computer, Graphentheorie, Netzwerk, Zeit
 
|
  |
|---|
|
Hallo Forum Ich sitze gerade an einem Problem fest, wo ich einfach nicht mehr weiter weiss. Idee: Man hat ein Computernetzwerk mit 5 Computern Knoten / Ecken). Dieses Netzwerk ist voll-vermascht, . jeder Computer hat mit jedem eine Verbindung Kante). Siehe dazu auch die beiden Anhänge (Matrix und Graph). Die Gewichtung der Verbindungen können als Kosten oder auch Zeit interpretiert werden. Umso tiefer, umso besser. Das Ziel ist nun, den Baum für einen gegebenen Startpunkt Computer) zu finden. Dabei soll die total benötigte Zeit am kleinsten sein! Einschränkung: es ist immer nur eine ausgehende Verbindung "gleichzeitig" erlaubt Beispiel könnte sein: eine Datei oder Nachricht soll vom Startpunk Computer A an alle anderen Computer versendet werden. Nun das Problem, warum der minimale Spannbaum nicht unbedingt optimal ist: In einem minimalen Spannbaum geht man von EINEM "Akteur" aus finde den Weg, womit der Postbote am schnellsten alle Briefkästen bedienen kann). Hier gibt es aber zeitabhängig mehrere Akteure! Hat . der Computer die Datei von Computer A erhalten, so wird er nach Zeiteinheiten selbst zu einem Akteur und kann die Datei weiterversenden. Vielleicht hat A die Datei aber zuerst an weitergegeben, so wird erst nach Zeiteinheiten zum Akteur, muss die Datei dafür sicher nicht mehr an weitergeben. Im dritten Anhang habe ich das ganze auch mal grafisch anhand der Zeitachse dargestellt (aber mit anderen Werten). Dabei ist das grosse eines Knoten die Zeit die der Knoten zur Abarbeitung seiner Kinder-Knoten benötigt. Ein kleines ist die Zeit/Kosten der Verbindung. Eine grosse Schwierigkeit ist, dass durch die volle Vermaschung jeder beliebige Baum möglich wäre und dass man zu Beginn somit noch keine vorgegebene Struktur Baum) hat. Ebenso kann es sein, dass sich durch das Hinzufügen eines weiteren Knoten die ganze "überliegende" Struktur wieder ändert. Beispiel: ist der Startpunkt. A wird hinzugefügt wird hinzugefügt Hier wird nun die Verbindung verwendet, obwohl der schnellste Weg (Distanz-mässig) wäre. ABER: Zeitlich gesehen: und sind total und sind total Fügt man nun noch hinzu (mögliche Wege): Der schnellste Weg wäre wiederum also Nun kann aber die restliche Struktur optimiert werden!! benötigt also ZE (Zeiteinheiten), um seine Kinderknoten zu bedienen. ist . total also . Obwohl einen Knoten dazugekommen ist, sind wir jetzt schneller fertig. Dafür musste aber die gesamte andere Struktur nochmals überprüft werden! Der Knoten könnte jetzt direkt bei angeschlossen werden, die Zeit würde sich dadurch aber trotzdem nur um eines erhöhen WEIL: Sobald er die Datei an übertragen hat, kann er sie an schicken. selbst benötigt also total nur hat bereits nach seine Arbeit fertig. Meine "Lösungsidee" bis jetzt war: Man hängt einen Knoten immer so an, dass sich die Gesamt-Zeit am wenigsten erhöht (probiert also alle "Anschlussmöglichkeiten" aus). Sind alle Punkte angeschlossen, so geht man für jeden Punkt nochmals durch und überprüft, ob man ihn an einem anderen Ort anschliessen könnte sodass die Gesamt-Zeit nicht zunimmt resp. sogar abnimmt. Dies funktioniert aber nur teilweise. Wäre bis jetzt die "oberste Struktur" gewesen, so könnte es sein, dass sich aufgrund der neu angeschlossenen Knoten plötzlich die Struktur ergibt, was in meinem "Algorithmus" oben nicht berücksichtigt ist. Ah ja: Durchrechnen aller Bäume fällt wohl aus: für einen bestimmten Startknoten gibt es bei 5 Knoten bereits Möglichkeiten (wenn ich richtig gerechnet habe :-) ) So, vielleicht hat hier jemand ein paar Tipps dazu :-) Bin sehr gespannt auf Antworten :-) Gruss lousek    Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
1066747
1066747