Aufgabe 4.4 The Power of Data Reduction

Moderator: Algorithmische Modellierung

mister_tt
Kernelcompilierer
Kernelcompilierer
Beiträge: 502
Registriert: 29. Sep 2008 15:54

Aufgabe 4.4 The Power of Data Reduction

Beitrag von mister_tt » 27. Aug 2013 10:03

Moin zusammen,

ich bin gerade etwas skeptisch, was die Reduktionsregeln auf Folie 188 angeht. Betrachten wir mal folgendes Beispiel:

Code: Alles auswählen

A-_-_-_-_B- - - -C
A, B, C sind die Stationen. - bzw. _ zwei unterschiedliche Züge. Zug - fährt also von A nach B nach C und Zug _ fährt nur von A nach B. Nach der zweiten Reduktionsregel lässt sich das zusammenfassen zu (Zug _ kann gelöscht werden, da er überall hält, wo Zug - auch hält):

Code: Alles auswählen

A- - - -B- - - -C
Das kann wiederum nach der ersten Reduktionsregel zusammengefasst werden zu (alle Züge, die an Station A halten, halten auch an Station B; alle Züge, die an Station B halten, halten auch an Station C): Somit haben wir aber nicht das gewünschte Ergebnis. Denn das Ergebnis soll ja immer noch so viele Stationen beinhalten, dass alle Züge an mindestens einer der Stationen halten. Zug _ hält aber nicht an Station C.

Was übersehe ich?
Viele Grüße und danke
Simon

mister_tt
Kernelcompilierer
Kernelcompilierer
Beiträge: 502
Registriert: 29. Sep 2008 15:54

Re: Aufgabe 4.4 The Power of Data Reduction

Beitrag von mister_tt » 5. Sep 2013 18:00

Im ersten Schritt habe ich genau den falschen Zug rausgeschmissen. Es muss also so sein:

Code: Alles auswählen

A-_-_-_-_B- - - -C
Da Zug - überall hält, wo Zug _ hält, kann Zug - gelöscht werden:

Code: Alles auswählen

A _ _ _ _B       C
Da alle Züge, die an Station A halten, auch an Station B halten, kann A gelöscht werden: Weiter kann nicht vereinfacht werden, da an Station B Züge halten, die nicht an Station C halten (nämlich Zug _).

Ich hoffe, so stimmt es jetzt :-)

Antworten

Zurück zu „Algorithmische Modellierung“