Algorithme de rangement

Bonjour ,
Cela fait quelques jours que je travaille sur le problème suivant :
J'ai plusieurs cellules dans chaque cellule il y a quatre places , chaque place peut être soit vide soit contenant un carton. L'ensemble de mes cartons sont numérotés de 1 à n et dispatchés dans le désordre dans ces différentes cellules.
L'objet de l'exercice est de trouver une méthode permettant d'utiliser les places vides afin de réarranger tous les cartons pour pouvoir les sortir de le bon ordre ( 1-2....n).
NB : Si une cellule est pleine on peut pas accéder au carton qui est dans le fond, pour accéder à ce carton là il faudra déplacer les trois autres.

J'ai essayé dans un premier temps de réduire mon exercice. J'ai considérer que j'ai 8 cartons numérotés de 1 à 8 et répartis aléatoirement sur les 4 cellules (4*4 places). Mais il m'est toujours difficile de poser le problème mathématiquement.
Je suis ouvert à toutes propositions. Je vous remercie par avance.
(Ci joint un document permettant de mieux visualiser le problème)

Bonjour,

Rapidement, ça ressemble au problème des tours de Hanoï, as tu regardé de ce coté là si il n'y avait pas des solutions qui conviennent à ton problème ?

Bonjour Golgotha,

Je tiens à vous remercier de votre retour.
Je vais y jeter un coup d’œil, à première vue c'est exactement le même problème. Je vous tiendrai informé.

Merci infiniment.

J'ai regardé le problème des Tours de Haroi. Mais ce n'est pas tout à fait mon problème l'objectif est le même certes la seule différence c'est que dans les Tours de Haroi à l'état initial on a une cellule de cartons déjà rangée de 1 à 8 sauf qu'en réalité c'est pas le cas.
Voici un exemple :
------------------------------------------------
* A l'instant t0, j'ai ceci :
Celulle 1 : 1,9,0,0
Celulle 2 : 2,6,3,0
Celulle 3 : 4,5,8,7
Celulle 4 : 0,0,0,0

* Trouver un algorithme afin d'obtenir :
Celulle 1 : 4,3,2,1
Celulle 2 : 8,7,6,5
Celulle 3 : 0,0,0,0
Celulle 4 : 0,0,0,0
ou bien
Celulle 1 : 7,6,3,1
Celulle 2 : 8,5,4,2
Celulle 3 : 0,0,0,0
Celulle 4 : 0,0,0,0
etc ... ( L'objectif ça serait de pouvoir sortir tous les cartons dans l'ordre).
------------------------------------------------------

Contrairement à Tours de Haroi :
Initialement on a :
Celulle 1 : 4,3,2,1
Celulle 2 : 0,0,0,0
Celulle 3 : 0,0,0,0

Après le calcul on obtient :
Celulle 1 : 0,0,0,0
Celulle 2 : 0,0,0,0
Celulle 3 : 4,3,2,1

-------------------------------------

Je vous remercie !

Si tu as k places par cellule et moins de k places libre au total, tu n'es pas sûr qu'il existe une solution.
Par exemple, si tu as :
(1, 2, 3, 4)
(5, _, _, _)
Tu ne peux rien faire.

S'il existe k places libres (ou plus), alors la solution est triviale puisque tu peux aller chercher le carton que tu veux, et le placer où tu veux (il me semble).

Si j'ai bien compris, ton objectif n'est pas forcément de les ordonner de manière stricte, mais juste t'assurer que les cartons "plus au fond" ont un numéro plus grand que ceux "devant".

Autrement dit, pour une cellule (a1, a2, a3, a4) tu veux que a1 <= a2 <= a3 <= a4 (avec pas de carton = +inf pour simplifier).

Est-ce que tu veux minimiser le déplacement des cartons ?

Si tu veux poser le problème de façon mathématique, tu peux dire que tu as des k-uplets qui contiennent soient un entier soit un élément ⊥ (pas de carton) et définir l'opération de déplacement d'un carton. Mais je ne suis pas sûr que ça aide. :)

