MinMaxRouteFinder

MinMaxRouteFinder

L'algorithme MiniMax est particulièrement connu et applicable pour calculer le meilleur coup (coup optimal) dans les jeux à deux joueurs où toutes les informations sont disponibles.

Ici, nous allons essayer de montrer comment MiniMax peut être utilisé pour résoudre un problème de recherche d'itinéraire, en faisant en sorte qu'un sélecteur d'itinéraire (le client/passager/tarif) sélectionne l'itinéraire à distance minimale et l'autre (le chauffeur du taxi) pour sélectionnez alternativement l'itinéraire à distance maximale depuis l'objectif ou le lieu de destination (max, min). Exemple de distance de la source à la destination

Les données saisies dans le système sont basées sur des fichiers. Les données suivantes sont stockées dans un fichier appelé « ourRoutes.txt ». ourRoutes.txt ressemble à ceci

La première chose qu'un utilisateur doit faire lorsqu'il utilise ce programme de recherche d'itinéraire utilisant l'algorithme Min-Max est de préparer la carte, le format de la carte doit être similaire au format ci-dessus.

1. * séparateur, sépare les nœuds enfants (chemin) de leurs nœuds parents
2. Chaque chiffre (c'est-à-dire 1 ou 0) qui apparaît après le séparateur ~ nous indique à quel tour de joueur c'est maintenant de sélectionner un chemin. (1 pour maximiser et 0 pour minimiser)
3. Si un nom de nœud est séparé par * d'un nombre, alors le nombre indique la distance ou le coût du chemin passant par les nœuds mentionnés.

Par exemple, Stadium_*_9 : cela signifie que le stade est le dernier chemin vers la destination et que sa distance est de 9 km jusqu'à Saris via le chemin du stade.

Lorsque l'utilisateur exécute le programme, le « formulaire » du programme de recherche d'itinéraire s'affiche. Tout d’abord, sélectionnez le chemin du fichier qui contient l’espace d’état et entrez l’emplacement de destination dans la zone de texte. Les étapes sont les suivantes :

• Cliquez sur «…» pour sélectionner l'emplacement du fichier, puis
• Entrez le lieu de destination, dans la zone de texte prévue.
• Cliquez sur le bouton « Go » ou appuyez sur la touche Entrée/Retour pour exécuter le programme.

Le système effectue automatiquement la tâche suivante :

1. Il vérifie l'existence du fichier contenant l'espace d'état dans le dossier spécifié.
2. Si le fichier est disponible/existe, lisez le contenu du fichier et stockez-le dans « contenu », puis tokenisez le chemin avec le nom du chemin.
3. Après la tokenisation, le contenu sera stocké dans la structure de données respectivement en tant que nœud, successeur, niveau MiniMax et distance.
4. Le contenu du fichier sera stocké sous forme de liste de structure.