Salut les gars,

Je me prend la tête sur un problème depuis ce matin et je n'arrive pas à trouver une solution.

Je vous explique le problème, j'ai un graphe avec un point de départ et un point d'arrivé, chaque "nœud" représente une salle, chaque liaison un tube dans lequel peuvent passer les fourmis.

Un nombre N de fourmis est placé dans la salle de départ, le but de l'exercice (qui fais partie d'un problème de programmation) est de les emmener à la salle d'arrivé en le moins de tours possible.

Les chemins ne se croisent jamais, il ne peut y avoir qu'une fourmis par salle à la fois (sauf au départ et à l'arrivé), chaque tours fais avancer toutes les fourmis à la salle suivante et si une salle à plusieurs liaisons (par exemple le départ ou l'arrivée) on peut envoyer simultanément une fourmis dans chacune de ses liaisons dans le même tours.

Voici un exemple:

On voit ici que si on à 2 fourmis de départ, il vaut mieux toutes les faire passer par le chemins rouge (ce qui ferais un total de 3tours).

En revanche si on passe à 3 fourmis au départ on remarque qu'il vaut mieux les séparer dans les deux chemins (ici 1 dans le chemin vert et 2 dans le rouge).

La question est donc de savoir comment déterminer le nombre de fourmis à envoyer dans chaque tube pour que le nombre de tours final soit le plus bas possible.

J'ai déjà trouvé la relation qui donne le nombre de tour d'un chemins en fonction de taille du chemins et du nombre de fourmis:

nb_de_tour = nb_fourmis + longueur_chemins - 1

Mais je n'arrive pas à trouver une relation qui me donnerais le nombre de fourmis à envoyé dans chaque chemins en fonction du nombre de fourmis totale :/

Des idées ? 

PS: J'ai à ma disposition le nombre total de chemins ainsi que leurs longueurs respectives

Déjà, avec 2 fourmis, on a 2 solutions : 2 dans le chemin rouge, ou 1 dans chaque.

Bon, pour rédiger la relation que tu cherches, ca ne va pas être si facile à rédiger, par contre on peut toujours analyser le problème.

Qu'est-ce qui fait la différence entre un chemin A de longueur 5 et un chemin B de longueur 2 ?

3 tours de plus pour que la fourmi fasse le trajet. Ce qui veut dire que pour les 3 premières fourmis, il vaut mieux prendre le B, et pour toutes les fourmis d'après, peu importe car chaque chemin leur prendre autant de temps. Soit 3 tours d'attente avant le chemin B ou 3 tours de plus pour parcourir le chemin A.

En gros, sur le total, tu auras forcément 3 fourmis de plus qui seront passés par le chemin B. Ou à 1 d'écart car la dernière fourmis, si elle est seule dans la case de départ peut prendre l'importe quel chemin au choix, ça ne changera pas le temps.

Imaginons maintenant 5 chemins et leur longueur respective :

A - 1

B - 5

C - 3

D - 2

E - 1

On aura, sur le même principe, 4 fourmis de plus qui passeront par A ou E que pour le B. 2 de plus que pour le C, et  de plus que pour le D.

Du coup, si on note xA le nombre de fourmis qui passe par A, xB le nombre de fourmis qui passent par B, etc....

xA - 4 = xB

xA - 2 = xC

xA - 1 = xD

xA = xE

On a donc pour le moment, 4 équations à 5 inconnus.... Sauf qu'il nous manque le nombre total de fourmis, x qui vaut :

x = xA + xB + xC + xD + xE

=> x = 5*xA - 7

Si on prend la valeur de x = 100, on trouve donc qui faut passer 21 fourmis par A ou par E, 17 par B, 19 par C et 20 par D. Ce qui fait un total de 98 fourmis, les 2 dernières passent par où elles veulent.

Reste à formaliser tout ça.

Tu as ici un graph très simple, avec seulement 2 chemins. Ta solution d'explorer toutes les solutions possibles et de conserver celle qui se réalise en le moins de tours est donc tenable. Mais quand tu commenceras à avoir bien plus de chemins (ce qui sera sûrement le cas lors de la correction de ton projet), tu ne pourras plus te le permettre.

Sinon j'ai déjà répondu à un sujet similaire la semaine dernière : https://openclassrooms.com/forum/sujet/algorithmie-pathfinding