Celelibi,
Je tiens à vous remercie de votre retour.
L'objectif est de ranger les cartons de telle sorte de pouvoir les sortir dans l'ordre et aussi de minimiser le déplacement des cartons.
Alors existerai t il une fonction à minimiser ça risquerait d'être difficile de la trouver :) !
Une précision vous aviez dit que la solution était triviale. Certes pour l'exemple que j'ai cité mais en réalité j'aurai affaire à une centaine de cellules contenant des cartons que je dois ranger. Cela devient vite complexe .

Je vous remercie !

Tiens, en fait j'avais pas vu dans l'exemple que j'ai donné qu'il existe une solution :
(1, _, _, _)
(5, 4, 3, 2)

Dans cet exemple il ne devrait pas y avoir de solution :
(1, 3, _, _)
(2, _, _, _)

Du coup je ne suis même plus sûr des conditions que j'ai donne dans mon message précédent puisqu'ici avec 2k-3 places libres il n'y a pas de solution. Et je pense qu'à partir de 2k-1 places libres, tu trouves forcément une solution puisque tu peux forcément libérer la place du carton que tu veux placer, et tu peux aussi libérer le carton que tu veux placer.


Oui, d'ailleurs j'ai dit de la merde, ce que tu veux c'est que toutes tes cellules (a1, a2, a3, a4) respectent a1 >= a2 >= a3 >= a4 avec pas de carton = 0. Parce que tu sors les cartons sur la droite.

Le problème de trouver le nombre de déplacement minimal m'a l'air d'être NP-Hard. Donc soit tu as des heuristiques pour trouver une solution "correcte" sans être sûr que c'est la meilleure, soit tu trouves la meilleur solution dans un temps exponentiel.

Exactement, pour l'exemple que vous aviez cité la solution est triviale.
En réalité mon objectif serait de gérer un stock contenant n cellules ( n sera de l'ordre de 100) avant de lancer mon calcul je suppose que j'aurai k cellules complétement vides (Une vingtaine voir une trentaine) qui vont me permettre de ranger mes cartons. Les n-k cellules sont occupées (peuvent contenir soit 1,2,3 ou 4 cartons).
Effectivement, implémenter une heuristique reste la meilleure solution quand on augmente la taille le problème devient horriblement complexe. J'ai pensé à une méthode de type Recuit Simulé, mais je n'ai pas la moindre de comment je pourrai l'appliquer à ce cas ci.
- Par contre je sais pas comment vous aviez calculé le nombre minimal de places nécessaires ?
Merci encore !

Après quelques recherches et grâce à l'indication de Golgotha, j'ai réalisé que l'algorithme de Tours de Hanoï était valable même quand la tour de départ est désordonnée ! La condition serait pour ranger une cellule j'aurai besoin de deux cellules vides , c'est condition qui est souvent vérifiée. Donc l'algorithme est complétement adaptable à mon problème.

Merci à Golgotha et Celibi !

Citation:

---

Envoyé par Amiral56

- Par contre je sais pas comment vous aviez calculé le nombre minimal de places nécessaires ?
Merci encore !

---

Ce n'est pas le nombre minimal de cellules nécessaire, c'est une borne sup du nombre minimal de cellules vides nécessaires.

Bien, pour calculer ça, j'ai choisi un algo :
1) Enlever tous les cartons devant celui que je veux déplacer
2) Déplacer tous les cartons qui m'empêchent de placer le carton où je veux
3) Placer le carton rendu accessible en 1) dans la place rendue libre en 2)

Par exemple :
(X, Y, Z, _) <-- a places occupées et k-a places libres (k étant le nombre de places par cellule)
(1, W, _, _) <-- 1+b places occupées et k-(1+b) places libres
(...)
Et on va dire que je veux placer le carton 1 à la place de X.
Pour l'étape 1 je vais devoir déplacer b cartons dans des places libres ailleurs. Pour l'étape 2 je vais devoir déplacer a cartons dans des places libres ailleurs.
Il me faut donc a+b places libres en plus de celles que j'avait déjà à la fin des deux cellules.
Il m'en faut donc au total a+b+k-a+k-(b+1) = 2k-1.

