Optimiser des déplacements

Bonjour,

Etant complètement novice en programmation et en algorithmes, j'aurais aimé avoir des pistes concernant l’élaboration en python d'un algorithme permettant l'optimisation de déplacements de billes selon le schéma joint :
Pièce jointe 199087
les contraintes sont les suivantes :

les déplacements des billes noires se font horizontalement et verticalement, pas en diagonale
les billes entrent par A1, les billes a éliminer sortent par D4
le but étant de limiter le nombre de déplacements, de trouver le ou les chemins les plus courts pour chaque billes.

Bonjour.

Le débit est limité par l'unique point de sortie et il n'y a pas d'obstacles. Or une stratégie naïve permettra toujours de faire sortir une bille à chaque tour (sauf espaces initiaux). Elle est donc optimale.

Stratégie : vers le bas si possible, sinon vers la droite, sinon on passe à la bille suivante.

Bonjour :coucou:

Parler de stratégie sur ce genre de quadrillage est un petit peu exagéré puisque tous les mouvements se valent.
Exemple:
Trajet de A1 à C3
=A1-A2-A3-B3-C3
=A1-A2-B2-B3-C3
=A1-A2-B2-C2-C3
=A1-B1-B2-B3-C3
=A1-B1-B2-C2-C3
=A1-B1-C1-C2-C3

Toujours la même longueur

par curiosité, c'est un exercice de quel niveau ? L1 info ?

Hello,

est-ce que le fait d'implémenter un déplacement naïf peut être jugé par un niveau d'étude précis ?
Si oui, je dirais :
- le déplacement en soi est quasi-inné. Même un gamin de maternelle lambda éviterait le maximum d'obstacles et choisirait toujours le plus court chemin pour aller d'un point A à un point B.
- tu as des algorithmes que tu peux éventuellement voir dès bac+2 et ++ qui te permettent, au travers de graphes par exemple, d'effectuer des déplacements. Je cite parcours du plus court chemin dans un graphe, distance Manhattan (https://fr.wikipedia.org/wiki/Distance_de_Manhattan) ...

Ensuite, il faut ordonnancer le tout pour qu'aucune de tes billes ne bloque les autres. Dans quel ordre vas tu traiter tes billes ? Mon choix se porterait sur :
- pour chaque bille
--- calculer la distance de la bille la plus proche de la sortie
--- prendre cette bille et la faire sortir via la distance Manhattan

N'hésite pas à nous donner ton état d'avancement car c'est un sujet sympa ! Et si tu as d'autres questions, nous sommes là pour t'aider !

Je vois pas où est la difficulté :

Code:

---

1 2 3

Tant qu'il reste des billes Prendre la bille la plus proche de la sortie Faire sortir cette bille

---