Discussion :

[lowkick01]

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 :

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.

[DonQuiche]

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.

[Flodelarab]

Bonjour

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

[tbc92]

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

[zaza576]

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 !

[CliffeCSTL]

Je vois pas où est la difficulté :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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