salut

si tu veux un maximum de points donc d'arêtes il faut on peut choisir à chaque fois une arête de poids minimal pour passer au sommet suivant ... ou tester tous les cas ...

puisque le graphe est complet je partirai d'un sommet dont une arête est de poids minimal

dans tous les cas le cycle ne sera pas optimal ...

supposons qu'on ait n sommets numérotés de 1 à n

je créerai une liste graphe [sommet(i), arête(i)] où arêtes est elle-même la liste des poids
de toutes les arêtes partant de sommet(i)

arête(1) = [0, p_12, p_13, ..., p_1n]
arête(2) = [p_21, 0, p_23, ..., p_2n]
...
arête(n) = [p_n1, ..., 0]

avec p_ij = p_ji

je mets 0 pour l'arête sommet(i)-sommet(i) qui n'existe pas ...   (ou travailler avec une matrice ...)

ensuite je créerai une fonction récursive cycle qui demande en entrée sommet(i)
qui passe à un sommet suivant en testant s = poids < L
avec un compteur du nombre de sommets

Bonjour,,

Petite question à propos du problème, pour lever un doute :

nidya @ 24-10-2020 à 12:05


Partant d'un point donné, je cherche un cycle ( = chemin qui commence et se termine par un même point) de longueur qui maximise le nombre de points par lequel il passe, tout en ayant une longueur

Distinct oui !!

Il faut partir d'un point donné du graphe, on a pas le choix du départ !
Ou bien vous pouvez généraliser à n'importe quel point si vous souhaitez pimenter la chose

Bon finalement, en manipulant mes données de travail, j'ai pu transformé le problème concret dont j'ai formalisé cet énoncé de telle sorte que le graphe respecte les distances euclidienne c'est à dire AB + BC >= AC.
Ainsi, il suffit je pense de rajouter un sommet si l'on est sûr que le retour n'entrave pas la condition de majoration

Ainsi, dans ce cas précis, supposons qu'on parte de A et qu'on peut au moins faire un aller retour avec un sommet ( sinon le circuit serait juste... A) :

Initialisation :
Circuit = (A)
X = A le dernier sommet de Circuit
l = 0 la longueur de Circuit
N = 1 le nombre de sommet dans le Circuit
W = ensemble des successeurs de X (donc tous les sommets par complétude)

Récurrence :
Tant que X != A ou l==0 :
          Tant qu'on ne rajoute pas de sommets :
                    Y = sommet dans W dont l'arête est minimum
                    d = XY longueur de l'arête
                    retour = YA distance du retour si on souhaite fermer le circuit (avec AA = 0)
                   Si l + d + retour <= L :
                            Circuit = Circuit ++ Y on rajoute Y au Circuit
                             X = Y
                              l = l + d + retour
                             N = N + 1
                   Else :
                            W = W/{Y}
                   Fin si
        Fin tant que
Fin tant que


Le résultat est forcément un cycle puisque en le construisant on s'assure que le retour est possible.

La condition de majoration est forcément respectée puisqu'on rajoute seulement des points dont le retour en A respecte la majoration.

Est-ce ce que le nombre de sommets est maximal ? Puisqu'on prend à chaque fois l'arête qui est la plus courte possible et qui respecte la majoration, alors ça veut sûrement dire qu'on a un circuit qui a le plus d'arêtes possibles et donc le plus de sommets puisque le graphe respecte les distances euclidiennes (je saurais pas prouver formellement cette dernière implication mais mes dessins m'en persuadent..)

Donc c'est (sûrement) un cycle qui correspond à ce qu'on veut !

Est-ce qu'il est d'ailleurs le cycle de longueur minimal ? J'ai envie de dire oui puisqu'on choisit à chaque fois l'arête la plus petite possible ! Je ne saurais pas non plus le prouver formellement mais je ferais comme Fermat en disant que la marge est bien trop petite pour l'écrire



Pour ma part cette solution me convient puisqu'elle résout mon problèmer réel, mais libre à vous d'essayer de trouver une solution générale pour des graphe où on pourrait trouver des sommets tels que AB + BC < AC. Je garderai un œil très curieux sur ce sujet !!