Discussion :

[bizulk]

Bonjour,

je dois piloter un automate qui transporte des charges dans un rayon.Je recherche à implémenter l'algorithme qui permettrait de calculer le prochain mouvement à réaliser de manière à minimiser le cout de l'ensemble des mouvements.
Mes prédécesseurs ont développé un algorithme basé sur scénario, qui a fait preuve de ses limites (l'automate ne bouge pas alors que des mouvements sont en attente).
Je recherche à réprésenter le pb par un graphe et utiliser une méthode générique pour la recherche de solution (recherche de minimas).

Voici un schéma du problème :

|col1-nivNa|col2-nivNa|col3-nivNa|..|coln-nivNa|
-------------------------------------------------
......
-------------------------------------------------
|col1-niv2|col2-niv2|col3-niv2|..|coln-niv2|
-------------------------------------------------
|col1-niv1|col2-niv1|col3-niv1|..|coln-niv1|

|-------|
-[Automate]---------------------------------------------
|-------|

|S1|E1|
|S2|E2|
..
|SNb|ENb|

Les rayons sont des cases sur plusieurs niveaux et plusieurs colonnes (fixés),
Les entrées/sorties vers les rayons sont des piles (de tailles fixes également).


A un instant T donné je peux avoir :

• Des charges à sortir depuis les rayons,
• Des charges à entrer depuis l'entrée vers les rayons,
• Des charges en entrée à ressortir
• à vérifier que des cases rayons sont bien vides.

Pour construire le graphe j'ai déjà en tête les éléments suivants :
un noeud d'un graphe est la localisation de l'automate après avoir exécuté un mouvement,
une arrête entre deux noeud est le cout en distance (unité : colonne) pour l'exécution du mouvement. J'ajoute un delta pour le changement de niveau qui est exécuté en // du changement de colonne.
la construction du graphe est itérative car certains mouvements d'entrée/sortie ne peuvent plus/pas encore être réalisés (après avoir exécuté Nb sortie la sortie est saturée il n'est plus possible d'en faire d'autres, les entrées sont obligatoirement dépilées).

La recherche va passer une et une seule fois par tous les sommets du graphe (sous-graphes), mémoriser le cheminement et le cout global exécuté, et bien sur conserver le cheminement de cout inférieur.

J'ai des pistes pour répondre à la construction du graphe et la recherche de solution. J'ai aussi recherché à identifier le problème comme un pattern mathématique mais sans succès (on n'est pas dans le cas de la recherche de chemin le plus court avec l'algo de Dijkstra).
Voilà si des personnes plus avisées que moi pourrait me donner des pistes

[bizulk]

Bon,
Je décide d'essayer d'implémenter un parcours itératif en profondeur. Avant d'empiler les prochains mouvements je relance une pondération des coûts de mouvements
Lorsque j'ai effectué tous les mouvements je retiens le coût global et le parcours, si au prochain parcours je trouve mieux je le sélectionne.

Ha oui en terme d'évaluation de l'efficacité de la recherche je calcul en amont ces deux indicateurs :
Nombre de mouvement maximum = "nombre de vérifications de cases vides" + "nombres de charges présentes en entrée" + "nombres de places disponibles en sortie".
Nombre de cheminement maximum à évaluer = !(Nombre de mouvement maximum)

[bizulk]

Bon en fait je suis plutôt dans un cadre mixte de recherche de l'arbre recouvrant de poid minimum et du chemin le plus court.
Pour la construction du graphe je voulais me baser sur la matrice d'incidence, tous les sommets étant par défaut chaînés les uns aux autres je pense que c'est la meilleur façon de représenter le problème.
La difficulté porte sur la pile en entrée : je ne sais pas comment poser "à plat" dans le graphe le dépilage obligatoire. Pour l'instant je ne vois que changer le poids de ces sommets lorsque je passe par la tête de pile.