Discussion :

[deuzef68]

Bonjour

mon intitulé sera surement laconique et obscur mais je n'arrivais pas à faire un titre court et précis

Voilà je m'explique...je recherche un algo dans le cadre d'un projet perso...
C'est sur la création de graphe (en recherche opérationnelle)
c'est pour une détermination et savoir si à la prochaine itération le graphe sera fermé (ou bouclé)

bon j'imagine que ce n'est pas plus clair
alors je détaille

au départ il y a juste un point...
de ce point on peut créer des voisins toujours à égale distance delta (c'est une valeur d'exemple)
avec comme contrainte des directions bien spécifiques... 6 maxi...
on nommera les directions de 1 à 6 et ses directions sont "espacés" de 60 degrées
la 1 est à midi
la 2 à 2 heures
la 3 à 4 heures
etc...

de chaque point ne peux partir que 3 directions max...espacé de 120 degrés

chaque point connait le ou les pts suivants au fur et à mesure que l'on crée les pts

à partir du 1er point on décide d'une direction "principale" et en découle forcément les 2 autres directions

exemple...de p1 on décide que ce sera la direction 1 la direction principale
donc de p1 on crée les pt
- P2 en direction 1
- p3 en direction 3
- p4 en direction 5
nota : les création se font toujours dans le sens des aiguilles d'une montre

comme on vient de créer les "3 voisins" de p1 on ne peut plus en créer depuis p1
on va en p2 par exemple
comme on prend la direction 1 en P2 on ne peut donc créer que les pts en direction 2 et 6
en direction 4 on retombe sur P1 qui existe déjà

donc depuis p2 on crée
- p5 en direction 2
- p6 en direction 6

et ainsi de suite...on choisit un pt suivant et on crée les voisins....

sauf que... le voisins suivant peut être déjà créé...

ainsi si on ce déplace à la suite dans les directions 1-2-3-4-5...
si on ce déplace après dans la direction 6 on retombe sur le premier point
que l'on ne peut créer puisqu'il l'ai déjà !

il y aurait il un moyen de déterminer que le prochain point existe déjà et va produire une boucle ???
et donc que l'on juste besoin de faire le lien..
mais sans astuce "géographique" pour déterminer la position

précision...une boucle est une boucle simple en "forme" de zéro... pas de forme de "8" à double boucle

à noter aussi que les boucles peuvent être simple 123456
ou plus complexe :
1232345656
ou
1234345616

J'ai pu remarquer :
que pour une boucle il faut forcément qu'il y ait les 6 directions au moins 1 fois

12456 ne produit pas une boucle
un chemin est de longueur pair forcément

que si une direction apparait un certains nombre de fois...sa direction inverse doit être en aussi grand nombre
les inverses sont
1 <-> 4
2 <-> 5
3 <-> 6
ainsi dans 1232345656
1 et 4 apparaissent bien 1 seule fois chacun
2 et 5 ... 2 fois chacun
3 et 6 ... 2 fois chacun

on pourrait penser que si on scinde le chemin en 2 parties égales...la 2ème est l'inverse de la première
mais ce n'est pas le cas
ex: 123434565612
123434 n'a pas pour inverse le chemin 565612
ici en réarrangeant le chemin il devient 1212 3434 5656... à méditer

Si vous avez des idées je suis preneur

d'avance merci

Fred

[stendhal666]

Je ne suis pas certain d'avoir parfaitement compris ta question mais bon, voilà ce que je ferais pour le résoudre le problème tel que je l'ai compris:

- je définirais chaque sommet du graphe comme un triplet (a, b, c) où a = d1 - d4, b = d2-d5, c = d3-d6, pour dn= nombre d'arêtes parcourues depuis le sommet initial dans la direction n pour aller jusqu'au sommet défini par le triplet. Chaque sommet est ainsi uniquement défini.
- je garderais les nœuds générés dans une structure qui facilite la vérification de l'existence d'un élément (un arbre balancé, une hash map), et je testerais l'existence du noeud nouvellement créé pour voir s'il y a boucle.

[deuzef68]

Je ne suis pas certain d'avoir parfaitement compris ta question ...

