Stadtmauer Tor Algorithmus

[rosima26]

Moin,
habe eine Aufgabe bei der ich absolut nicht weiss was gewollt ist. Ich brauche hier auch keine code-mäßige Hilfe sondern einfach wen, der den Knoten in meinem Kopf löst und vielleicht eine Ahnung hat was die hier von mir wollen. Bitte keine expliziten Lösungshilfen, aber ein paar Denkanstösse wären super. Danke

Im Mittelalter kommt ein Wanderer nachts bei dichtem Nebel an eine die Stadt vollständig umschließende Stadtmauer. Dort gibt es einen Weg, der linksherum an der Stadtmauer entlang verläuft, und einen Weg, der rechtsherum verläuft. Der Wanderer möchte möglichst schnell zum einzigen Stadttor kommen. Es ist aber unklar, welcher Weg der Richtige ist. Der Wanderer weiß, dass der Weg zum Stadttor nicht mehr zu schaffen ist, wenn er sich für die falsche Richtung entscheidet. Die Sicht ist so schlecht, dass man das Stadttor erst erkennen kann, wenn man direkt davor steht. Entwickeln Sie einen Algorithmus, der den Wanderer sicher zum Stadttor und zur direkt daneben liegenden Herberge führt! Der Wanderer kann seine Richtung beliebig oft wechseln.

a) Entwickeln Sie in Java eine Methode public int wandern(Tor tor) (in Klasse Wandern), die die Position des Stadttors als Ergebnis liefert und dem Wanderer eine Folge von Anweisungen auf der Konsole ausgibt, wie er entlang der Stadtmauer zu dem Stadttor kommen kann! Eine Anweisung hat die Form: "Gehe k Schritte nach links (bzw. rechts)!"(wobei k ∈ N). Die Methode soll weiterhin die Anzahl der benötigten Schritte auf der Konsole ausgeben. Diese Gesamtlänge des zu wandernden Weges in Schritten bis zum Stadttor soll in O(d) liegen, wobei d die Entfernung vom Ausgangspunkt zum Stadttor ist. Eine Methode private boolean gefunden(int position) (in Klasse Tor) kann als vorhanden angenommen und genutzt werden, um herauszufinden, ob der Wanderer das Stadttor beim Erreichen von Position position vorgefunden hat. Die Position, die man in einer Entfernung von k Schritten vom Ausgangspunkt auf dem rechten Weg erreicht, ist k; auf dem linken Weg entsprechend −k.

 

[mihe7]

habe eine Aufgabe bei der ich absolut nicht weiss was gewollt ist.

Hm... wir sehen ja auch nur die Aufgabenstellung und dort steht:

Entwickeln Sie einen Algorithmus

Entwickeln Sie in Java eine Methode public int wandern(Tor tor) (in Klasse Wandern),

Was die Aufgabe selbst betrifft: vielleicht mal aufzeichnen. Wichtig: Du weißt nicht, wo das Tor ist. Die Kunst besteht darin, dass das Ergebnis in O(d) liegen soll. Du kannst also nicht einfach links/rechts alternierend die Zahl der Schritte erhöhen, denn dann wäre das Ergebnis 1+2+3+4+...+d = (d² + d)/2, der Algorithmus läge also in O(d²).

 

[rosima26]

Danke, hab mir das mal mit so nem Baumdiagramm versucht aufzuzeichnen... Die Position von dem Tor muss ich aber ja schon angeben, das macht ja sonst garkeinen Sinn oder

 

[mihe7]

Die Position von dem Tor muss ich aber ja schon angeben, das macht ja sonst garkeinen Sinn oder

Wo? Was ich oben meinte ist, dass Du im Algorithmus die Position vorab nicht kennst.

 

[rosima26]

Achso ja. Das mit dem links/rechts alternierend hab ich mir auch gedacht. Aber das geht ja offensichtlich nicht. Fragt sich nur wie man das in linearer Komplexität durchführt...

 

[mihe7]

Wie sehen denn die Klassen aus? Gibts evtl. auch ein Bild zur Aufgabe?

 

[rosima26]

Das hier war ein Tipp, sonst garnichts : "Anders formuliert geht es darum eine beliebig große ganze Zahl zu finden wobei man fragen kann ob die aktuelle Position die gesuchte Zahl ist und sie um eins erhöhen oder reduzieren kann. Die Gesamtzahl der Erhöhungen und Reduzierungen soll dabei in einem linearen Verhältnis zur gesuchten Zahl stehen. "

 

[rosima26]

So habe ich mir das anfangs vorgestellt aber da wäre der Aufwand ja 2^n was ja völliger Unsinn wäre

 

[rosima26]

public class Tor {

    private int distanz;

    public Tor(int dist) {
        distanz = dist;
    }

    public boolean gefunden(int position) {
        return (position == distanz);
    }
}

 

[rosima26]

Schätze es geht schon darum bei jedem Schritt zu prüfen ob man am Stadttor ist oder nicht. Die Frage ist aber, erhöhe oder verringere ich dann wenn ich es nicht bin, ich weiss ja überhaupt nicht wo das Stadttor liegt und kann dementsprechend keine "Tendenz wo es hingehen soll" nutzen. Also eigentlich müsste dann ja ohnehin der gesamte Raum abgesucht werden. Nur verstehe ich nicht wie man das ohne extremen Aufwand bewerkstelligen soll.

