Effizienter Algorithmus < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Ich möchte mit dem Auto von A nach B fahren. Mein Tank fasst genügend Benzin, um n km zu fahren, und ich habe eine Karte, die alle Tankstellen auf der Strecke mit den Entfernungen dazwischen anzeigt. Ich möchte so selten wie möglich zum Tanken anhalten.
Entwerfe einen effizienten Alg., der mir angibt, welche tankstellen ich anfahren solle, und zeige, dass der Alg, eine minimale Lösung liefert. |
Hallo,
ich hab leider keine Ahnung, wie ich den Alg. entwerfen soll. Ich hoffe, es kann mir jemand einen Tipp geben, wie man da vorgeht bei der Aufstellung des Algorithmus. Ich komm allein nicht auf die Lösung....
Minimale Lösung bedeutet doch, dass so wenig Tankstellen wie möglich angefahren werden oder?
Viele Grüße, wetterfrosch
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:24 So 11.06.2006 | | Autor: | goeba |
Hi,
mir fiele dazu folgendes ein:
- zunächst mal prüfen, ob Strecken größer n dabei sind. Dann gibt es keine Lösung.
- dann nach aufeinanderfolgenden Strecken suchen, die zusammen größer als n sind. Hier muss die in der Mitte liegende Tankstelle angefahren werden
- dann selber weiterüberlegen ...
Viele Grüße,
Andreas
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:16 Mo 12.06.2006 | | Autor: | Frank05 |
> Ich möchte mit dem Auto von A nach B fahren. Mein Tank
> fasst genügend Benzin, um n km zu fahren, und ich habe eine
> Karte, die alle Tankstellen auf der Strecke mit den
> Entfernungen dazwischen anzeigt. Ich möchte so selten wie
> möglich zum Tanken anhalten.
> Entwerfe einen effizienten Alg., der mir angibt, welche
> tankstellen ich anfahren solle, und zeige, dass der Alg,
> eine minimale Lösung liefert.
> Hallo,
Hallo,
> ich hab leider keine Ahnung, wie ich den Alg. entwerfen
> soll. Ich hoffe, es kann mir jemand einen Tipp geben, wie
> man da vorgeht bei der Aufstellung des Algorithmus. Ich
> komm allein nicht auf die Lösung....
> Minimale Lösung bedeutet doch, dass so wenig Tankstellen
> wie möglich angefahren werden oder?
So verstehe ich das auch. "so selten wie möglich" scheint das einzige zu optimierende Kriterium zu sein.
Am besten versuchst du das ganze mal zu abstrahieren. Es soll eine Strecke von A nach B abgefahren werden und es können immer maximal n km gefahren werden. Alle Tankstellen auf der Strecke sind bekannt, was uns dazu führt die Strecke als linear aufzufassen.
Du hast also jetzt eine Strecke von 0 (=A) bis x (=B) abzudecken. Dabei darfst du zum Abdecken Stücke verwenden, die maximal n lang sind, aber immer bei einer Tankstelle oder bei B aufhören müssen. Um das zu vereinfachen seien A und B ab jetzt auch Tankstellen (in der Aufgabe steht ja nicht, dass du wenn du bei B ankommst noch Benzin für die Rückfahrt haben solltest  )
Jetzt lässt sich das Problem schon viel besser abstrahieren: Du hast eine geordnete Sequenz von k Integern (=Tankstellenpositionen auf der Strecke) und suchst eine Teilsequenz mit folgenden Eigenschaften:
- erste und letzte 'Tankstelle' müssen enthalten sein
- der Abstand zwischen zwei aufeinanderfolgenden Integern muss <= n sein
- die Länge der Teilsequenz (=Anzahl Tankstellen) soll minimal sein
Nun gibt es natürlich viele Möglichkeiten für solche Teilsequenzen. Ein Trivialalgorithmus wäre alle Teilsequenzen einzeln auf die Erfüllung dieser Eigenschaften zu testen und dann eine mit der geringsten Länge zu wählen.
Allerdings bin ich der Meinung, dass sich dieses Problem Greedy lösen lässt. Da ich aber schon lange nichts mehr in der Richtung gemacht habe fällt es mir gerade schwer die zugehörige Matroid-Struktur aufzustellen. Wenn jemand da eine Idee hat würde ich das auch gerne hier sehen 
Zur Idee: Wenn du bei A beginnst und 2 Tankstellen zur Auswahl hast, die innerhalb der ersten n km liegen, welchen Vorteil kannst du dir besorgen, indem du die näher liegende Tankstelle anfährst? Ich sehe da keinen Vorteil und dementsprechend würde ich immer die maximal mögliche Entfernung bis zur nächsten Tankstelle wählen.
PS: Sollte ich mich mit dem Greedy irren, dann ist DP ein gutes Stichwort, nicht zu verwechseln mit BP, da ich denke, dass es nicht erlaubt ist zusätzliche Tankstellen ins Spiel zu bringen
|
|
|
|