j'imagine bien qu'étant moi dans "mon trip" il n'est pas toujours facile d'expliquer et de clarifier les choses.
J'ai donc fait un "petit" pdf pour détailler les étapes de façon graphique...

J'espère que cela sera plus parlant et plus graphiquement clair.

J'attends toutes vos suggestions et vos remarques, de mon côté j'ai pu remarquer pas mal de choses pour déterminer ou détecter les boucles...
Mais à postériori...donc après le création d'un point.. et le tracé des liens...

j'aimerai pouvoir détecter avant... c'est à dire que l'on vérifie qu'il y aura ou pas une boucle...et donc on ne crée pas le pt mais on tire un lien...
c'est plus clair dans le pdf

Cordialement
et bonne année à tous

Fred
Les étapes.pdf

[stendhal666]

Ton pdf est très clair et très bien fait.
En revanche je ne vois pas ce qui ne te convient pas dans ma solution. Pour rappel: garder la liste des noeuds créés sous la forme (a, b, c) où a, b et c sont la différence entre le nombre de fois que les directions opposées (respectivement d1 et d4, d2 et d5, d3 et d6) ont été parcourues; pour reprendre les étapes du pdf:
étape 1: on crée le premier sommet (0,0,0) // sommet initial, aucune distance parcourue
...
étape 2.2: on crée le troisième sommet (0,0,1) // (a, b, c) où c = 1 (1*d3-0*d6)
...
étape 5.2: on crée le dixième sommet (0, 1, 1) // (a, b, c) où a = 0 (1*d1-1*d4), b = 1 (1*d2-0*d5), c = 1(1*d3-0*d6)
...
étape 6.3: on tente de créer le 12ème sommet mais : (0,1,1) - d5 = (0,0,1) !! déjà créé.

[deuzef68]

Ton pdf est très clair et très bien fait.

Merci c'est sympa... disons que j'ai l'habitude de faire des cahiers des charges

En revanche je ne vois pas ce qui ne te convient pas dans ma solution.

Je ne me permettrai pas de dire que cela ne convienne pas... j'ai juste répondu sur le fait que peut-être mon explication n'étais pas claire..
certainement pas sur le fond de ta réponse.
Je me suis concentré sur une meilleur modélisation
pas sur ta réponse... que je vais maintenant étudier de près

Pour rappel: garder la liste des noeuds créés sous la forme (a, b, c) où a, b et c sont la différence entre le nombre de fois que les directions opposées (respectivement d1 et d4, d2 et d5, d3 et d6) ont été parcourues; pour reprendre les étapes du pdf:
étape 1: on crée le premier sommet (0,0,0) // sommet initial, aucune distance parcourue
...
étape 2.2: on crée le troisième sommet (0,0,1) // (a, b, c) où c = 1 (1*d3-0*d6)
...
étape 5.2: on crée le dixième sommet (0, 1, 1) // (a, b, c) où a = 0 (1*d1-1*d4), b = 1 (1*d2-0*d5), c = 1(1*d3-0*d6)
...
étape 6.3: on tente de créer le 12ème sommet mais : (0,1,1) - d5 = (0,0,1) !! déjà créé.

effectivement ça fonctionne ton truc...plutôt bien même
à chaque nouveau point que tu veux créer, tu calcules sa "carte de position", son triplet..
puis tu balayes la liste des points déjà créés...tu compares avec celui que tu veux créer
et s'il n'y a pas de correspondance tu peux créer le nouveau point
s'il y a correspondance tu tires seulement un lien avec le point

on peux tout modéliser sous forme de triplet
D1: (1,0,0) D4: (-1,0,0)
D2: (0,1,0) D5: (0,-1,0)
D3: (0,0,1) D6: (0,0,-1)

On crée P1: (0,0,0)
quand on crée P2: = P1 + D1 = (0,0,0) + (1,0,0) = (1,0,0)
etc...

un grand merci déjà

ça répond bien au fait de savoir si un emplacement est déjà occupé par un point existant...
mais pas sur le comment on détermine si il y a une (ou plusieurs) boucle(s)

ah oui...remarque en sus... au maximum il ne devrait y avoir qu'une centaine de points...max...enfin je pense

Fred

[stendhal666]