Donc si j'ai 2k-1 places libres, je sais que je pourrai toujours appliquer cet algo.
Et je sais que vu l'exemple dans un message précédent, il n'existe pas toujours de solution pour 2k-3 places libres. Autrement dit le nombre minimal de places libres pour avoir toujours une solution est soit 2k-1 soit 2k-2.

Il y a quelque chose qui m'échappe:
Remarque :
Vous prenez le nombres de places ( Occupées + vides ) par cellule comme étant un paramètre k , or le nombre de places est fixé à 4.

Ce qui me choque c'est que le nombre de places vides nécessaires est indépendant de a et de b !! Ce qui me parait très bizarre !

Je vous rappelle que k est fixé à 4 places le seul paramètre ici c'est le nombre de places occupés.

Qu'est ce que vous en pensez ?

Oui, c'est juste une généralisation, j'ai pris k et pas 4. Parce que je trouve que ça serait dommage de se limiter à un cas particulier. :)

Oui, le nombre de places libres nécessaire est indépendant de k. Forcément, si une cellule est "moins pleine" elle contient des places libres qu'il faut compter.
Tu peux aussi chercher quel serait le pire cas (celui qui demande le plus de places libres) de l'algo que j'ai proposé précédemment.

Ça serait quelque chose du genre :
(W, X, Y, Z)
(1, A, B, C)

Pour pouvoir placer 1 à la place de W, il faut 2*k-1 places libres. Justement, comment être sûr que c'est "le pire cas" ? Est-ce que, s'il restait des places libres à la fin des cellules 1 et 2 ça ne viendrait pas s'ajouter au nombre de places libre total qu'il faut ? D'où la formulation un peu plus générale de mon précédent message.


Sinon, côté algo, tu peux peut-être commencer par appliquer un algo bête qui trouve forcément une solution et ensuite essayer de lui appliquer des transformations pour essayer de rendre le nombre de déplacement plus faible.
Le plus dur étant de trouver les transformations forcément faisables qui réduisent (ou peuvent potentiellement amener à pouvoir réduire) le nombre de déplacement.

Effectivement, c'est ce que j'ai fait dans un premier temps. J'ai appliquer un algorithme de tri dans chacune des cellules.
Exemple :
t0 : (1,3,8,7)
(5,4,2,6)
t1: (8,7,3,1)
(6,5,4,2)
Ce qui me permet de sortir dans l'ordre 1 puis 2 puis 3 .... puis 8. Ce qui est gênant c'est le nombre de déplacements il est très grand. Pour ranger deux cellules j'avais besoin d'à peu près 16 mouvements.
En faisant un algorithme de tri sur chaque cellule on obtient une et une seule combinaison qui satisfait l'ordre de sortie. Or ces combinaisons il y en a énormément :
4321
8765
------
8721
6543
------
etc...
J'ai essayé d'écrire mes cellules sous forme matricielle et trouvé une relation entre les termes de cette matrice. Je sais pas je patauge ....

Merci !

Je pense que trier les cellules est aussi un bon algorithme.
Ça nécessite k ( = 4) cellules ayant au moins une place libre. Et tu fais au pire 2k déplacements.

Donc pour N cartons, cet algo est en O(N). On peut difficilement faire mieux en terme d'ordre de grandeur de complexité.

Du coup je vois pas ce que tu veux de plus. Tu veux minimiser encore le nombre de déplacements ?

Oui je suis d'accord avec toi l'algorithme de tri de chacune des cellules donne un résultat satisfaisant ! :)
J'étais un peu exigeant de vouloir minimiser le nombre de déplacements cela risque d'être très compliqué et je ne suis pas sur qu'il puisse donner un résultat inférieur à 2k déplacements.

En tout cas merci beaucoup.

:)