Problème combinatoire ? [Résolu]

[ISIC]

Bonjour,

Voici un problème que je n'arrive pas à résoudre. Ce n'est pas un problème de mathématiques établi, c'est un problème réel que j'ai essayé de schématiser. j'espère que vous pourrez m'aider et que j'ai su correctement expliquer. J'ajoute un schéma que j'ai dessiné pour que se soit plus clair.

Je souhaite relier les points rouges entre eux. Dans chaque cas je dois passer par un point bleu. Lorsque je suis passé par un point bleu, je n’ai pas la possibilité de revenir sur le même point bleu.
C’est à dire que dans mon parcours je ne pourrais pas passer deux fois par le point A2. Les points bleus conduisent vers un point rouge. Ensuite il y a le choix de passer par l’un ou l’autre des points bleus.
Exemple : je suis sur le point rouge A, A1 se dirige vers B et A2 se dirige vers E. Je choisis le parcours A1 j’arrive donc sur le point rouge B,. B1 se dirige vers le point rouge C. C1 se dirige vers D et C2 se dirige vers E etc.... Bien sûr ceci n’est qu’un exemple et n’est en rien une contrainte. Vous pouvez décider que A1 va vers D ou C etc.. Dans tous les cas il faudra passer par tous les points bleus. Il faut que cela fonctionne quelque soit les choix : que je choisisse de passer d’abord par A1 ou par A2. A l’arrivée sur chaque point rouge le passage par le point bleu doit être aléatoire. (on ne peut pas forcer le passage par A1 ou A2.

Merci d'avance pour votre aide.

[Dlzlogic]

Bonjour,
En fait j'ai pas très bien compris.
Ou bien c'est une application de la théorie des graphes, ou bien c'est une utilisation de l'analyse combinatoire, et là il y a un bon moyen de faire une bonne approche avant généralisation, c'est de dessiner un arbre.

[messinmaisoui]

Bonjour Isic

Quel est le problème ?
Proposer toutes les combinaisons de passage possible ?

[ISIC]

Oui le probleme c'est de pouvoir trouver tous les chemins possible.

[ISIC]

Bonjour,
En fait j'ai pas très bien compris.
Ou bien c'est une application de la théorie des graphes, ou bien c'est une utilisation de l'analyse combinatoire, et là il y a un bon moyen de faire une bonne approche avant généralisation, c'est de dessiner un arbre.

Je ne sais pas ce que c'est la théorie des graphes ni une ana;use combinatoire je suis désolée.

[fatal_error]

salut,

avec trois noeuds rouges au lieu des 5, donc A, B et C
on a un chemin de base de la sorte
A,B,C,A,B,C, qui permet de faire passer par tous les noeuds bleus.

Ensuite, apres une majuscule, A par exemple, il faut a_1 ou a_2 (l'un des deux noeuds bleus)

La question est donc dans un premier temps d'agencer les noeuds rouges parmi les 6 emplacements disponibles ce qui donne :
chemins (sans tenir compte des noeuds bleus)

Puis pour le premier A trouve, il y a deux possibilites, il est suivi par a_1 ou a_2 idem pour B et C cad au final le nombre de chemins est

[Doraki]

Je suis pas sûr d'avoir compris.
Il faut compter de combien de façons on peut visiter les points bleus ?
A quoi servent les points rouges ? pourquoi tu ne les effaces pas ?

Tu peux faire un exemple avec juste 2 points rouge et faire la liste des parcours possibles ? il devrait pas y en avoir trop.

[messinmaisoui]

Oui le probleme c'est de pouvoir trouver tous les chemins possible.

D'accord ...

et

Tous ... en les nommant ex : A-A1-E-E2-...
ou juste obtenir le nombre de combinaison (cf fatal_error ) ?

En partant du point A ou de n'importe quel point ?

[ISIC]

D'accord ...

et

Tous ... en les nommant ex : A-A1-E-E2-...
ou juste obtenir le nombre de combinaison (cf fatal_error ) ?

En partant du point A ou de n'importe quel point ?

oui en les nommant.
On peut partir de n'importe quel point. Si c'est trop complexe on peut imposer le point de départ A.

[messinmaisoui]

oui en les nommant.
On peut partir de n'importe quel point. Si c'est trop complexe on peut imposer le point de départ A.

Et le départ de A impérativement ?
J'insiste je sais c'est triste :we:
[EDIT]Grillé

[messinmaisoui]

oui en les nommant.
On peut partir de n'importe quel point. Si c'est trop complexe on peut imposer le point de départ A.

Ok mais tu voudrais quoi exactement ?

La liste de toutes les combinaisons correspondantes à ton exemple précis
5 points rouges + 10 points bleus en rentrant par n'importe lequel de
tes 5 points rouges ...
ou
un algorithme qui te permettrait de générer cette liste
ou
autre chose ... à détailler :hein:

[ISIC]

Et le départ de A impérativement ?
J'insiste je sais c'est triste :we:
[EDIT]Grillé

Non non pas impérativement sauf si cela peut faciliter la tache évidement.

[ISIC]

Ok mais tu voudrais quoi exactement ?

La liste de toutes les combinaisons correspondantes à ton exemple précis
5 points rouges + 10 points bleus en rentrant par n'importe lequel de
tes 5 points rouges ...
ou
un algorithme qui te permettrait de générer cette liste
ou
autre chose ... à détailler :hein:

Je préférerais la premiere solution car il n y aura jamais plus de 5 points rouges.

[ISIC]

Merci pour toutes vos réponses !

En fait, je ne sais pas si nous nous sommes bien exprimés…

Nous ne cherchons pas (oui, nous sommes plusieurs derrière l’écran) à calculer le nombre total de parcours différents possibles.

Nous cherchons ‹simplement› à nous assurer qu’il est possible de passer par tous les points rouges en ne passant qu’une seule fois par chacun des points bleus, et ce pour tous les parcours possibles.
Il n’est pas nécessaire de passer par tous les points bleus. Il n’y a pas de point rouge de départ imposé (sauf si cela ne peut pas fonctionner autrement).

Sachant que :

• il faut passer par un point rouge pour traverser un point bleu,
• un point rouge n’est relié qu’à deux points bleus différents
• chaque point bleu mène à un point rouge.

Voilà, nous espérons être plus clairs…

[fatal_error]

ben ui c'est possible. :hum:
Aa_1Bb_1...E

[messinmaisoui]

Merci pour toutes vos réponses !
...
Nous cherchons ‹simplement› à nous assurer qu’il est possible de passer par tous les points rouges en ne passant qu’une seule fois par chacun des points bleus. Il n’est pas nécessaire de passer par tous les points bleus. Il n’y a pas de point rouge de départ imposé (sauf si cela ne peut pas fonctionner autrement).

Sachant que :

• il faut passer par un point rouge pour traverser un point bleu,
• un point rouge n’est relié qu’à deux points bleus différents
• chaque point bleu mène à un point rouge.

:hein: mais je ne vois pas en quoi ça serait pas possible ...
ça me parait évident vu le peu de contraintes que ça ne puisse pas
se faire ... si encore il y avait des chemins entre les points, des sens,
des croisements à ne prendre qu'une fois etc ...

[nodjim]

ISIC ne nous dit pas si on le droit d'aller en A depuis A1 ou A2. C'est important.
Ensuite, j'ai compris qu'il voulait trouver le nombre de boucles différentes qui passent par tous les points bleus.

[nodjim]

La seule chose que je peux dire est que ta question n'est pas claire.
Si tu veux savoir s'il sera toujours possible de passer au moins une fois par toutes les cases rouges en réalisant un parcours aléatoire la réponse est non évidemment.
Exemple:
A1 B1 A2 B2 A1 on ne passe jamais par C,D ou E.

[nodjim]

Ne serait ce pas la modélisation d'un montage électrique pas hasard ?

[Doraki]

Nous cherchons ‹simplement› à nous assurer qu’il est possible de passer par tous les points rouges en ne passant qu’une seule fois par chacun des points bleus, et ce pour tous les parcours possibles.
Il n’est pas nécessaire de passer par tous les points bleus.

Je comprends encore moins.
c'est quoi un parcours possible ?
ça veut dire quoi, quand on a un parcours possible, qu'il est possible de passer par tous les points rouges et tous les points bleus une seule fois mais pas forcément tous les points bleus ?

Pourquoi tu fais pas :

1. On tire au sort un point bleu parmi ceux qu'on doit encore visiter.
2. On va vers le point rouge associé à ce point bleu.
3. On va à ce point bleu.
4. Goto 1.