Discussion :

[stendhal666]

Excellent!!

Au moins on peut être sûrs qu'on ne manque aucune boucle En revanche on les compte un certain nombre de fois... Du coup tu as décidé de "masquer" successivement toutes les arêtes partant de chaque sommet? Tu penses que ça ne peut pas marcher avec la succession "en éclair":
\
|
\
?

[deuzef68]

Excellent!!

je savais que ça allait te plaire c'est cool le top serait que l'on sorte le document par génération automatique

Au moins on peut être sûrs qu'on ne manque aucune boucle En revanche on les compte un certain nombre de fois...

oui tu peux compter 72 boucles trouvés alors qu'il n'y en a réellement que 7...
c'est plus que des doublons mais qu'importe on est sûr des les trouver toutes comme ça
après il faut une moulinette pour repérer les doublons (ou plus) et n'en garder qu'une

Du coup tu as décidé de "masquer" successivement toutes les arêtes partant de chaque sommet? Tu penses que ça ne peut pas marcher avec la succession "en éclair":
\
|
\
?

je ne dis pas que cela ne peux pas fonctionner... je dis juste que je n'ai pas recul pour voir si ça fonctionne à 100%
ne risque t'on pas de louper des choses ? là est la question

[deuzef68]

Excellent!!

Au moins on peut être sûrs qu'on ne manque aucune boucle En revanche on les compte un certain nombre de fois... Du coup tu as décidé de "masquer" successivement toutes les arêtes partant de chaque sommet? Tu penses que ça ne peut pas marcher avec la succession "en éclair":
\
|
\
?

Bon j'ai repris le schéma de départ, celui qui est détaillé dans le pdf...
utilisé comme possibilité ta technique "en éclair"
j'ai appliqué la même méthode du "Delete + Compacte" et voilà ce que l'on en déduit


c'est plus rapide... mais on en déduit que 2 boucles

Euh ôte moins d'un doute c'est comme ça que tu voyais les choses... je ne suis plus sûr

[stendhal666]

