MinMaxRouteFinder

MinMaxRouteFinder

Der MiniMax-Algorithmus ist besonders bekannt und anwendbar für die Berechnung des besten Zuges (optimaler Zug) in Spielen mit zwei Spielern, bei denen alle Informationen verfügbar sind.

Hier versuchen wir zu zeigen, wie MiniMax zur Lösung eines Routenfindungsproblems verwendet werden kann, indem ein Routenwähler (der Kunde/Passagier/Fahrpreis) die Route mit der Mindestentfernung auswählt und der andere (der Fahrer des Taxis) die Route wählt Wählen Sie alternativ die maximale Entfernungsstrecke vom Ziel oder Zielort aus (max., min.). Beispiel für die Entfernung von der Quelle zum Ziel

Die Dateneingabe in das System erfolgt dateibasiert. Die folgenden Daten werden in einer Datei namens „ourRoutes.txt“ gespeichert. ourRoutes.txt sieht so aus

Das erste, was ein Benutzer tun sollte, wenn er dieses Routenfindungsprogramm mit dem Min-Max-Algorithmus verwendet, ist, die Karte vorzubereiten. Das Format der Karte sollte dem oben genannten Format ähneln.

1. * Trennzeichen, trennt die untergeordneten Knoten (Pfad) von ihren übergeordneten Knoten
2. Jede Zahl (z. B. 1 oder 0), die nach dem Trennzeichen ~ erscheint, sagt uns, welcher Spieler nun an der Reihe ist, einen Pfad auszuwählen. (1 für Maximierer und 0 für Minimierer)
3. Wenn ein Knotenname durch ein * von einer Zahl getrennt wird, gibt die Zahl die Entfernung oder die Kosten des Pfades durch die genannten Knoten an.

Beispiel: Stadion_*_9: Dies bedeutet, dass das Stadion der letzte Weg zum Ziel ist und die Entfernung nach Saris über den Stadionweg 9 km beträgt.

Wenn der Benutzer das Programm ausführt, wird das „Formular“ des Routenfindungsprogramms angezeigt. Wählen Sie zunächst den Pfad der Datei aus, die den Zustandsraum enthält, und geben Sie den Zielort in das Textfeld ein. Die Schritte sind:

• Klicken Sie dann auf „…“, um den Dateispeicherort auszuwählen
• Geben Sie den Zielort in das dafür vorgesehene Textfeld ein.
• Klicken Sie auf die Schaltfläche „Los“ oder drücken Sie die Eingabe-/Eingabetaste, um das Programm auszuführen.

Das System führt automatisch die folgende Aufgabe aus:

1. Es prüft, ob die Datei, die den Statusraum enthält, im angegebenen Ordner vorhanden ist.
2. Wenn die Datei verfügbar ist/existiert, lesen Sie den Inhalt der Datei, speichern Sie ihn unter „Inhalt“ und tokenisieren Sie dann den Pfad mit dem Pfadnamen.
3. Nach der Tokenisierung wird der Inhalt in der Datenstruktur als Knoten, Nachfolger, MiniMax-Ebene bzw. Entfernung gespeichert.
4. Der Dateiinhalt wird als Strukturliste gespeichert.