Aufgabe 4.4 - Begriff "isolated"

Moderator: Algorithmische Modellierung

Dreamdancer
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 17. Jul 2005 23:17
Wohnort: Frankfurt am Main

Aufgabe 4.4 - Begriff "isolated"

Beitrag von Dreamdancer »

Hallo,

ich habe eine Frage bzgl. der Datenreduktion. Was soll hier der Begriff isolated bedeuten? Intuitiv würde ich sagen, dass bedeuted, dass ein Bahnhof keine Zugverbindung zu einem anderen Bahnhof hat, bzw. eine Menge von Bahnhöfen, die zu einem Bahnhof reduziert worden sind. Aber mir fällt dazu echt kein Beispiel ein, weil ich in der Datenreduktion ja nur mehrere Komponenten durch eine Komponente ersetze, jedoch nichts rausschmeiße...
Außerdem widerspricht die Grafik auf S. 189 diesem Begriff nach meiner Denke, da ja hier alle Bahnhöfe mit mindestens einen anderen verbunden sind.

LG und vielen Dank im voraus

Dreamdancer
Mausschubser
Mausschubser
Beiträge: 67
Registriert: 17. Jul 2005 23:17
Wohnort: Frankfurt am Main

Re: Aufgabe 4.4 - Begriff "isolated"

Beitrag von Dreamdancer »

Oder ist das ein Fehler im Skript? Kann ich mir eigentlich nicht vorstellen.

tss
Neuling
Neuling
Beiträge: 8
Registriert: 9. Apr 2008 10:40

Re: Aufgabe 4.4 - Begriff "isolated"

Beitrag von tss »

Hi,
also auf der Grafik S. 189 rechts sind nach meinem Verständnis nicht alle Bahnhöfe mit einander verbunden. Man erkennt teilweise kleine schwarze Dreiecke zwischen den grauen. Die durch diese Dreiecke verbundenen Bahnhöfe sind nicht isoliert, alle anderen (die mit grauen Linien verbunden sind) sind isoliert. Die isolierten Bahnhöfe sind die, die nicht wegreduziert werden konnten und somit als "Wartungsstationen" o.ä. übrig bleiben. Die nicht isolierten müssen dann noch irgendwie isoliert werden, um das Problem vollständig zu lösen, also quasi das F' aus dem Hitting-Set-Problem zu komplettieren.

Was auf den Folien nicht so genau gesagt wurde: Wie war nochmal die Projektion Bahnhof -> Hitting-Set? Soweit ich es verstanden habe, ist ein Zug die Menge der Bahnhöfe und somit Element von S. F ist dann die Menge aller Bahnhöfe. F' wäre somit die Menge der isolierten Bahnhöfe. Damit wird doch ein Hitting-Set-Problem draus, oder habe ich was übersehen?

ymy
Erstie
Erstie
Beiträge: 21
Registriert: 15. Jan 2008 10:37

Re: Aufgabe 4.4 - Begriff "isolated"

Beitrag von ymy »

tss hat geschrieben:Wie war nochmal die Projektion Bahnhof -> Hitting-Set? Soweit ich es verstanden habe, ist ein Zug die Menge der Bahnhöfe und somit Element von S. F ist dann die Menge aller Bahnhöfe. F' wäre somit die Menge der isolierten Bahnhöfe. Damit wird doch ein Hitting-Set-Problem draus, oder habe ich was übersehen?
Genau, S = Züge und F = Bahnhöfe. F' ist aber nicht die Menge der isolierten Bahnhöfe, sondern die Stationen-"Minimalmenge", für die gilt, dass jeder Zug an mindestens einer dieser Stationen (in F') hält. Du schreibst ja selbst, dass F' noch durch nicht-isolierte Knoten ergänzt werden mus.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Aufgabe 4.4 - Begriff "isolated"

Beitrag von Prof. Karsten Weihe »

Dreamdancer hat geschrieben: ich habe eine Frage bzgl. der Datenreduktion. Was soll hier der Begriff isolated bedeuten? Intuitiv würde ich sagen, dass bedeuted, dass ein Bahnhof keine Zugverbindung zu einem anderen Bahnhof hat, bzw. eine Menge von Bahnhöfen, die zu einem Bahnhof reduziert worden sind. Aber mir fällt dazu echt kein Beispiel ein, weil ich in der Datenreduktion ja nur mehrere Komponenten durch eine Komponente ersetze, jedoch nichts rausschmeiße...

Sie schmeißen Züge 'raus, und Züge sind die Verbindungen zwischen Bahnhöfen. Wenn ein Bahnhof X isoliert ist, dann ist zugleich mit X ein (einziger) Zug übrig geblieben, dessen Zuglauf durch Elimination anderer Bahnhöfe auf X reduziert wurde.

Dreamdancer hat geschrieben: Außerdem widerspricht die Grafik auf S. 189 diesem Begriff nach meiner Denke, da ja hier alle Bahnhöfe mit mindestens einen anderen verbunden sind.
Die grauen kanten sind in beiden Graphiken das Schienennetz. In der linken Grphik besteht die Lösung aus sechs isolierten Knoten, die schwarzen Kanten sind die ICE-Verbindungen (also Teil des Inputs, nicht des Outputs der Datenreduktion). In der rechten Graphik hingegen gehören die schwarzen Kanten zur Reduktion. (Sorry, ist nicht so einfach, zwei so unterschiedliche Beispiele anschaulich zu machen...)

Gruß,

KW

Antworten

Zurück zu „Algorithmische Modellierung“