Projet d'algorithmique : la technologie dernier cri dans les télécommunications

Résumé du document

Projet d'algorithmique complet de fin de 1ère année d'école d'ingénieurs.

Extraits

[...] L'ensemble des villes à relier au nouveau réseau est disponible sur une carte avec également les tracés potentiels pour certaines d'entre elles ainsi que leur coût de réalisation. En effet, des raccordements sont impossibles sur des régions au relief trop accidenté. Ainsi, par exemple, pour raccorder Clermont-Ferrand à Limoges, on raccordera la première à Paris qui sera raccordée à Bordeaux qui elle-même sera raccordée à Limoges. En suivant le principe énoncé auparavant, Limoges et Clermont-Ferrand seront bien reliées. Les moyens financiers seront limités et les villes de plus de cent mille habitants seront privilégiées sauf exceptions. [...]

[...] Formalisation du problème Données V = nombre de villes sur la carte donnée nombre total de grandes villes sur la carte E = nombre de raccordements entre les villes sur la carte donnée (arêtes) MatAretes = matrice reliant les villes avec leurs arêtes respectives MatCout = matrice des coûts de réalisation de chaque raccordement possible Ville = entier définissant une ville GdVille = entier définissant si la ville a plus de 100.000 habitants ou pas (si oui = sinon Marquage = entier définissant si on est déjà passé dans une ville (si oui = sinon Arete = entier définissant un raccordement entre deux villes (une arête) CalculCout = fonction calculant le coût total d'un parcours Connecycle = fonction déterminant la connexité et la présence de cycle(s) Parcours = structure ayant comme données SousgrapheFinal et CoutFinal VilleSommet = structure ayant comme données Ville, GdVille et Marquage ListeVilleSommet = liste chaînée de VilleSommet PtrVilleSommet = pointeur sur un élément de ListeVilleSommet FileAttente = liste First-In-First-Out doublement chaînée Sousgraphe = tableau définissant un parcours Cout = entier définissant le coût d'un parcours (calculé avec CalculCout) CoutFinal = entier définissant le coût du parcours le moins cher SousgrapheFinal = tableau définissant le parcours le moins cher Explications complémentaires La carte qui nous est donnée au départ correspond à un graphe G(V,E). E MatAretes, et MatCout sont donnés dès le départ par le problème. V comprend à la fois les villes de moins et de plus de 100.000 habitants. Ville permet de différencier les différentes villes par un numéro. [...]

[...] Pour des raisons d'optimisation de temps, V sera donné au maximum égal à 20. E est le nombre total de raccordements entre villes imposé par la carte donnée, donc par le problème. Grâce à on va pouvoir par récursivité énumérer toutes les solutions possibles ressemblant à des mots binaires de E bits Chaque bit sera une case du tableau Sousgraphe et correspondra à un raccordement entre deux villes (arête). La case i du tableau (Sousgraphe[i]) correspondra à l'arête i de la carte donnée. [...]

[...] Au départ, la structure Parcours est vide et au fur et à mesure de l'avancée de l'algorithme, la comparaison de Cout et CoutFinal permet de l'actualiser. Structures de données Parcours : Struct graphe{ int* SousgrapheFinal ; int CoutFinal ; } ; VilleSommet : Struct sommet{ int Ville ; int GdVille ; int Marquage = 0 ; } ; ListeVilleSommet : Struct listesommet{ Struct VilleSommet ; struct listesommet* suiv ; } ; FileAttente : Struct file{ int* PtrVilleSommet ; struct file* suiv ; struct file* prec ; } ; Méthode algorithmique simplifiée Enumération générant tous les sous graphes possibles Si un sous graphe est crée, tester la connexité (toutes les grandes villes présentes) Si vrai Si faux tester si le sous graphe est cyclique Aller au Si vrai Si faux calculer le coût du parcours Aller au vérifier si le coût du parcours est minimum à cet instant Si vrai Si faux mettre le parcours et son coût dans la structure Aller au Continuer l'énumération (retour Retourner la structure Parcours II/ Méthode algorithmique Pseudo code de la fonction principale Fonction Parcours MAIN(MatAretes, MatCout, Déclarations: est un entier (initialisé à est un entier (initialisé à •Parcours est une structure (les champs sont initialisés sur Null) ENUMERATION(Sousgraphe, ; Retourner Parcours ; FinFonction MAIN Pseudo code de la fonction Enumeration Fonction Enumeration(Sousgraphe, Déclarations: est un entier (initialisé à est un entier (initialisé à est un entier (initialisé à •CoutFinal est un entier (initialisé à 99999) Si alors #Création d'un parcours terminée# s Connecycle(Sousgraphe, MatAretes, ; Si = alors Cout CalculCout(Sousgraphe, MatAretes, MatCout) ; Si (Cout CoutFinal Sousgraphe s=1 Cout= 85 (cf exemple E.2) Cout>CoutFinal Retourner Parcours Complexités •Complexité fonction CalculCout Dans le pire des cas, on parcourt les deux boucles Tantque imbriquées V fois et la boucle Pour E fois. [...]

[...] Cette dernière variable est à 1 si l'on est déjà passé par la ville et à 0 par défaut. La fonction CalculCout sera utilisée dès qu'un parcours sera déclaré valide (connexe et non cyclique). Elle calculera le coût total d'un parcours et le retournera dans la variable Cout. Cette dernière sera comparée à CoutFinal pour savoir si le nouveau sous graphe est moins cher que celui étant dans la structure Parcours. Celle-ci contient deux variables, SousgrapheFinal qui est le parcours le moins coûteux avec son fameux coût contenu dans CoutFinal. [...]