0 Daumen
359 Aufrufe

Aufgabe:

Betrachten Sie das dargestellte Schachbrett. Keine Figur außer dem
weißen Springer darf ziehen. Das Springerproblem besteht darin, zu beweisen,
ob mit dem weißen Springer auf a8 die schwarze Dame auf h1 geschlagen werden kann, wobei einige Felder von weißen Bauern blockiert werden und daher nicht vom Springer betreten werden dürfen. Wenn ja, soll die minimale Anzahl an dafür benötigten Springerzügen angegeben werden.


Problem/Ansatz:

1) Modellieren Sie dieses Problem mit Hilfe eines ungerichteten Graphen und geben Sie eine
Graphentheoretische Formulierung des Springerproblems an.


2)  Verwenden Sie einen geeigneten Algorithmus aus der Vorlesung zur Lösung des unten
dargestellten Springerproblems. Erklären Sie Ihre einzelnen Schritte bei der Anwendung
des Algorithmus.

blob.png

Avatar von
einen geeigneten Algorithmus aus der Vorlesung...

Und was für Algorithmen wurden denn vorgelesen?

Strong Components Algorithmus und Graph Scanning Algorithmus

schau Dir mal meinen Kommentar zu einer ähnlichen Frage an. Vielleicht hilft das weiter.

1 Antwort

0 Daumen

Naja, mal ganz ohne Computer-Algorithmen:

(1.) es ist leicht, einen Weg in 6 Zügen zu finden (durch Anschauen und ein wenig Probieren); dabei gibt es nicht bloß einen einzigen

(2.) einen Weg in 5 Zügen kann es nicht geben (warum nicht?)

(3.) ein Weg mit weniger als 5 Springer-Zügen kann nicht vom Startfeld a8 zum Zielfeld h1 führen (warum nicht?)

(4.) somit ist 6 die gesuchte minimale Anzahl von Zügen

Avatar von 3,9 k

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

2 Antworten
1 Antwort
Gefragt 24 Mär 2021 von Edanour
2 Antworten
Gefragt 8 Dez 2019 von Gast

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community