Problème combinatoire ? [Résolu]

[ISIC]

Je prends un exemple.

Admettons que les points soient ainsi disposés :

A1 -> B1 -> C1 -> D1 -> E1 -> A2 -> E2 -> D2 -> C2 -> B2 -> A <- Fin, toutes les portes bleues (a1 et a2) du point rouge A ont été traversées.

Pour ce parcours, cette disposition fonctionne parfaitement. Cependant, les courts circuits sont possibles :

A1 -> B2 -> A2 -> E1 -> A <- Fin.

Comme tous les points rouges n’ont pas été traversés au moins une fois, cette disposition ne répond pas à notre cahier des charges (si l’on peut dire).

Nous nous demandons s’il existe une disposition particulière qui permettent de traverser tous les points rouges au moins une fois pour tous les parcours possibles.

Sachant que les deux portes bleues d’un même point rouge ne peuvent pointer vers un même point rouge. Exemple : Si a1 -> B , alors a2 -> B impossible.
Par conséquent, la disposition suivante n’est pas possible (rapport au cahier des charges, si l’on peut toujours dire) :
A1 -> B1 -> C1 -> D1 -> E1 -> A2 -> B2 -> C2 -> D2 -> E2 -> A <- Fin.

Merci encore pour votre aide. :-)

[ISIC]

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

Non, est ce que ça aiderait si on expliquait a quoi ça sert ?

[ISIC]

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

Non, ce n’est pas un circuit électrique. Enfin pas exactement. C’est pour la conception d’un dispositif interactif… (mais c’est pas non plus de la prog, c’est juste un problème de logique nous concernant : est-ce qu’on peut envisager notre dispositif ainsi ?).

[Doraki]

Je crois que j'ai compris :

Tu cherches à relier chaque point bleu à un point rouge tel que :
- les deux points bleus issus d'un même point rouge ne sont pas reliés aux mêmes points rouges
- tous les parcours formés par ces liaisons (on commence au point rouge qu'on veut, on va vers un de ses points bleus qu'on a pas encore pris (s'il en reste), puis on continue jusqu'au point rouge à lequel on l'a relié, et on recommence, jusqu'à ce qu'on soit bloqué) doivent passer au moins une fois par chaque point rouge

?

[ISIC]

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.

Notre dispositif ne nous permettra pas cette ‹facilité›. Malheureusement.

En fait, on peut voir les points bleus comme des portes vers un point rouge.

[Dlzlogic]

A mon avis, soit il s'agit qu'un truc théorique, et pour l'instant il ne semble pas qu'on ait compris, soit une logique à appliquer à quelque-chose de précis, et là un peu plus de détail nous aiderait.
Eventuellement pas MP privé à l'un de nous, si c'est confidentiel.

[ISIC]

Je crois que j'ai compris :

Tu cherches à relier chaque point bleu à un point rouge tel que :
- les deux points bleus issus d'un même point rouge ne sont pas reliés aux mêmes points rouges
- tous les parcours (on commence au point rouge qu'on veut, on va vers un de ses points bleus qu'on a pas encore pris (s'il en reste), puis on continue jusqu'au point rouge à lequel on l'a relié, et on recommence, jusqu'à ce qu'on soit bloqué) doivent passer au moins une fois par chaque point rouge

?

Quand vous dites qu’on ‹recommence›, je ne suis pas certain de comprendre. Si on est bloqué, c’est perdu. Il faut trouver la disposition qui ne bloque jamais, en gros. Existe-t-elle seulement ?

[Doraki]

euh si on doit passer au plus 1 fois par chaque point bleu, je vois mal comment tu veux continuer indéfiniment. Ou alors il faut faire une boucle ?

[ISIC]

euh si on doit passer au plus 1 fois par chaque point bleu, je vois mal comment tu veux continuer indéfiniment. Ou alors il faut faire une boucle ?

Pas indéfiniment, en fait. Une fois qu’on est passé sur tous les points rouges, c’est bon. On peut considérer que l’expérience interactive prenne fin à cet instant (c-à-d quand tous les points rouges ont été traversé au moins une fois).

[nodjim]

1 configuration simple te donne l'assurance que ça marche toujours:
tous les i1 vers les (i+1)1 et tous les i2 vers les (i+1)2.

[nodjim]

Ce graphe a l'air de marcher, mais il mérite tout de même d'être vérifié à fond:
A1->B1->C1->D1->E1->A1 et
A2->C2->E2->B2->D2->A2

[ISIC]

Ce graphe a l'air de marcher, mais il mérite tout de même d'être vérifié à fond:
A1->B1->C1->D1->E1->A1 et
A2->C2->E2->B2->D2->A2

Merci nodjim. Je vais essayer un maximum de possibilité…
En fait, en venant ici, nous pensions que cela pouvait-être un problème connu en Mathématique.

Mais, je me rends compte que les joueurs d’Echec non-humains calculent leurs coups de manière empirique, en testant toutes les possibilités sur le plus grand nombre de tour possible.

Notre problème n’est pas aussi complexe, mais, le principe reste le même…

[nodjim]

En fait tous les graphes qui sont établis avec exactement 2 entrées par point rouge marchent (sauf si bien sûr ce sont des boucles sur eux mêmes).

[ISIC]

J’ai pu vérifier votre graphe, elle semble effectivement fonctionner. Et je vois ce que vous voulez dire à propos des deux entrées…

Bon, eh bien nous vous remercions. Vous nous avez bien aidé à comprendre notre problème. Savoir le formuler et l’expliquer, c’est déjà le résoudre, n’est-ce pas ? :-)

Bon vent à vous tous !

[nodjim]

OK, mais attention, je retire ce que j'ai écrit sur la généralisation, c'est une condition nécessaire mais pas forcément suffisante. Le probléme est qu'en 1er geste, on ôte une sortie à A, et donc il pourrait très bien advenir qu'on repasse rapidement sur A (donc -1 entrée et -1 sortie) puis qu'on y aboutisse à nouveau sans être passé par tous les pts rouges.
Dans la configuration donnée, ce n'est pas le cas, il marche tout le temps.