Autor |
Beitrag |
Gausi
Beiträge: 8538
Erhaltene Danke: 475
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Sa 12.12.09 15:39
Da es hierzu ja noch gar keinen Hinweis gab, kommt jetzt ein etwas deutlicherer dazu.
Auch wenn sich hinter dieser Aufgabe ein Standard-Problem aus der Graphentheorie verbirgt, so kann man diese Aufgabe auch einfach durch "Malen" lösen - also Punkte für die Sender und Linien zwischen zwei Punkten, wenn diese nahe genug beieinander liegen.
Das könnte dann so ähnlich aussehen:
Das linke Bild zeigt dabei eine Sendeleistung, die nicht ausreicht: Wenn der Sender in der Mitte ausfällt, können die drei auf der linken Seite nicht mehr mit den dreien auf der rechten Seite kommunizieren. Erhöht man die Reichweite der Sender, dann wird das Netz dichter, und bei Ausfall eines Senders gibt es noch eine Ersatzroute.
Einloggen, um Attachments anzusehen!
_________________ We are, we were and will not be.
Zuletzt bearbeitet von Gausi am Mo 14.12.09 09:00, insgesamt 1-mal bearbeitet
|
|
Gausi
Beiträge: 8538
Erhaltene Danke: 475
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Mo 14.12.09 09:00
So, dann wollen wir das mal auflösen. Die richtige Antwort ist: 85 wm.
Man kann diese Aufgabe durch malen und scharf hingucken lösen. Eine Online-Lösung dazu hat Christian S. schon in der Shoutbox vorgestellt, eine für Delphi ist im Anhang.
Wenn die Sendeleistung bei 80wm liegt, dann gibt es in der Ecke "NRW/Niedersachsen" einen Zipfel, der von dem Rest des Netzes bei Ausfall eines Knotens getrennt werden kann. Bei 83wm kommt an dieser Stelle eine Ausweichroute hinzu.
Wenn man das algorithmisch lösen möchte, dann ist der Begriff "zweifacher Zusammenhang" eines Graphen interessant. Dieser lässt sich effizient mit einer Tiefensuche berechnen. Man müsste dann für die einzelnen Sendeleitungen den so genannten Unit-Disk-Graphen mit dem passenden Radius aufbauen und diesen auf zweifachen Zusammenhang testen. Diese Unit-Disk-Graphen spielen bei der Modellierung von mobilen Adhoc-Netzen eine große Rolle, zum Beispiel im Gebiet "Sensornetze" oder auch bei der "Fahrzeug-zu-Fahrzeug-Kommunikation".
Einloggen, um Attachments anzusehen!
_________________ We are, we were and will not be.
|
|
Flamefire
Beiträge: 1207
Erhaltene Danke: 31
Win 10
Delphi 2009 Pro, C++ (Visual Studio)
|
Verfasst: Mo 14.12.09 10:14
Ich habe zum Lösen minimale Spannbäume des Graphen berechnet und nacheinander je einen Knoten rausgenommen.
Von dann ist die Entfernung die längste Kante aller minimalen Spannbäume.
Als Grund-implementierung hab ich mir dazu den Code von narses zu WLAN-Kabeln letztes Jahr kopiert
War dann schon fast zu einfach
|
|
Gausi
Beiträge: 8538
Erhaltene Danke: 475
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Mo 14.12.09 10:34
Könntest du das mit den minimalen Spannbäumen mal genauer erläutern? Was ein minimaler Spannbaum ist, ist mir klar, aber wie kann man den für die Aufgabe hier verwenden?
_________________ We are, we were and will not be.
|
|
Niko S.
Beiträge: 566
Erhaltene Danke: 10
Win 7, Ubuntu
Lazarus, Turbo Delphi, Delphu 7 PE
|
Verfasst: Mo 14.12.09 12:22
Eine Frage bleibt noch aus ...
Warum braucht der Weihnachtsmann in Deutschland ein Netzwerk?
Und warum ist ein Wichtelmeter ca 1,5 Kilometer wenn doch die Wichtel (Vermutlich) kleiner sind?
|
|
elundril
Beiträge: 3747
Erhaltene Danke: 123
Windows Vista, Ubuntu
Delphi 7 PE "Codename: Aurora", Eclipse Ganymede
|
Verfasst: Mo 14.12.09 12:39
_________________ This Signature-Space is intentionally left blank.
Bei Beschwerden, bitte den Beschwerdebutton (gekennzeichnet mit PN) verwenden.
|
|
Boldar
Beiträge: 1555
Erhaltene Danke: 70
Win7 Enterprise 64bit, Win XP SP2
Turbo Delphi
|
Verfasst: Mo 14.12.09 12:41
Weil die Wichtel 1.5 Km an einem Tag gehen können
Ich habe erst eine Algorithmische Lösung versucht, Hatte den Graphen auch schon in einer Adjazenzmatrix, bin dann aber an der Tiefensuche gescheitert.
Dann hab ichs einfach durch malen gelöst...
|
|
Hidden
Beiträge: 2242
Erhaltene Danke: 55
Win10
VS Code, Delphi 2010 Prof.
|
Verfasst: Mo 14.12.09 15:26
hi
Lösungen werden gerne getestet
E: Setzen weiterer Punkte entweder per Mausklick oder manuell, Ändern der Reichweite per Scrollrad.
PS: Ich sehe gerade, mit Gausis Programm sind es eigentlich genau genommen 83WM Sollte ich mit meinen 84 einem Rundungsfehler unterliegen?
Einloggen, um Attachments anzusehen!
_________________ Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)
|
|
JungerIslaender
Beiträge: 427
Erhaltene Danke: 5
Win XP
Delphi 7; Delphi 2005
|
Verfasst: Mo 14.12.09 15:28
Sagt mal, ist das hier die Lösung vom Adventsgewinnspiel 2009 - 2. Gewinnspiel?? Weil wenn ja herrscht da ech Erklär Bedarf für mich.
|
|
Hidden
Beiträge: 2242
Erhaltene Danke: 55
Win10
VS Code, Delphi 2010 Prof.
|
Verfasst: Mo 14.12.09 15:45
_________________ Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)
|
|
Flamefire
Beiträge: 1207
Erhaltene Danke: 31
Win 10
Delphi 2009 Pro, C++ (Visual Studio)
|
Verfasst: Mo 14.12.09 16:05
@Hidden: Ja du hast da einen Fehler. Genau wären es 82.73 wm
@Gausi:
Ok, ein minimaler Spannbaum verbindet alle Punkte eines Graphen und achtet dabei darauf, dass die Verbindungen so kurz wie möglich sind.
Also wenn ich einen minimalen Spannbaum zu dem Graphen finden kann, dessen längste Kante <= der Rechweite ist, sind alle Stationen damit erreichbar.
Rest ist nur noch "probieren":
1. Knoten fällt aus, welche Reichweite brauche ich? -->Minimaler Spannbaum, längste Seite wählen
2. Knoten fällt aus. Das gleiche nochmal.
So dann man der Reihe nach jeweils einen Knoten ausblenden und von allen längsten Seiten des MSB die längste nehmen, um sicherzustellen, dass mit dieser Reichweite in jedem möglichen Graphen, bei dem 1 Knoten fehlt, ein MSB mit Kantenlänge <= dieser Länge existiert.
Das ganze dann noch grafisch kontrolliert, in dem ich mir alle Kanten mit länge >80wm rot anzeigen lassen hab, und damit das Problem bei einer Reichweite von nur 80wm direkt sehen konnte.
Mein erster Ansatz war aber auch, einen Slider o.ä. zu nehmen und einfach "zu gucken"
|
|
spawn89
Beiträge: 82
Erhaltene Danke: 6
Linux
CodeTyphon
|
Verfasst: Mo 14.12.09 16:07
Einloggen, um Attachments anzusehen!
Zuletzt bearbeitet von spawn89 am Mo 14.12.09 16:09, insgesamt 1-mal bearbeitet
|
|
Gausi
Beiträge: 8538
Erhaltene Danke: 475
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Mo 14.12.09 16:08
@Hidden: Nein, dein Programm liefert doch auch 83. Nur über das Scrollrad kommst du nur in Zweierschritten an die Lösung ran. Bei einer Direkteingabe der 83 oben in das Edit kommt auch schon die fehlende Verbindung.
@Spannbäume: Ah, ok. Mit dem Spannbaum bekommst du die Reichweite, die man für einfachen Zusammenhang braucht. Und wenn du jeden Knoten je einmal rausnimmst und für diesen Graphen den Zusammenhang über den MST herstellst und dir dabei das Maximum der benötigten Reichweiten merkst, kommst du dahin. Ok, Algorithmus verstanden.
_________________ We are, we were and will not be.
Zuletzt bearbeitet von Gausi am Mo 14.12.09 16:13, insgesamt 1-mal bearbeitet
|
|
Boldar
Beiträge: 1555
Erhaltene Danke: 70
Win7 Enterprise 64bit, Win XP SP2
Turbo Delphi
|
Verfasst: Mo 14.12.09 16:13
Das ist meine Lösung, da ist auch noch ein Ansatz für die "Richtige" Lösung drin, aber da bin ich an der Tiefensuche gescheitert.
Einloggen, um Attachments anzusehen!
|
|
Hidden
Beiträge: 2242
Erhaltene Danke: 55
Win10
VS Code, Delphi 2010 Prof.
|
Verfasst: Mo 14.12.09 16:32
Gausi hat folgendes geschrieben : | @Hidden: Nein, dein Programm liefert doch auch 83. Nur über das Scrollrad kommst du nur in Zweierschritten an die Lösung ran. Bei einer Direkteingabe der 83 oben in das Edit kommt auch schon die fehlende Verbindung. |
Oh Ich war mir so totsicher dass ich's garnicht mehr ausprobiert habe vor dem Posten^^
_________________ Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)
|
|
Sylvus
Beiträge: 195
|
Verfasst: Mo 14.12.09 17:23
habs auch richtig
82,7 sind mindestens nötig
Danke für die Rätsel!
|
|
Flamefire
Beiträge: 1207
Erhaltene Danke: 31
Win 10
Delphi 2009 Pro, C++ (Visual Studio)
|
Verfasst: Mo 14.12.09 17:48
|
|
Sylvus
Beiträge: 195
|
Verfasst: Mo 14.12.09 18:25
als wenn wir jetzt so anfangen reicht deins aber auch nicht
es müssen schon 82,74 oder besser:
82,734515167492218767139425743058 wm sein!
|
|
Kha
Beiträge: 3803
Erhaltene Danke: 176
Arch Linux
Python, C, C++ (vim)
|
Verfasst: Mo 14.12.09 18:49
Können wir uns einfach auf √6845 einigen ?
_________________ >λ=
|
|
Boldar
Beiträge: 1555
Erhaltene Danke: 70
Win7 Enterprise 64bit, Win XP SP2
Turbo Delphi
|
Verfasst: Mo 14.12.09 18:52
Besser 37√5
Das ist schöner!
Teilweises radizieren FTW!!
|
|