Discussion :

[CosmoKnacki]

Bonjour,

Je dispose de n volumes (disons 8) de tailles à peu prés semblables. Ces tailles sont fixes et non modifiables. Chacun de ces volumes contient de nombreux fichiers de tailles variées. Les 8 volumes sont pleins à craquer et disposent de peu d'espace libre. Autrement dit, l'espace disponible sur un volume peut être inférieur à la taille des plus gros fichiers. Par contre l'espace libre total de tous les volumes est supérieur à la taille du plus gros fichier. La taille de chacun des volumes est aussi supérieure à la taille du plus gros fichier.

Le but du jeu est de réorganiser les fichiers sur ces volumes en les déplaçant d'un volume à l'autre pour aboutir à une répartition bien précise des fichiers (chaque fichier doit se retrouver à la fin sur le volume sur lequel il est censé être).

Deux méthodes me viennent à l'esprit:

• Méthode 1: Par volume.
  Je pars d'un volume, j'expédie par ordre décroissant de taille un maximum de fichiers mal placés vers leurs volumes respectifs lorsque c'est possible (dans le cas contraire je tente le fichier de taille inférieur), puis quand ce n'est plus possible (faute de place sur les autres volumes ou parce qu'il n'y a plus de fichiers mal placés), je fais la même chose avec le volume suivant et ainsi de suite quitte à faire plusieurs fois le tour de tous les volumes.
  
• Méthode 2: Par fichier.
  Partir de la liste de tous les fichiers mal placés (tous volumes confondus) et commencer par placer le plus gros quitte à devoir, dans le pire des cas, déplacer des fichiers vers les mauvais volumes pour faire de la place. La liste est ensuite mise à jour, puis on attaque le plus gros fichier à nouveau, jusqu'à ce que la liste soit vide.

Avec la première méthode, le déplacement de fichier est minimal, mais il y a le risque d'être coincé par deux gros fichiers (ou plus) à cause du manque d'espace libre sur l'un ou l'autre des volumes. (à ce moment là, la méthode 2 pourrait venir à la rescousse).

La deuxième méthode est plus radicale concernant les gros fichiers puisqu'elle les traite en priorité et réussit toujours, par contre elle peut entraîner des déplacements "inutiles".

Connaissez-vous d'autres algorithmes applicables à ce problème et qui minimiseraient le nombre de déplacements de fichiers la quantité de données déplacée?

[CosmoKnacki]

Méthode 3: Par fichier avec récursion.
On part de la liste des fichiers mal placés et on commence par placer le plus gros comme dans la méthode 2.
Disons qu'il se trouve sur le volume A et qu'on veuille le mettre sur le volume B.
Si la place est suffisante on effectue le déplacement et on passe au plus gros fichier suivant.
Si la place est insuffisante, on déplace les plus gros fichiers mal placés (par ordre décroissant) du volume B vers leurs volumes adéquates jusqu'à ce qu'il y ait suffisamment de place.
Si le déplacement d'un de ces fichiers du volume B vers le volume "adéquate", disons C, n'est pas possible car C n'a pas la place suffisante, on recommence la même procédure avec le plus gros fichier mal placé du volume C.
La récursion se poursuit jusqu'à ce qu'un mouvement soit possible.

L'idéal serait de transformer ça en processus itératif pour éviter un dépassement de pile.

Et est-ce que je ne risque pas d'être à nouveau coincé du fait que cette méthode n'autorise pas les "mauvais" déplacements?

[tbc92]

Je propose une méthode 4 :

- Recenser tous les fichiers mal placés, et trier ces fichiers du plus gros au plus petit.

Tant qu'un mouvement est possible :
- rechercher le plus gros fichier qu'on peut déplacer vers son volume Final
- faire le mouvement en question.
Autrement dit, dans cette phase, je ne fais aucun mouvement 'sur-numéraire'.

Si à un moment, j'arrive à un blocage :
- Quel est le volume V où il y a la plus de place disponible ? (en se limitant aux volumes qui sont sensés recevoir au moins un nouveau fichier)
- Quel est le plus gros fichier F sensé aller dans ce volume, mais pas encore à la bonne place ? (Variante, on prend un fichier F de taille moyenne)
- Quel est l'espace manquant pour mettre ce fichier F dans ce volume V ?
- On déplace des fichiers de V vers un autre volume au hasard, prioritairement des fichiers qui ne devraient pas être dans V, puis si nécessaire, des fichiers sensés être dans V , jusqu'à pouvoir déplacer le fichier F sélectionné dans son volume Final.
- On déplace F vers son volume Final
Et on reprend l'algorithme principal.


On peut avoir des blocages.
Mais avec les contraintes que tu donnes, il y a des situations où aucun algorithme ne va convenir.

Exemple :
Tu as n volumes qui font tous environ 10 ou 12 Go.
Dans chaque volume, tu as un fichier de 7 ou 8 Go, plus des fichiers annexes plus petits.
Tous les fichiers sont mal placés.

Problème : tu ne pourras jamais déplacer les fichiers de 7 ou 8 Go
Donc aucun algorithme ne pourra convenir.

[tbc92]

En y réfléchissant un peu plus, c'est probablement plus compliqué.
L'information 'volumes plein à craquer' est importante.

Si l'espace total vide est assez important (disons 2% pour fixer les idées), on doit pouvoir y aller en confiance (la méthode que je proposais), et on aura peu besoin de la procédure 'B'.
Mais si l'espace total vide est très petit, on est en fait dans de la combinatoire. Ca devient comme une énigme à résoudre. Un peu comme l'énige des tours de Hanoi ou différents jeux sur le thème du blocage.
Il faut commencer par le plus gros fichier : comment faire en sorte que le plus gros fichier mal placé aille dans le bon volume. Mais pour résoudre cette énigme, il faut trouver le cheminement total, s'assurer que les mouvements sont les bons... puis faire effectivement les mouvements.