Il y a une nuance qui m'échappe : quelle est la différence entre trouver un point qui existe déjà et former une boucle?

[deuzef68]

Il y a une nuance qui m'échappe : quelle est la différence entre trouver un point qui existe déjà et former une boucle?

facile tu ne peux avoir réellement de boucle qu'avec des points qui sont tagués

aussi l'exemple suivant n'est pas une boucle... P3 n'est pas tagué donc la boucle n'est pas réellement fermée


car à l'étape suivante tu n'est pas obligé d'aller sur P3 pour chercher les voisins
tu pourrais partir de P11 et continuer comme ci-dessous


celui-là est une boucle


Dans le cas suivant il y a 3 boucles

1 - P1-P2-P5-P8-P10-P3
2 - P8-P9-P14-P16-P11-P10
3 - P1-P2-P5-P8-P9-P14-P16-P11-P10-P3
Attention : la boucle en forme de 8 n'est pas compté comme une boucle car on ne peut utiliser qu'une seul fois un point tagué

j'ai fait une version V2 du pdf... en tenant compte de tes idées

[Flodelarab]

Bonjour

À ta place, je munirais ce quadrillage hexagonal de coordonnées. Et finies, les prises de têtes.

[deuzef68]

Bonjour

À ta place, je munirais ce quadrillage hexagonal de coordonnées. Et finies, les prises de têtes.

si tu penses aux coordonnées cartésiennes...
ce n'est pas très futé... tu vas te trinqueballer des sin30 et cos30 à tire-larigot...
alors imagine si tu fais un tour...pour retomber sur tes pattes...non franchement non !
c'est encore plus la prise de tête !!!

et puis les coordonnées ne vont pas te dire ou sont les boucles

la solution de stendhal666 est vraiment très futé... toute simple au niveau calcul...aucun arrondi puisque l'on utilise des entiers !
on peux faire 10 fois le tour on retombe toujours sur ses pieds...

c'est un pb de recherche opérationnelle



Un question pour stendhal666

si je voulais modifier l'énoncé et changer le nombre de voisins...passer de 3 à 6
toujours dans les 6 directions... penses-tu que ça fonctionne toujours ?

Fred

[stendhal666]

Oui, il n'y a pas de différence tant qu'il existe 6 directions opposées deux par deux.
Une question pour toi maintenant: avec quel outil fais-tu tes pdf?

Pour les boucles le problème est plus compliqué.

1. lors de la construction, une boucle est formée lorsqu'on tague un sommet dont deux sommets adjacents sont déjà tagués. Mais cela ne détecte pas les boucles composées.

