Gausi hat folgendes geschrieben :

@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.

So hab ich das auch gelöst. Brauchte dazu auch nur wenig meinen Code von der Paranuss3 aus dem Jahr 2008 ändern.

Aktzeptier ich gerne, wenn Boldar zugibt, dass sein Taschenrechner ihm das vorgesagt hat

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

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...

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,

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...

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

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

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

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    ausgeblendet

markieren

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.

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.

Da es diesmal scheinbar keine Meinungsverschiedenheiten gibt: Wann gibs denn die Lösung?
Ich möchte endlich mein neues Delphi-10 haben

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

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.

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.

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,

*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

Hidden hat folgendes geschrieben :

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,

Wie 2 getrennte netzte???

Danke für den Preis und das Gewinnspiel! Und herzlichen Glückwunsch an die anderen Gewinner.

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,