Graphes et outils logiques Projet Python - Les labyrinthes
Jean ARBACHE - DL Math-Info Groupe A2
Questions n'ont pas été faits
B0(partielement fait) - B3 - B5'
*B0 -> J'ai réussi à extraire de laby les informations important (les endroits où dit s'il y a des mures ou non) dans la fonction 'decompress' et du coup j'ai enlevé tous les 0 et 1 qui se répetent toujours s'il y avait des mures ou non. Mais pour le decompresser il fait un erreur(Il y a des explicationsencore dans le code )
*B3 -> L'idée pour moi est clair mais j'ai preferé de faire autre fonction pour avancer
*B5' -> j'ai comris ce q'il fait mais j'ai pas eu le temps de coder je vais vous donner un exemple ,qui peut être vrai si j'ai bien compris, c'est toujours mieux que rien
Petite remarque:
Quand il y a une ameliartion demandée les fonctions écrites sont directements la versions ameliorées je n'ai pas gardé les anciennes, du coup il y aura pas deux fonctions une avant l'ameliartion et une après l'ameliartion il y aura juste la fonction ameliorée. Donc il y a une fonction affiche qui est déja ameliorée et une algorithme union-find qui est déja optimisée et une fonction résout qui resout les deux types de labyrinthe et quand c'est imparfait elle trouve le plus court chemin
Difficultés rencontrés
Juste le début j'ai pris plein du temps à comprendre ce qu'on doit faire et puis la fonction affiche amilioré m'a pris le plus de temps avec la fonction compress aussi
VARIABLES GLOBLAES
Fonction d'affichage ameliorer
Explication de compression
L'idée principale de compression c'est d'enlever tous les 0,1 qui sont répétés et qui ne donnent aucun renseginment partilculaires sur le labirainthes (par exemples les coins qui sont oujours des 1 et les milieu de chaque case 'les tuile' qui sont toujours 0)
fonction compress --> réussi elle retourne juste les informations sur les murs
fonction decompress --> pas réussi totalement
le but et de compresser le labyrinth et dans le fonction affiche le décompressé avant l'afficher
""AlGORITHME QUICK-FIND""
C'est le même principe de l'ameliartion Compression des chemins que vous avez proposé mais c'est son nom sur le refrence où je le trouver sur Internet (Algorithms, 4th Edition by Robert Sedgewick) http://www.albertstam.com/Algorithms.pdf
J'ai choisit cette amelioration pour ces raisons:
1- Cet Algo est plus adapté pour la fonction genere parce que le nombre d'appele de fonction find est toujours superieur ou égal à nbr d'appel de union. Du coup cela sera plus efficace de faire un find plus rapid
2- Dans cette Version on a toujours des arbres de hauteur maximal 1 parce que les sommets pointent directement vers le racine
3- Find est de complixité constante O(1)
4-La seul point négatif c'est union qui est de complixité linéaire O(n)
le technique utilsé pour savoir si la fonction "uninion" fait un cercle c'est de savoir si le graphe est connexe c.a.d si elle est connexe elle va forcement connecter deux elements qui sont déja connéctée donc dans plus part de cas on va tomber sur un cercle
Cette fonction fait un laby pas parfait qui contient 'cr' cycles
En plus elle affiche les lieu où les cercles ont étés crées
RESOLUTION
La fonction de resoudre le labyrithe
elle crée un dictionnaire dont les clés sont les cases de labyrinthe et chaque clé point vers le tuile suivant pour arrivé à la sortie Si le labyrinthe n'est pas parfait elle trouve le plus court chemin aussi. Du coup elle fonctionne pour les deux labyrinth
ces deux fonction resumeParfait et resumeImparfait resument tous ce que j'ai fait avant donc elle genere un laby parfait et un autre imparfait et resoudre les deux laby par afficher les chemins de chauque tuile vers la sortie et quand le laby est imparfait elle fait le plus court chemin Ces deux fonction n'a rien avoir la question B6'