Non, je voyais un truc séquentiel:
on masque \ (par exemple l'arête noir-bleu)
puis on nettoie et on compte
on masque | (donc bleu orange)
puis on nettoie et on compte
on masque \ (et orange vert)
puis on nettoie et on compte
pour chacune des paires de sommets de degré 3

[deuzef68]

En tout cas dans mon développement détaillé dans le pdf
les différentes solutions sont

Les 7 y sont

Dans ce schéma on trouve 4 pts de degré 3... 12 cas...
le fait d'enlever 1 degré sur 1 pt... à pour conséquence après "compactage"... d'enlever aussi 1 degré sur un autre pt
il reste donc 2 pts de degré 3... donc 2 * 3 -> 6 cas
que qui fait au total 12 * 6 -> 72 cas à tester

mais il y a des lien entre des pts de degré 3 qui sont communs

là on peux voir qu'il y a 3 liens dans ce cas...donc on pourrait détecter ses liens "communs" pour ne rechercher
des boucles qu'une seule fois au lieu de 2
Ce qui fait que l'on ne ferait plus que 12 - 3 = 9 cas au départ...

qui ont chacun 6 cas... au total 9 * 6 = 54 cas à tester
ça fait moins mais je ne sais pas si on trouvera quelque chose de plus court

[deuzef68]

Petite question subsidiaire...
pour calculer dans le schéma de l'algo détaillé dans le pdf...combien doit on trouver de cas ?

dans l'hypothèse ou il y a :
4 pts de degré 3 cela fait (4*3)*(2*3)=72 cas à tester
6 pts de degré 3 cela fait (6*3)*(4*3)*(2*3)=1 296 cas à tester
8 pts de degré 3 cela fait (8*3)*(6*3)*(4*3)*(2*3)=31 104 cas à tester
ça grimpe vite

ce serait quoi la formule pour calculer le nombre de cas en fonction de n ?

Non, je voyais un truc séquentiel:
[…]
puis on nettoie et on compte pour chacune des paires de sommets de degré 3

tu comptes quoi ? je ne pige pas...

[deuzef68]

J'ai entrevu quand même des cas ou il faut refaire des étapes de traitement
ainsi dans le cas suivant

je n'ai pas dessiné tous les cas...
mais on voit bien qu'au final... dans le cas dessiné...au lieu d'avoir une boucle on en aura 3...
mais tous les points sont de degré 2 et on a séparé les boucles
il faut donc rajouter une étape de comptage de boucle

[stendhal666]

Hello,
Je continue à suivre mais j'ai un autre projet en même temps qui m'a pas mal occupé.
J'ai l'impression qu'on arrive pas à diminuer la complexité comme ça. Il faudra peut être revenir à un algo classique. J'ai quelques idées là dessus...

[deuzef68]

Hello,
Je continue à suivre mais j'ai un autre projet en même temps qui m'a pas mal occupé.

hello aussi
oui j'imagine que tu n'as pas que le forum comme préoccupation
je comprend pas de soucis

J'ai l'impression qu'on arrive pas à diminuer la complexité comme ça. Il faudra peut être revenir à un algo classique. J'ai quelques idées là dessus...

j'ai fouillé les algo de parcours...mais c'est aussi assez complexe...pas forcément moins que ce que l'on a envisagé pour l'instant...

si tu as une idée pour le calcul du nombre de cas je suis preneur (voir message au dessus)

maintenant soit on fait un algo simple qui tourne vite...même si tu as beaucoup de cas...
ou un algo plus péchu plus fin mais avec pas mal de test et de conditions qui ralentissent le déroulement
j'aurai tendance à dire...plus mais plus vite...à voir
si tu as des idées je suis preneur

[stendhal666]

En restant sur un algo plus fin, je me demande la chose suivante:
- n'y a-t-il pas un moyen de déduire le nombre de boucles internes à une grande boucle en comptant le nombre de sommets de degré 3 connectés entre eux qui lui appartiennent? Cela reste à fouiller, en particulier la notion de sommets connectés entre eux. L'idée serait en deux étapes: isoler les "grandes" boucles (celles qui ne sont contenues dans aucune autre boucle) puis additionner les résultats obtenus par observation de leurs sommets de degré 3.
- il ne reste plus qu'à déterminer quelle est la boucle la plus grande, mais cela peut-être fait assez facilement (mais assez lentement également) avec un backtracking simple de type breadth-first-traversal.

[deuzef68]

En restant sur un algo plus fin, je me demande la chose suivante:
- n'y a-t-il pas un moyen de déduire le nombre de boucles internes à une grande boucle en comptant le nombre de sommets de degré 3 connectés entre eux qui lui appartiennent?

c'est pas idiot comme question...mais je dirais que la réponse doit être "non"...

Cela reste à fouiller, en particulier la notion de sommets connectés entre eux. L'idée serait en deux étapes: isoler les "grandes" boucles (celles qui ne sont contenues dans aucune autre boucle) puis additionner les résultats obtenus par observation de leurs sommets de degré 3.

"additionner"...tu veux dire quoi ? que si on avait la boucle "englobante" et le nombre de pt de degré 3 de cette boucle on pourrait en déduire le nombre de boucles ?
si c'est oui j'en doute... quoique en y réfléchissant...2 pts de degré 3 veux dire qu'il y a interconnexion de 2 boucles...donc 2 boucle séparé + 1 boucle englobante
mais après vouloir en tirer une formule...pour 4, 6 ou plus... j'imagine qu'il doit y avoir encore pas mal de contre-exemples

- il ne reste plus qu'à déterminer quelle est la boucle la plus grande, mais cela peut-être fait assez facilement (mais assez lentement également) avec un backtracking simple de type breadth-first-traversal.

c'est un parcours en largeur me semble t'il...
je voyais plus un parcours en profondeur... à voir...

[deuzef68]

En restant sur un algo plus fin, je me demande la chose suivante:
- n'y a-t-il pas un moyen de déduire le nombre de boucles internes à une grande boucle en comptant le nombre de sommets de degré 3 connectés entre eux qui lui appartiennent?

si je reprend ce schéma...il y a 4 pts de degré 3... 3 appartiennent à une boucle... et 1 fait le regroupement des 3 boucles
il n'y a pas de boucle englobante... ça va être dur de trouver une règle de simplification autre qu'une règle de "force brute" pour faire tous les cas

[stendhal666]

si je reprend ce schéma...il y a 4 pts de degré 3... 3 appartiennent à une boucle... et 1 fait le regroupement des 3 boucles
il n'y a pas de boucle englobante... ça va être dur de trouver une règle de simplification autre qu'une règle de "force brute" pour faire tous les cas

Oui c'est très juste mais l'idée est de connaître d'abord la boucle englobante, donc ça ne poserait pas problème. Cependant pour connaître la boucle englobante il faut la distinguer de celles qui sont plus petites, donc ça rend l'optimisation que je proposais inutile.

Du coup, parcours en largeur ou en profondeur c'est un peu indifférent, je crois, non?

- on part du sommet initial
- on marque chaque sommet parcouru
- à chaque fois qu'il y a plus d'un embranchement possible, on ajoute à la liste des parcours chacun des embranchements
- si le parcours aboutit à un sommet déjà marqué, on a deux cas: soit c'est le sommet initial et le parcours entier forme une boucle, soit non et dans ce cas un parcours en sens inverse jusqu'à retrouver le même sommet permet de dégager la boucle.

[deuzef68]

Du coup, parcours en largeur ou en profondeur c'est un peu indifférent, je crois, non?

pour le résultat ça ne change pas...pas contre pour le traitement..;quand tu rencontre une nouvelle banche
tu lances un autre traitement récursif que tu peux souvent traiter en parallèle
c'est souvent un sacré avantage