Frage mich wie er denn wissen soll dass "er sich für den falschen Weg entscheidet" wenn er doch absolut keine Ahnung hat wo sich das Tor befindet.

 

[mihe7]

Also eigentlich müsste dann ja ohnehin der gesamte Raum abgesucht werden.

Höchstens bis zum Intervall [-d,d]

Wie ist in

wobei man fragen kann ob die aktuelle Position die gesuchte Zahl ist und sie um eins erhöhen oder reduzieren kann.

das "kann" am Ende zu verstehen?

 

[LimDul]

Mal als Idee, nehmen wir doch einfach die Konstante für O(d) mal als 10 an. Und fangen wir an nach links zu gehen.
Sollte das Tor aber direkt rechts sein, dürfen wir maximal 10 Schritte gehen um das Tor zu erreichen. Also gehen wir:
* 4 nach links
* 4 nach rechts
Jetzt stehen wir am Anfang, haben 8 Schritte verbraucht und wissen das Tor ist nicht in den ersten 4 Schritten links. Wir gehen jetzt aber nach rechts
Sollte es am 5 Schritt links sein, dürfen wir maximal 50 Schritte insgesamt verbrauchen um in O(d) zu bleiben. 8 haben wir bereits verbraucht, bleiben noch 42. Von diesen 42 brauchen wir 5, wenn wir wieder am Anfang sind um 5 nach links zu gehen. Ergo haben wir 37 Schritte zur Verfügung um nach nach Rechts zu gehen und wieder zum Anfang zurück zu kommen. Wir können also 18 nach rechts gehen und 18 zurück. Dann haben wir 2x4 + 2x18 = 44 Schritte verbraucht.
Im nächsten Step gehen wir wieder nach links. Wir müssen aber sicher sein, sollte das Tor am nächst möglichen Punkt rechts, den wir nicht erkundet haben, den in O(d) zu erreichen. Das sind 19 Schritte, die wir brauchen. Das heißen wir haben 190 Schritte insgesamt zur Verfügung die wir nutzen können, bis wir da sind. 44 haben wir verbraucht, 19 brauchen wir nach rechts, also 63 weg. 190-63 = 137. Wir können also 68 Schritte nach links gehen und dann wieder zurück. usw.

Die Zahlen (für unsere Konstante 10) wären also:
4 links
4 rechts, dann 18 rechts (=22)
18 links, dann 68 links (=84)

Entweder man formuliert das wirklich exakt so wie ich es gemacht habe als Algorithmus (man setzt die Konstante für O(d) fest und geht dann so lange in eine Richtung bis man umkehren muss, weil man sonst im Worst-Case die Bedingung für O(d) verletzt) Oder man versucht daraus eine mathematische Formel / Reihe herzuleiten und kann die ggf. per vollständiger Induktion beweisen.

 

[rosima26]

Das klingt irgendwie sinnvoll, werde das aber nicht als Algorithmus formulieren können...
Hab das jetzt mit sich alternierend erhöhenden Zahlen gemacht. Das ist zwar wie schon erwähnt wurde in O(d^2) aber dafür wenigstens verständlich für mich.

 

[mihe7]

Alternativer Vorschlag.

Berachten wir nochmal die alternierende Vorgehensweise, wobei die Schrittzahl um jeweils 1 erhöht wird:

   -   +
  432101234 
1      -     1r
2    --      2l
3     ---    3r
4   ----     4l
5    -----   5r
6  ------    6l
7   -------  7r
8 --------   8l

Hier decken wir neun Zahlen ab (-4 bis +4). Richten wir die Schritte bündig aus, erhalten wir

i (Iteration)
1 -          1r
2 --         2l
3 ---        3r
4 ----       4l
5 -----      5r
6 ------     6l
7 -------    7r
8 --------   8l

Um n Zahlen abzudecken, gehen wir also (n²-n)/2 Schritte. Das Problem ist, dass mit jeder Iteration genau eine Position hinzugewonnen wird, während die Zahl bereits betrachteter Positionen immer weiter zunimmt.

Was wäre denn, wenn wir die Schrittzahl beim Umkehren verdoppeln?

     -    +
   543210123
1        -   1r
2      --    2l
3       ---- 4r
4  --------  8l

Auch hier werden nun neun Zahlen (-5 bis +3) betrachtet. Bündig ausgerichtet:

i (Iteration)
1 -          1r
2 --         2l
3 ----       4r
4 ---------  8l

In Iteration i > 1 ist die Zahl der bereits besuchten Positionen genau so hoch wie die Zahl der neu hinzugekommenen. Die Gesamtzahl der Schritte nach i Iterationen beträgt 2^i-1 (z. B. Iteration 4 = 8+4+2+1=15=2^4-1). Zugleich wächst die Zahl der Iterationen aber nur logarithmisch, so dass man insgesamt eine Schrittzahl erreichen dürfte, die in einem linearen Verhältnis zu d steht. Nagelt mich hier aber nicht fest, bin gerade etwas "balla balla"