0 Daumen
163 Aufrufe

Aufgabe:

gegeben: 8 x 8 Schachbrett, indem die Zeilen bzw. Spalten mit 0, .. , n-1 nummeriert sind.

Es wird ein neuer Springer hinzugefügt, welcher drei Felder in eine Richtung, also horizontal oder vertikal, gefolgt von 1 Feld senkrecht dazu ziehen oder vise versa. 2 Felder sind durch einen Bogen (Gewicht = 4) verbunden, wenn diese durch diesen neuen Springer erreicht werden können. Es kommen Abstandfunktionen hinzu:

1. Summe vertikaler und horizontaler Abstand zum Zielknoten, die sogenannte Manhattan-Distanz multipliziert mit einem Faktor alpha1 >= 0.

2. Maximum vertikaler und horizontaler Abstand zum Zielknoten multipliziert mit einem Faktor alpha2 >= 0.


Problem/Ansatz:

1. Frage: Beide Fälle betrachten. Welche Werte sind für alpha1 und alpha2 möglich?

2. Frage: A* Algorithmus für Heuristik h = 0 (Dijkstra) + oben genannte Herusitiken mit den jeweiligen Max-Werten für alpha abgerundet. Der Springer startet auf Positionsfeld s = e7, Ziel hierbei ist das Feld t = a1. Bei allen Entscheidungen wähle immer kleineren Knoten, z.B. von c4 der Nachbarknoten a3 - auch wenn d(v) + h(v) für mehrere Knoten gleich sind und ein kleinerer Knoten zu einem späteren Zeitpunkt gefunden wurde. Man gebe die Knoten-Anzahl an, die zum Endzeitpunkt die Mengen S & Q enthalten.



Wie sieht der Lösungsweg zum Ergebnis aus?

Vielen Dank.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community