Irrgarten-Ungleichung

Neue Frage »

Finn_ Auf diesen Beitrag antworten »
Irrgarten-Ungleichung
Gegeben ist der folgende Raum:


Man zeige, dass die Punkte (2|2) und (12|13) durch einen zusammenhängenden Weg verbunden sind. Wie lang ist der kürzeste Weg zwischen diesen beiden Punkten?
HAL 9000 Auf diesen Beitrag antworten »

Sieht auf alle Fälle interessant aus: Die folgende Abbildung zeigt mit rot markierten Start- und Zielpunkt:

[attach]49089[/attach]

Zitat:
Original von Finn_
Man zeige, dass die Punkte (2|2) und (12|13) durch einen zusammenhängenden Weg verbunden sind.

Das mag vielleicht noch angehen.

Zitat:
Original von Finn_
Wie lang ist der kürzeste Weg zwischen diesen beiden Punkten?

Ist nicht dein Ernst? Augenzwinkern
Leopold Auf diesen Beitrag antworten »

[attach]49093[/attach]
HAL 9000 Auf diesen Beitrag antworten »

Damit können wir ja a) abhaken. Fehlt nur noch der kürzeste Weg zu b) und der Beweis, dass der auch wirklich diese Eigenschaft hat. Augenzwinkern
Leopold Auf diesen Beitrag antworten »

Am besten fragen wir Theseus und Ariadne. Die haben Erfahrung bei solchen Problemen.
HAL 9000 Auf diesen Beitrag antworten »

Eigentlich ja gar nicht so schwer: Erstmal einen Weg mit den "topologisch richtigen" Gängen finden (womöglich ist das ja schon dein oberer Weg) und dann den Ariadne-Faden straff ziehen. Augenzwinkern
 
 
Leopold Auf diesen Beitrag antworten »

Eine alternative Methode geht nach Alexander. Dem war die Knotentheorie auch egal. Einfach mittendurch eine Bresche schlagen:
HAL 9000 Auf diesen Beitrag antworten »

Stimmt - da die Aufgabe in der Rätselrubrik steht, ist das wohl gemäß Formulierung

Zitat:
Original von Finn_
Wie lang ist der kürzeste Weg innerhalb M zwischen diesen beiden Punkten?

die richtige Rätsellösung. Freude
HAL 9000 Auf diesen Beitrag antworten »

Da die Interessenten hier nicht gerade die Bude einrennen, kann ja mal Rätsel-Autor (bzw. zumindest -poster) Finn_ was zum Thema sagen? Wink
Finn_ Auf diesen Beitrag antworten »

Na dann. Zur numerischen Behandlung des Problems erscheint mir das folgende Verfahren als zielführend:
  1. Das Problem ausreichend fein diskretisieren und den näherungsweise kürzesten Weg mit dem A*-Algorithmus finden.
  2. Den Polygonzug nun verfeinern und anschließend straff ziehen.

Für die Wohlfahrt hab ich angefangen ein neues Tool »Pfadfinder« zu implementieren, das allgemein wahrheitswertige constraints verarbeiten kann.

Das diskrete Gitter ist in den Startpunkt eingehakt. Meine Implementation von A* scheint zu funktionieren, spuckt bei einer Maschenbreite von 0,02 den richtigen Weg nach etwa 95000 Schritten aus:

[attach]49131[/attach]
Finn_ Auf diesen Beitrag antworten »

Die Länge des kürzesten Weges zwischen (2|2) und (12|13) beträgt etwa 19,94.

Zum straff ziehen eignet sich die iterierte Anwendung des gleitenden Mittelwertes, solange bis nichts mehr geht.
Finn_ Auf diesen Beitrag antworten »

Das Tool »Pfadfinder«:
Pfadfinder

Anwendung von Pfadfinder auf den Irrgarten (Vorsicht, benötigt etwas Berechnungszeit):
Irrgarten
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »