Mon répertoire pour le bureau d'étude graphes de 3MIC à l'INSA de Toulouse
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
gasc 59329c4dbc Importation du code depuis GitHub 2 years ago
be-graphes-algos Importation du code depuis GitHub 2 years ago
be-graphes-gui Importation du code depuis GitHub 2 years ago
be-graphes-model Importation du code depuis GitHub 2 years ago
rsc Importation du code depuis GitHub 2 years ago
README.md Importation du code depuis GitHub 2 years ago
pom.xml Importation du code depuis GitHub 2 years ago

README.md

I3MIIL11 - Bureau d’étude graphes

Répertoire de travail pour le bureau d’étude graphes de 3 MIC à l’INSA de Toulouse.

Remarques

Ce BE sera à priori fait sous VSCode (sous Ubuntu 20.04.02) au lieu d’Eclispe pour des raisons de praticité et d’habitudes (et aussi parce que je n’ai pas énormément de place sur mon disque dur). Jusqu’à présent ce choix ne m’a posé aucun problème hormis pour générer la docs.

Algorithme de Dijkstra (PCC)

Voici quelques résultats visuels de mon algorithme de Dijkstra en mode plus court chemin. D’abord sans observateurs, en vert sans contrainte de chemin, en rouge les routes autorisées aux voitures uniquement :

2 chemins

Exemple de résultat avec observateurs :

avec observateurs

Test

Test avec oracle

Pour effectuer ces tests, j’ai utiliser le GUI pour créer un oracle avec Bellman Ford (un trajet entre l’aéroport LFBO et l’INSA de Toulouse sur la carte Haute Garonne). Notez que les tests peuvent être effectués avec n’importe quel autre oracle (il suffit de changer la carte et l’oracle).

On vérifie alors que la solution retournée est equivalente à l’oracle. Note: On vérifie pas l’égalité strict des chemins car (théoriquement) deux chemins optimaux peuvent co-exister.

Test d’optimalité (tests sans oracle)

Plusieurs tests sans oracle ont été implémentés :

  • Test des sous-chemins : tous les sous-chemins doivent également suivre les mêmes nodes
  • Test du vol d’oiseau : la distance en vol d’oiseau doit être plus courte que la distance obtenue
  • Test de l’inégalité triangulaire : le même trajet passant par un troisième point doit être plus long ou égal en distance au chemin trouvé