alors voila le sujet :
un postier doit parcourir toutes les rues d'une ville, mais il doit aussi pouvoir le faire en un minimum de temps (il marche à vitesse constante)
de plus il peut y avoir des rues "doubles" et des boucles.
modele : un graphe non orienté simple ou non, avec ou sans boucles, et à aretes pondérées par la longueur des routes.
solution :
pour l'instant j'ai une solution en O(m) avec m = nombre d'aretes, dans le cas ou il n'y a pas de sommets de degré impair.
j'ai aussi la solution dans le cas ou il y a exactement 2 sommets de degré impair, en O(m) aussi.
but du sujet : trouver un algo pour la generalisation à 2n sommets de degré impair, avec une complexité minimale.
j'avais trouvé une methode mais le prof il m'a dit qu'il etait sceptique (si y'en a qui sont cho pour la preuve je serai grave heureux qu'ils la trouve)
idée :
- on cherche tous les sommets de degré impair.
- on cherche tous les chemins minimum (avec dijkstra) qui vont d'un sommet à un autre. jusque là on est en O(n*m+n) ce qui est deja pas mal
- c'est là que mon idée intervient :
on cree un graphe avec comme sommet les depart et arrivées des chemins. les aretes sont les chemins, et les poids sont les poids des chemins.
on applique kruskal pour trouver dedans un arbre couvrant minimal
et là il faudrait montrer que le meilleur choix de chemin (c'est a dire la somme des chemins doit etre minimale) est inclue dans cet arbre.
et the prof of algo il est pas d'accord...
BUT / PROUVER QUA CA MARCHE? OU TROUVER UN CONTRE EXEMPLE...
etape d'apres je l'ai et si la meilleure combinaison de chemin est dans l'arbre je peux l'extraire de cet arbre.
cette methode permettrait d'obtenir une complexité polynomiale au lieu d'exponentielle ou factorielle...