2. si on cherche à les détecter après la construction, il me semble qu'il faut s'appuyer sur les propriétés du circuit eulérien (tous ses sommets sont de degré pair - en l'occurrence de degré 2 puisque les sommets ont un degré maximal de 3 par construction): soit tous les sommets ont deux arêtes incidentes et on a une seule boucle, soit non.

Si non, alors on identifie les sommets de degré impair:
- on peut éliminer en premier lieu les sommets de degré 1 puisqu'ils représentent la fin d'un chemin, sans possibilité de boucle;
- quand il n'y a plus de sommets de degré 1, il faut regarder les sommets de degré 3, plus compliqués: l'idée est de tenter de supprimer une des arêtes adjacentes et d'en voir l'effet:
- soit on retombe sur un cycle eulérien unique: on a ainsi détecté une boucle extérieure en plus des deux à l'intérieur;
- soit on retombe sur deux cycles eulériens distincts: il n'y a pas de boucle extérieure.

Cela fonctionne dans le cas des trois boucles que tu montrais dans ton avant-dernier message. Mais, naturellement, il y a la possibilité qu'il y ait plus de trois boucles, contigües ou non: il faut donc appliquer cet algorithme récursivement.

[deuzef68]

Oui, il n'y a pas de différence tant qu'il existe 6 directions opposées deux par deux.

Je pense que oui mais pourtant quand je fais des essais j'ai des incohérences.
Je vais faire un petit graphe et je refais une réponse tout à l'heure

Une question pour toi maintenant: avec quel outil fais-tu tes pdf?

toutes les questions que tu voudras je te dois bien ça
tu veux dire comment je fais les graphes avec les boules ? tout simplement avec visio...et copier coller dans word...
que je sauvegarde en pdf
sinon pour faire des graphes il existe des petit logiciels... j'utilise Grin mais pas dans ce cas ci

Pour les boucles le problème est plus compliqué.

je me doutais bien que c'était "moins" simple

1. lors de la construction, une boucle est formée lorsqu'on tague un sommet dont deux sommets adjacents sont déjà tagués. Mais cela ne détecte pas les boucles composées.

Est-ce que totalement vrai ? j'ai l'impression, à première vue, mais je peux me tromper qu'il doit y avoir des cas inverse...
je vais explorer cette hypothèse

2. si on cherche à les détecter après la construction, il me semble qu'il faut s'appuyer sur les propriétés du circuit eulérien (tous ses sommets sont de degré pair - en l'occurrence de degré 2 puisque les sommets ont un degré maximal de 3 par construction): soit tous les sommets ont deux arêtes incidentes et on a une seule boucle, soit non.

Si non, alors on identifie les sommets de degré impair:
- on peut éliminer en premier lieu les sommets de degré 1 puisqu'ils représentent la fin d'un chemin, sans possibilité de boucle;
- quand il n'y a plus de sommets de degré 1, il faut regarder les sommets de degré 3, plus compliqués: l'idée est de tenter de supprimer une des arêtes adjacentes et d'en voir l'effet:
- soit on retombe sur un cycle eulérien unique: on a ainsi détecté une boucle extérieure en plus des deux à l'intérieur;
- soit on retombe sur deux cycles eulériens distincts: il n'y a pas de boucle extérieure.

Cela fonctionne dans le cas des trois boucles que tu montrais dans ton avant-dernier message. Mais, naturellement, il y a la possibilité qu'il y ait plus de trois boucles, contigües ou non: il faut donc appliquer cet algorithme récursivement.

je ne pense pas que l'on est besoin de le faire à postériori... mais juste quand on tague
mais je garde sous le coude tes explications... toujours passionnantes

Fred

[deuzef68]

Ok de retour... j'ai fait encore des petits graphes

il faut savoir que j'ai au départ un peu simplifié l'énoncé... pour éviter de noyer tout le monde...

mais au début donc on a un point...auquel on crée les points voisins...
mais en plus on crée ce que j'appellerai des "co-voisins"... faut bien leur trouver un nom

ils n'ont pas la même propriété.
on ne peut créer des voisins que depuis d'autres voisins...pas les co-voisins
les co-voisins ne sont pas non plus tagué

donc si on reprend un début d'exemple
on a au départ P1


puis on choisit une direction principale ici D1... on crée les voisins dans les directions D1, D3 et D5


les coordonnées sont donc
P2 := (1, 0, 0)
P3 := (0, 0, 1)
P4 := (0, -1, 0)

puis on crée les "co-voisins" dans les directions D2, D4 et D6


les coordonnées sont donc j'imagine
C1 := (0, 1, 0)
C2 := (-1, 0, 0)
C3 := (0, 0, -1)

je ne me trompe pas ?

Puis et seulement ici on tague le point P1


Voilà tel qu'aurais dû être l'énoncé de base...
Mais hier soir j'ai essayé de l'appliquer et sauf grosse erreur de ma part...
ce qui n'est pas fortement improbable
j'ai des cas ou je ne retombe pas sur me pattes...

je vais essayer de retrouver le cas et je refais un graphe mais là plus complet

Fred

[stendhal666]

les coordonnées sont donc j'imagine
C1 := (0, 1, 0)
C2 := (-1, 0, 0)
C3 := (0, 0, -1)

je ne me trompe pas ?

Je ne pense pas.

mais pourtant quand je fais des essais j'ai des incohérences.

En même temps quand je vois l'heure à laquelle tu envoies tes messages il peut y avoir une explication

Citation Envoyé par stendhal666
1. lors de la construction, une boucle est formée lorsqu'on tague un sommet dont deux sommets adjacents sont déjà tagués. Mais cela ne détecte pas les boucles composées.

Est-ce que totalement vrai ? j'ai l'impression, à première vue, mais je peux me tromper qu'il doit y avoir des cas inverse...

Comme on dessine le graphe "sans lever le stylo", il n'est pas possible de relier deux points tagués qui n'appartiennent pas au même chemin, c'est-à-dire de boucler une boucle

je ne pense pas que l'on est besoin de le faire à postériori... mais juste quand on tague

Oui mais quand tu crées ton graphe, je ne vois pas comment tu pourrais faire pour détecter si tu crées une ou plusieurs boucles en fermant un chemin. Dans le dernier cas que tu évoquais (les 3 boucles du graphe en forme de 8), tu pourras détecter que tu formes deux boucles puisque tu fermeras deux chemins, mais tu ne pourras pas détecter la troisième, je pense...

tout simplement avec visio...et copier coller dans word...

Eh bien je ne connaissais pas visio, je pensais qu'il n'y avait que powerpoint pour faire des diagrammes dans office. J'ai regardé les prix de visio () mais heureusement il y a des alternatives gratuites!

[deuzef68]

J'ai un exemple complet


On imagine bien qu'on a fait plusieurs étapes pour arriver là
on a fait donc le tour complet
si tu prends les pts P1-P2-P5-P8-P10-P3-P1
P1 + D1 = P2 vérification (0,0,0) + (1,0,0) = (1,0,0)
P2 + D2 = P5 vérification (1,0,0) + (0,1,0) = (1,1,0)
P5 + D3 = P8 vérification (1,1,0) + (0,0,1) = (1,1,1)
P8 + D4 = P10 Vérification (1,1,1) + (-1,0,0) = (0,1,1)
P10 + D5 = P3 Vérification (0,1,1) + (0,-1,0) = (0,0,1)
P3 + D6 = P1 Vérification (0,0,1) + (-1,0,0) = (0,0,0) -> pas de soucis on retombe sur P1...c'est ok

Maintenant on essaye avec les Cn

Partons simplement de P1 pour aller à P8 en passant par C1

P1 + D2 = C1 ... (0,0,0) + (0,1,0) = (0,1,0)
C1 + D2 = P8 normalement
(0,1,0) + (0,1,0) = (0,2,0).... P8 est égal à (0,1,1) !!!

Où me suis-je donc bien trompé ?

Fred

[deuzef68]

Je ne pense pas.

donc on est sur la même longueur d'onde

En même temps quand je vois l'heure à laquelle tu envoies tes messages il peut y avoir une explication

on soigne ses insomnies comme on peut... et quand je cherche des réponses...j'ai encore plus de mal à dormir

Comme on dessine le graphe "sans lever le stylo", il n'est pas possible de relier deux points tagués qui n'appartiennent pas au même chemin, c'est-à-dire de boucler une boucle

voilà le fond du pb "sans lever le stylo".... en fait on lève le stylo puisque on peut aller sur n'importe quel voisin...
non tagué pour continuer le graphe...
certes ce pt non tagué est relié forcément à au moins un pt tagué

Oui mais quand tu crées ton graphe, je ne vois pas comment tu pourrais faire pour détecter si tu crées une ou plusieurs boucles en fermant un chemin. Dans le dernier cas que tu évoquais (les 3 boucles du graphe en forme de 8), tu pourras détecter que tu formes deux boucles puisque tu fermeras deux chemins, mais tu ne pourras pas détecter la troisième, je pense...

je ne sais pas encore si c'est le plus important de trouver toutes les boucles...enfin pour l'instant pas

Eh bien je ne connaissais pas visio, je pensais qu'il n'y avait que powerpoint pour faire des diagrammes dans office. J'ai regardé les prix de visio () mais heureusement il y a des alternatives gratuites!

Je l'ai utilisé quotidiennement dans mon boulot alors j'y suis habitué
il est cher c'est vrai... mais bien pratique

il y en a d'autres...dia par exemple

Sinon comme logiciel pour tracer les graphes regarde là

http://pagesperso.lina.univ-nantes.f...con/frame.html

fred

[stendhal666]

Non, tu ne t'es pas trompé pour les 6 directions... Il va falloir trouver une autre solution
Mais tu es sûr qu'il y aura 6 directions, pas 12? Autant réfléchir directement pour trouver la bonne solution, non?

[deuzef68]

Non, tu ne t'es pas trompé pour les 6 directions... Il va falloir trouver une autre solution
Mais tu es sûr qu'il y aura 6 directions, pas 12? Autant réfléchir directement pour trouver la bonne solution, non?

non non 6 c'est sûr... pas une de plus
cela en fait déjà assez

c'est quand même étonnant que ça ne fonctionne pas avec les Cn alors qu'avec les Pn ça fonctionne...
alors qu'en fait les Cn ne sont que les symétriques par rapport au point de création des points Pn...

j'avais envisagé hier soir un changement de repère... pour les Cn... mais pas de résultats concluant...peut être un mauvais choix de repère

En fait on peut traiter les Cn en parallèle des Pn... comme ils n'ont pas la même fonction...
si on trouve un système pour les Cn en utilisant uniquement QUE les Cn ça va aussi...
avec une passerelle pour passer de l'un à l'autre...

ce que j'ai du mal à piger c'est que l'on crée bien les Cn à partir des Pn...
il y a bien une relation de causalité entre les deux...

Si tu as des idées...

[deuzef68]

J'avais envisagé une structure comme cela


ou le réseau des Cn ce superpose au réseau des Pn...
(le réseau des Cn est dans une autre couleur sur le schéma)
mais comment faire la passerelle entre les 2 mondes
car en fait le monde principal est celui des Pn et tous les "calculs" tournent autour d'eux...
les Cn sont calculés à partir des positions des Pn

tu peux donc définir 3 nouveaux axes
le pt central en C1 et les axes a' : (C1,C4) , b' : (C1,C5) , c' : (C1,C6)
et là uniquement dans le monde des Cn ça fonctionne


Mais on fait alors comment pour le "rattacher" au monde des Pn ? ...



J'avais aussi envisagé une structure de ce type


On fait table raz de l'énoncé du départ
les liens ne sont plus tiré directement des points Pn mais de Pn1-Cn1-Pn2
et donc on calculerait les Pts voisins à partir des co-voisins...
on inverse l'ordre de calcul... en intercalant les Cn entre les Pn

Mais il faut investiguer un peu plus

Ce n'est d'ailleurs peut être même pas pertinent

[deuzef68]

Dans le schéma du dessus

les axes sont
D1 := (1,0,0)
D2 := (0,1,0)
D3 := (0,0,1)
D4 := (-1,0,0)
D5 := (0,-1,0)
D6 := (0,0,-1)

Si on prend le chemin
P1-C3-P2-C4-P5
et qu'on le compare avec
P1-C1-P5

Dans le 1er cas
P1-(D6)-C3-(D2)-P2-(D1)-C4-(D3)-P5
P1 + D6 + D2 + D1 + D3 = P5
(0,0,0) + (0,0,-1) + (0,1,0) + (1,0,0) + (0,0,1) = (1,1,0)

on le compare avec
P1-(D2)-C1-(D1)-P5
P1 + D2 + D1 = P5

(0,0,0) + (0,1,0) + (1,0,0) = (1,1,0)

ça fonctionne !

ce pourrait être la solution...

Bon j'ai fait un pdf décrivant les étapes pour le schéma ci-dessous


ça fonctionne très bien... faudrait surement essayer sur un plus grand schéma...à voir demain

[stendhal666]

ça fait un joli cube!

La solution me paraît correcte. Reste à savoir si elle te satisfait, car il y a quelque chose de pas entièrement naturel à devoir passer par un point C obligatoirement pour atteindre un point P et cela pourrait ajouter de la complexité plus tard selon ce que tu souhaites faire.

D'un autre côté, la solution à laquelle j'ai pensé est tellement simple que je ne comprends pas que nous n'y ayons pas songé plutôt: il suffit d'identifier les points par leurs coordonnées (x, y) puisque les 6 directions sont:
D1 = ( 1, 0)
D4 = (-1, 0)
D2 = (-1, 1)
D5 = ( 1, -1)
D3 = ( 1, 1)
D6 = (-1, -1)

Après nous avons l'assurance que tout fonctionne puisque les calculs sont de l'arithmétique vectorielle tout ce qu'il y a de plus conventionnel.