Autor |
Beitrag |
Marc.
Beiträge: 1876
Erhaltene Danke: 129
Win 8.1, Xubuntu 15.10
|
Verfasst: Mo 14.12.09 18:59
|
|
Sylvus
Beiträge: 195
|
Verfasst: Mo 14.12.09 19:01
Aktzeptier ich gerne, wenn Boldar zugibt, dass sein Taschenrechner ihm das vorgesagt hat
|
|
chriscolm
Hält's aus hier
Beiträge: 5
|
Verfasst: Mo 14.12.09 19:01
Hallo,
also ich hatte mir da was viel einfacheres zu überlegt, auch wenn meine Lösung offenbar nicht die richtige war:
Wenn auch bei Ausfalls eines Sender immer jeder Sender jeden erreichen soll, dürfte es doch eigentlich genügen, wenn jeder Sender immer zwei andere erreicht? Fällt einer von beiden aus, ist die Verbindung über den anderen sicher gestellt. Ich habe die Entfernungen aller sender zueinander berechnet, dann für jeden Sender gezählt, ob mindestens zwei andere in der vorgegebenen Reichweite liegen. Dabei bin ich auf 75 wm gekommen (die exakte Lösung liegt zwischen 70 und 75)
Wo ist der Denkfehler? Ich möchte nicht ausschließen, dass ich beim Programmieren Mist gebaut habe, aber der Ansatz scheint mir so ganz verkehrt nicht zu sein.
Grüße
Christian
|
|
Sylvus
Beiträge: 195
|
Verfasst: Mo 14.12.09 19:04
Stell dir einfach zwei Wolken aus ganz vielen Punkten vor.
In jeder Wolke erreicht jeder Punkt jeden anderen, aber Wolke1 erreicht Wolke2 nicht, weil sie zu weit aus einander sind. Dann ist es für dich gelöst, aber der Weihnachtsmann kann trotzdem nichts von einer Wolke zur anderen schicken...
Im Beispiel waren es auch 2 Wolken, aber die eine Wolke bestand nur aus 3 Punkten...
|
|
Hidden
Beiträge: 2242
Erhaltene Danke: 55
Win10
VS Code, Delphi 2010 Prof.
|
Verfasst: Mo 14.12.09 19:09
Hi
Du kannst so nicht ausschließen, dass es nach dem Herausnehmen eines Einzelknotens zwei getrennte Netze gibt. Und genau das ist der Fall, die Ecke um NRW herum wäre nicht mit dem Rest von Deutschland verbunden(vlg. eine der vielen hochgeladenen visuellen Versionen).
mfG,
_________________ 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)
|
|
Martok
Beiträge: 3661
Erhaltene Danke: 604
Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
|
Verfasst: Mo 14.12.09 19:25
Niko S. hat folgendes geschrieben : | Und warum ist ein Wichtelmeter ca 1,5 Kilometer wenn doch die Wichtel (Vermutlich) kleiner sind? |
Das haben wir doch schon bei Otto gelernt: "Ganz altes Vorurteil!"
Kam jetzt etwas spät die Pointe, aber ist mir jetzt erst eingefallen...
_________________ "The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
|
|
Bruce
Beiträge: 80
|
Verfasst: Mo 14.12.09 19:31
chriscolm hat folgendes geschrieben : | Hallo,
also ich hatte mir da was viel einfacheres zu überlegt, auch wenn meine Lösung offenbar nicht die richtige war:
Wenn auch bei Ausfalls eines Sender immer jeder Sender jeden erreichen soll, dürfte es doch eigentlich genügen, wenn jeder Sender immer zwei andere erreicht? Fällt einer von beiden aus, ist die Verbindung über den anderen sicher gestellt. Ich habe die Entfernungen aller sender zueinander berechnet, dann für jeden Sender gezählt, ob mindestens zwei andere in der vorgegebenen Reichweite liegen. Dabei bin ich auf 75 wm gekommen (die exakte Lösung liegt zwischen 70 und 75)
Wo ist der Denkfehler? Ich möchte nicht ausschließen, dass ich beim Programmieren Mist gebaut habe, aber der Ansatz scheint mir so ganz verkehrt nicht zu sein.
Grüße
Christian |
Hallo Christian,
endlich mal einer, der auch so vorgegangen ist wie ich;)
Hab genau das gleiche gemacht und ab 71 hat jeder Sender mindestens 2 Partner.
Allerdings kam ich dann auch nur durch probieren weiter, weil von dem "richtigen" Lösungsweg hab ich keine
Ahnung und hab daher auch keinen anderen Ansatz gefunden, wie ich weitermachen soll;)
Hast Du Dir evtl. die Standorte gar nicht erst graphisch dargestellt? Die "gefährliche" Stelle ist dann nämlich
schon recht schnell auffällig und ich denke das war auch der gewollte Hinweis. Würde das nicht so ins Auge springen, hätte ich mich wohl auch vertan.
Im Anhang ist der Knackpunkt:
Wenn der Sender bei Nr. 1 ausfällt, dann sind die drei bei Nr. 2 mit 75 WM isoliert. Erst aber 83 wird der Punkt bei Nr. 3 erreicht und das Netzt ist wieder geschlossen.
Gruß,
Bruce
Einloggen, um Attachments anzusehen!
|
|
Chemiker
Beiträge: 194
Erhaltene Danke: 14
XP, Vista 32 Bit, Vista 64 Bit, Win 7 64 Bit
D7, BDS 2006, RAD Studio 2009+C++, Delphi XE2, XE3, VS 2010 Prof.
|
Verfasst: Mo 14.12.09 20:21
Hallo chriscolm,
viel ist es so noch etwas deutlicher. (siehe Anhang) Ich hatte zuerst den gleichen Ansatz wie Du und habe dann jede Linie nachgemessen mit dem PC. Ich muss leider zugeben, dass ich noch nie Grafik mit Delphi programmiert habe. Dabei musste ich feststellen, dass die Methode Canvas.MoveTo und Canvas-LineTo sich etwas merkwürdig verhalten, weil der Endpunkt nicht mehr zur Linie gehört.
Bis bald Chemiker
Einloggen, um Attachments anzusehen!
|
|
Bruce
Beiträge: 80
|
Verfasst: Mo 14.12.09 20:44
Chemiker,
ich gebe zu, bei Deiner Darstellung der
Isolation kommen echte Einsamkeits-Gefühle in mir hoch
Das haben die armen Westfalen aber auch nicht verdient
Trotzdem plädiere ich dafür, dass mir bis jetzt ein
Trostpreis zusteht für die hässlichste graphische Darstellung
des Problems (hab nämlich wie Du auch das erste mal mein
Canvas in Mitleidenschaft gezogen)
Und wenn sich jemand mit mir anlegen will dann gerne auch
im Bereich "Usability"... Da ist mein Programm so unterirdisch
zusammengefrickelt... es bedarf schon tiefer Nicht-Kentnisse,
um mich da zu toppen
Gruß,
Bruce
|
|
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 20:54
Da ich grade ne PN bekam mit der Frage nach Details, wie ich das algorithmisch lösen würde, poste ich das mal hier.
Ich würde die Graphen aufbauen, die man erhält, wenn die Sender eine Leistung von 50, 55, ..., 100 wm haben. Und dann bestimme ich die zweifachen Zusammenhangskompenenten, bzw. teste, ob der Graph selbst eine große tweifache Zusammenhangskomponente ist. Dafür ein Ausschnitt aus dem Skript zur Vorlesung Info3 von letztem Jahr an der HHU Düsseldorf.
Berechnung der zweifachen Zusammenhangskomponenten:
Die zweifachen Zusammenhangskomponenten eines Graphen sind nicht paarweise knotendisjunkt, aber kantendisjunkt. Daher spezifizieren wir eine zweifache Zusammenhangskomponente eindeutig durch ihre Kanten. Ein Knoten u ist ein Schnittpunkt bzw. Artikulationspunkt, wenn der Graph G ohne u mehr Zusammenhangskomponenten hat als G.
Zur Berechnung der zweifachen Zusammenhangskomponenten ermitteln wir die Schnittpunkte mit Hilfe der folgenden Überlegungen.
- Jede zweifache Zusammenhangskomponente befindet sich in genau einem Tiefensuchebaum.
- Beim Durchlaufen eines ungerichteten Graphens gibt es keine Querkanten.
- Trifft man während der Tiefensuche auf einen Schnittpunkt v, so muß sich mindestens eine Zusammenhangskomponente in einem Teilbaum mit Wurzel v des Tiefensuchebaumes befinden; aus einem solchen Teilbaum heraus gibt es keine Rückwärtskante zu einem Vorgänger von v.
- Wenn ein Schnittpunkt v Wurzel eines Tiefensuchebaumes ist, so hat v im Tiefensuchebaum mehr als einen Sohn, weil die Tiefensuche nur über v von einer Zusammenhangskomponente in die andere gelangen kann.
Quer-, Rückwärts-, Vorwärtskanten bezeichnen Kanten, die nicht zum Tiefensuchebaum gehören. Rückwärtskanten führen nach oben im selben Teilbaum, Querkanten führen in einen anderen Teilbaum, Vorwärtskanten führen weiter nach unten.
Wir merken uns in einer Variablen P[v] wie weit man über Rückwärtskanten höchstens im DFB-Index zurückgelangen kann. Ist P[v] ≥ DFB-Index[v], dann ist v ein Schnittpunkt.
Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24:
| Markiere alle Knoten als "unbesucht"; DFS-Beginnzähler=1; Initialisiere einen leeren Stack;
Für alle Knoten u aus V { Falls u als "unbesucht" markiert ist, dann 2ZSuche(u); }
2ZSuche(u) { Markiere u als "besucht"; DF-Index[u] = DF-Beginnzähler++; P[u] = DF-Index[u]; Betrachte alle mit u inzidenten Kanten {u, v} aus E { Lege {u, v} auf den Stack, falls noch nicht geschehen; Falls v als "unbesucht" markiert ist { Vater(v) = u; 2ZSuche(v); Falls P[v] >= DF-Index[u], dann nimm alle Kanten bis einschließlich {u, v} vom Stack und gebe sie als eine Komponente aus; P[u] = min(P[u], P[v]); } Sonst { Falls v <> Vater(u), dann P[u] = min(P[u], DF-Index[v]); } } } |
Damit kann man in Linearzeit testen, ob ein Graph zweifach zusammenhängend ist.
_________________ We are, we were and will not be.
|
|
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Mo 14.12.09 21:21
Ich dachte, du wolltest erklären und nicht verwirren
_________________ 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.
|
|
Boldar
Beiträge: 1555
Erhaltene Danke: 70
Win7 Enterprise 64bit, Win XP SP2
Turbo Delphi
|
Verfasst: Mo 14.12.09 21:30
|
|
Chemiker
Beiträge: 194
Erhaltene Danke: 14
XP, Vista 32 Bit, Vista 64 Bit, Win 7 64 Bit
D7, BDS 2006, RAD Studio 2009+C++, Delphi XE2, XE3, VS 2010 Prof.
|
Verfasst: Mo 14.12.09 21:34
Hallo BenBE,
ich finde Gausi sollte besser den fertigen Delphi – Code zur Verfügung stellen. Vor allen Dingen, für ältere Mitmenschen die sich vielleicht vor ca. 30 Jahren mit sowas beschäftigt haben.
Bis bald Chemiker
|
|
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 21:37
Nö, Code dafür hab ich auch nicht. Das mit Malen war effizienter, wenn man die Programmierzeit mit einrechnet. Wenn man nur die Graph-Struktur gegeben hätte, und nicht weiß, wie man den "schön" zeichnen soll damit man das "sieht", dann sähe das anders aus. Aber so soll die weiter oben gepostete Lösung reichen.
Ist halt ne Tiefensuche, bei der man sich ein paar Hilfswerte zusätzlich merkt.
_________________ We are, we were and will not be.
|
|
JungerIslaender
Beiträge: 427
Erhaltene Danke: 5
Win XP
Delphi 7; Delphi 2005
|
Verfasst: Mo 14.12.09 22:12
Hidden hat folgendes geschrieben : | JungerIslaender hat folgendes geschrieben : | 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. | Wenn ich nicht ziemlich absolut falsch liege, ist sie das Was können wir für dich tun? |
Also ich hab mir das ganze so vorgestellt: Das mit den koordinaten war mir klar. Also konnte ich mit excel eine grafik erstellen die mir alle Punkte anzeigt.
Zur Frage und Bedingungen: Kleinste mögliche Sendeleistung: "Er möchte daher den Elektrosmog möglichst gering halten"
Türme können mit anderen Türmen kommunizieren z.B. a mit b:a ---- b allerdings auch a mit c über b a ---- b ----- c : "Eine Kommunikation zwischen weit entfernten Stationen geschieht dann über Zwischenstationen."
Alle sender haben die gleiche Leistung: "Um den Elektrosmog gerecht zu verteilen, sollen alle Sender mit der gleichen Leistung senden."
"Da Funk nicht ganz so sicher ist wie ein Kabel, möchte der Weihnachtsmann gerne ein etwas dichteres Netz haben. Das heißt, auch wenn eine beliebige Funkstation ausfällt, soll immer noch jede Station mit jeder anderen verbunden sein (mit Ausnahme der kaputten, versteht sich.)": Das heißt also wenn wir folgende Situation haben:
a ---- b ---- c und b ausfällt muss die Sendereichweite ausreichen um von a nach c zu reichen.
Dann noch die entfernung vom punkt (1/1) zu (1/2) Beträgt 1 Wm und eine Turm mit der Reichweite 1WM müsste also reichen.
Das alles hab ich jetzt bei excel eingetippt und dann komme ich auf das ergebnis 65Wm und nicht 85. Also das Ganze sehr verwirrend für mich.
Vlt. hab ich mich auch verrechnet...?
Gerechnet habe ich wie folgt: Punkte aufgestellt und benannt. Punkt A von Punkt b abgezogen um den Vektor AB zu bekommen. Dann den Betrag des Vektors um die Länge zu bekommen. So habe ich jedwede Entfernung von jedem zu jedem Punkt berechnet.
Nach meiner Logik müsste es jetzt so sein: Da jedweder Punkt ausfallen könnte, muss jede zweitkleinste Entfernung verfügbar sein. D.h. Die größte Zweitkleinste Entfernung von einem Punkt zu einem anderen müsste das gesuchte Ergebnis sein.
Einloggen, um Attachments anzusehen!
|
|
Hidden
Beiträge: 2242
Erhaltene Danke: 55
Win10
VS Code, Delphi 2010 Prof.
|
Verfasst: Mo 14.12.09 22:16
Hi
JungerIslaender hat folgendes geschrieben : | Nach meiner Logik müsste es jetzt so sein: Da jedweder Punkt ausfallen könnte, muss jede zweitkleinste Entfernung verfügbar sein. D.h. Die größte Zweitkleinste Entfernung von einem Punkt zu einem anderen müsste das gesuchte Ergebnis sein. |
Das läuft auf den 2-Verbindungen-Ansatz heraus, oder? Da könnten es ja immer noch 2 getrennte Netze sein?
Grüße,
_________________ 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)
Zuletzt bearbeitet von Hidden am Mo 14.12.09 22:25, insgesamt 1-mal bearbeitet
|
|
jfheins
Beiträge: 918
Erhaltene Danke: 158
Win 10
VS 2013, VS2015
|
Verfasst: Mo 14.12.09 22:22
*auch eine Lösung hat*
Hier mein Programm - es ist vielleicht nicht das elegenteste, schnellste und ich habe auch keine 2-disk-sonstawas verwendet, aber es hat ne einigermaßen Grafik
Algo ist relativ einfach: Jeder Knoten wird weggenommen, dann wird duch Tiefensuche festgestellt ob der Graph noch zusammenhängend ist. Wenn nicht, reicht die Reichweite nicht. Wenn man aber jeden Knoten entfernen kann, ohne dass der Graph auseinander fällt, dann ist die Reichweite OK.
Laufzeit ist unter 1 Sekunde
Einloggen, um Attachments anzusehen!
|
|
JungerIslaender
Beiträge: 427
Erhaltene Danke: 5
Win XP
Delphi 7; Delphi 2005
|
Verfasst: Mo 14.12.09 23:56
|
|
elundril
Beiträge: 3747
Erhaltene Danke: 123
Windows Vista, Ubuntu
Delphi 7 PE "Codename: Aurora", Eclipse Ganymede
|
Verfasst: Di 15.12.09 00:04
Danke für den Preis und das Gewinnspiel! Und herzlichen Glückwunsch an die anderen Gewinner.
_________________ This Signature-Space is intentionally left blank.
Bei Beschwerden, bitte den Beschwerdebutton (gekennzeichnet mit PN) verwenden.
|
|
Hidden
Beiträge: 2242
Erhaltene Danke: 55
Win10
VS Code, Delphi 2010 Prof.
|
Verfasst: Di 15.12.09 00:07
Hi
Chemiker hat ja eben schon das hier hochgeladen. Erfüllt dieses Netz(entscheidende Verbindung ist schon gekappt, siehst du wenn du mal die Lösungen durchgehst) nicht noch dein Kriterium?
mfG,
_________________ 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)
|
|
|