Tours de HanoiSeuls les paresseux n'ont pas écrit sur le célèbre jeu d'Eduard Luc sur Habré. Il semble que toutes les couvertures soient arrachées et qu'il n'est plus possible d'ajouter quelque chose sur l'algorithme. Mais non, ce sujet a des ressources cachées. Aujourd'hui, en particulier, nous allons refaire l'algorithme pour résoudre ce puzzle en une sorte complète. (Pourquoi? Juste pour le plaisir. Vendredi possible.)
Cet article est dédié à la mémoire du véritable gourou de la programmation Andrei Mrrl Astrelin, qui m'a expliqué cet algorithme simplement et intelligiblement. Le pseudo-code ci-dessous est le texte de sa paternité.
Dans le casse-tête classique, les disques du premier pôle sont initialement commandés. Mais nous allons leur permettre d'être enfilés dans n'importe quel ordre.
De plus, les tailles de disque sont supposées uniques. Nous ne nous accrocherons pas à cette restriction et n'autoriserons pas les répétitions.
Si vous n'autorisez que ces deux libertés, les conditions initiales du puzzle peuvent être interprétées comme un tableau (les disques sont des nombres), et la tâche se résume au fait que ce tableau doit être trié.
Les conditions restantes nous ne changeons (presque) pas:
- Nous avons deux pôles auxiliaires (une paire de tableaux vides).
- Nous pouvons transférer les disques un par un.
- Placer uniquement les plus petits sur les plus grands (puisque nous avons autorisé les mêmes tailles de disque, nous pouvons également placer le disque déplacé sur d'autres de la même taille).
- Nous avons le droit de comparer un disque portable avec uniquement les disques supérieurs (c'est-à-dire que les 3 baies sont des piles).
Notre tâche: prendre l'algorithme de puzzle récursif classique ...
def hanoi(n, source, helper, target): if n > 0: hanoi(n - 1, source, target, helper) if source: target.append(source.pop()) hanoi(n - 1, helper, source, target)
... et transformez-le en tri!
En fait, du fait que nous avons autorisé le désordre initial et les répétitions pour la taille des disques - rien n'a essentiellement changé depuis. Dans l'ensemble, le problème est résolu de la même manière récursive classique. La chose la plus importante à comprendre est que tous les mouvements du disque sont divisés en plusieurs étapes, chacune étant une miniature classique de Hanoi.
Autrement dit, à chaque étape, nous ne considérons pas tous les disques disponibles, mais uniquement la totalité de ceux qui satisfont aux anciennes conditions. Après avoir trié ce petit ensemble par des classiques, nous rapprocherons l'état général du système du puzzle classique. Ensuite, nous reprenons l'ensemble de disques qui correspond aux classiques et appliquons à nouveau l'algorithme bien connu. Et cet ensemble sera plus grand qu'à l'étape précédente! Et donc nous répétons jusqu'à ce que tous les disques sur tous les pôles deviennent soudainement différents de l'état classique.
Le système qui a été violé initialement (par le fait que les disques ne sont pas commandés en entrée) est auto-réparé à chaque itération.
Quant à la résolution des répétitions, cela n'a pas d'importance du tout. Parce que les disques identiques consécutifs, nous nous déplaçons simplement comme un seul disque.
Algorithme
Nous appelons les colonnes
A ,
B ,
C (
A au début n'est pas vide).
Nous introduisons les opérations:
A ->
C () - déplacer un disque de
A à
C.top (A) ,
top (C) - la taille du disque supérieur
A ou
C. Si la colonne est vide, alors cette taille =
MaxInt .
B ->
C (
K ) - passer de
B à
C tous les disques dont la taille est inférieure à
K (nous pouvons le faire si les disques supérieurs
A et
C ne
sont pas inférieurs à
K ).
swap () - réorganise les colonnes
B et
C (ou renommez-les - peu importe où se trouvent les disques).
while (
A ) - boucle jusqu'à ce que
A soit vide.
Ensuite, l'algorithme suivant fonctionne:
©
MrrlDifficulté
Dans le pire des cas, le tri a tendance à être complexe dans le temps pour l'algorithme classique, qui, bien que simple et élégant, est en même temps au maximum inefficace. Quant aux meilleurs et moyens, j'ai du mal à assumer.
Quant à la mémoire, on peut dire que si la récursivité est utilisée, alors les coûts seront correspondants.
Implémentation
Je n'ai pas écrit ma propre version en Python (je le ferai plus tard). Cependant, dans la section «Liens» ci-dessous, j'ai publié quelques liens où vous pouvez voir les implémentations dans différentes langues. Option particulièrement intéressante en Java. L'auteur n'a pas pris comme base la méthode récursive bien connue pour résoudre le puzzle, mais a construit l'arbre de chemins le plus court. Vraisemblablement, c'est la solution la plus efficace si vous écrivez le tri dans le style de "Tour de Hanoi".
Caractéristiques de l'algorithme
Les références
Tour de HanoiImplémentations:
C ,
Java vs C ++ vs Python ,
Python .
Articles de série:
Dans l'application AlgoLab, ce tri est désormais disponible. Bien qu'il appartient à la classe des tris par insertions, en raison de l'extravagance de l'algorithme, il est placé dans la section "Autres tris". Il existe également une limitation - les nombres dans le tableau trié ne peuvent être que de 1 à 5 (en raison du rendu difficile des disques). D'autres numéros seront toujours remplacés par ceux-ci.
Il y a également une limite à la taille du tableau - pas plus de 20 éléments. Cela se fait uniquement dans votre propre intérêt - si vous prenez un tableau trop grand, il peut arriver que vous deviez le trier jusqu'à un âge très avancé.
Cet article a été écrit avec le soutien d'EDISON Software, une entreprise qui développe professionnellement l' éclairage intelligent des villes et entretient les sites Python.