Vidéo : Binaire, Hanoï et Sierpinski, 2e partie

Grant Sanderson • 3Blue1Brown • Boclips

Binaire, Hanoï et Sierpinski, 2e partie

12:13

Transcription de vidéo

On est de retour ! Ainsi, dans la dernière partie, j’ai montré un moyen de résoudre Tours de Hanoï simplement en comptant en binaire, une solution que j’ai apprise de l’informaticien Keith Schwarz. Si, d’une manière ou d’une autre, vous avez atterri ici sans regarder cela, vous voudrez probablement aller le vérifier. Ici, dans cette vidéo, je voudrais décrire une variante contrainte de ce puzzle et son rapport avec la recherche d’une courbe qui remplisse le triangle de Sierpinski.

KEITH : La variante du problème est que, vous savez, certains disques sont alignés. Vous êtes uniquement autorisé à déplacer un disque d’un axe à un disque adjacent. Et maintenant, la question est de résoudre les tours de Hanoï.

GRANT : Ainsi, par exemple, comme dans un précédent, nous commençons par déplacer le disque zéro vers le disque B. Et le mouvement suivant consistait à déplacer le disque 1 vers le disque C. Mais vous ne pouvez pas le faire car vous ne pouvez pas en mettre un directement vers C.

KEITH : Exactement ! C’est tellement plus compliqué. Mais l’idée de cette version modifiée est toujours similaire. Donc, si je veux déplacer le disque trois, disons que j’essaie de le faire passer de A à C. Donc, comme avant, je ne peux pas déplacer le disque trois à moins que la tour située au — dessus-deux, un et zéro — soit hors de le chemin. Donc, au final, j’aimerais que cette tour ne la bloque pas. Mais il y a deux façons de le bloquer maintenant. Donc, auparavant, il fallait juste ne pas être au top. Maintenant, il ne doit pas seulement ne pas être au sommet, il ne peut pas non plus être adjacent. Donc, vraiment, ce que je veux faire, c’est prendre cette tour de zéro, un, et deux et d’une manière ou d’une autre, je ne sais pas, aller au truc C, puis déplacer le disque trois. Puis retirez-le de C en A. Ensuite, déplacez le disque trois de la broche B sur la broche C. Ensuite, déplacez la tour tout en arrière.

Le plus petit cas se décompose essentiellement de la même manière. Vous le résolvez pour deux disques, déplacez le disque numéro deux, résolvez-le pour deux fois, déplacez le disque numéro deux, puis résolvez encore pour deux disques. Tandis que vous continuez à vous subdiviser dans ce modèle similaire, développez chaque sous-problème dans son propre ensemble de sous-problèmes. Finalement, vous arrivez au plus petit sous-problème de tous, déplacer une tour de taille un, ce qui implique simplement de déplacer deux fois le numéro de disque zéro.

Comme dans le cas sans contrainte, cela vous donnera la solution la plus efficace, car à chaque échelle, vous ne faites que ce que vous devez faire. Vous devez déplacer cette sous-tour avec zéro, un et deux sur la patte C si vous prévoyez de déplacer le disque numéro trois. Et vous devez le ramener à A pour pouvoir déplacer le disque trois. Et vous devez le déplacer tout le chemin de retour en C une troisième fois. Il n’y a tout simplement pas de place pour l’inefficacité une fois que vous avez décomposé en sous-problèmes comme celui-ci. Et tout comme le casse-tête sans contrainte reflétait le modèle de comptage en binaire, la décomposition de ce problème contraint se reflétait en comptant en base trois, également connue sous le nom de ternaire. Ici, prenons un moment pour parler de ce qu’est la troisième base, du rythme de comptage.

Donc, comme vous le savez, notre système de comptage habituel, base 10 a 10 chiffres séparés et binaire, ou base deux, a deux chiffres séparés. Trinaire est donc un système de représentation des nombres dans lequel vous ne disposez que de trois symboles distincts, zéro, un et deux.

KEITH : Je ne sais même pas comment vous appelez ça. Donc, ce n’est pas un peu ; ce n’est pas un chiffre ; est-ce que c’est un trit ? C’est juste que … je pense que nous en avons parlé plus tôt. Comme si ça ne sonnait pas juste.

Ils s’appellent en effet des trits. Mais bon, si cela vous semble un peu dérangeant, demandez simplement à un francophone ce qu’il en est de notre convention d’appel de «bits» à chiffres binaires.

Quoi qu’il en soit, revenons à ce que nous faisions, réfléchissons au rythme de comptage en ternaire. Vous commencez simplement par compter à travers les trits, zéro, un, deux. Ensuite, vous devez passer à une deuxième étape à la place des trois. Ensuite, vous comptez jusqu’à quatre, ce qui correspond à un, un ; cinq, qui est un, deux ; et vous devez revenir à deux, zéro, représentant six. Puis deux, un; deux, deux, à quel point vous devez rouler deux fois à la place des neuf, en écrivant le nombre neuf comme un, zéro, zéro. Tout comme la base deux et la base 10, il existe une certaine auto-similitude à ce motif. À toutes les échelles, il semble que l’on compte jusqu’à un certain montant, que l’on se retourne pour autant, que l’on compte à nouveau, que l’on recommence. Puis en comptant à ce même montant une troisième fois.

Mais c’est le schéma que nous venons de voir avec les tours de Hanoï contraintes. Faites une sous-tâche, faites une sorte de mouvement plus grand, faites une sous-tâche, faites le même mouvement plus grand. Ensuite, faites la sous-tâche une troisième fois. Donc, tout comme le comptage binaire reflète la solution aux tours non contraintes de Hanoï, compter en temps réel va refléter le schéma récursif de résolution des tours contraintes de Hanoï. Cela donne un moyen vraiment agréable et méthodique de résoudre le problème sous contrainte simplement en comptant. À chaque fois que vous ne modifiez que la dernière copie, déplacez le numéro de disque zéro. Donc, pour les deux premiers mouvements lorsque vous comptez un, deux, vous déplacerez le disque zéro. Chaque fois que vous passez une seule fois à la place des trois, par exemple lorsque vous comptez entre deux et trois, représenté par un, zéro, vous déplacez le disque numéro un.

Et en continuant comme ça, vous retourneriez le dernier, bougeriez zéro ; retournez le dernier, déplacez le zéro ; survolez en écrivant deux, zéro ; puis déplacez le disque un. Puis encore deux fois, vous retournez le dernier et déplacez le disque zéro. Ensuite, chaque fois que vous passez deux fois à la place des neuf, vous déplacez le disque numéro deux. Encore une fois, c’est assez amusant de rester assis et de regarder cette pièce. Cela prend un moment, cependant. Pour quatre disques, vous devrez compter jusqu’à deux, deux, deux, deux, ce qui est ternaire de trois à quatre, moins un, ce qui représente 80. Cela signifie que la résolution de ce problème implique 80 étapes. Néanmoins, comme je l’ai dit précédemment, c’est la solution la plus efficace.

KEITH : Mais cela vous donne aussi quelque chose de très cool. Vous pouvez demander : « Combien de configurations différentes existe-t-il pour les tours de Hanoï »?

En fait, prenons un moment pour réfléchir à cela. Combien de configurations totales de disques sur chevilles sont possibles, où les disques sur une cheville donnée doivent être dans un ordre décroissant de taille ? La réponse est de trois puissance quatre, 81 états possibles dans lesquels votre casse-tête peut se situer. Pour voir cela, notez qu’il existe trois choix pour placer le plus gros disque. Ensuite, trois choix d’endroits pour placer le prochain disque le plus volumineux. Et pour chaque disque successif, vous avez trois choix pour l’emplacement.

Et rappelez-vous, ce processus de résolution en comptant en ternaire implique de prendre trois puissance quatre moins une. Ce qui signifie que, du début à la fin, vous allez choisir 81 configurations différentes. Et si vous y réfléchissez, cela ne peut pas frapper une configuration donnée deux fois. Si c’était le cas, il y aurait une solution plus efficace en travaillant jusqu’à la première fois où vous atteignez cette configuration, puis en sautant toutes les informations entre celle-ci et la seconde fois, vous poursuivez.

KEITH : J’ai en quelque sorte un grand tour. Cela ne résoudra pas que les tours de Hanoï. Cela passera par toutes les configurations possibles des disques.

Assez cool, non ? Eh bien, voici où les choses deviennent géniales. Pour ceux qui connaissent les graphiques, ces configurations présentent une très belle structure. Ce que je vais faire est de représenter chacune de ces configurations avec un point, un nœud dans notre graphique. Ensuite, nous disons que deux configurations différentes sont connectées si vous pouviez passer de l’une à l’autre avec des déménagements légaux de Tours de Hanoï. Et cette fois, je veux dire un mouvement sans contrainte. Donc, les configurations sont toujours considérées comme connectées même si cela nécessite un déplacement de la cheville A à la cheville C. Lorsque vous passez par toutes les configurations de ce type et que vous trouvez toutes les arêtes qui représentent une sorte de déplacement, la structure de la courbe pour Tours de Hanoï a cette forme étrangement familière.

Zoomons dessus et réfléchissons à l’origine de ce schéma. Par exemple, ce nœud représentant ici l’état de départ avec tous les disques de la cheville A va être connecté à celui-ci, résultat du déplacement du disque zéro sur la cheville B. Ces deux éléments sont connectés à celui-ci, qui est le résultat du déplacement du disque de zéro à la cheville C. Ces trois configurations constituent un petit triangle dans notre graphique. C’est-à-dire que les trois configurations sont toutes connectées les unes aux autres. En fait, n’importe quelle configuration fera partie de l’un de ces triangles quelque part dans la courbe. Vous ne considérez que ce qui se passe lorsque vous vous déplacez librement autour du numéro de disque zéro parmi les trois piquets.

Maintenant, pour comprendre comment ces petites îles triangulaires sont interconnectées, examinez ces deux nœuds. Ils ne diffèrent que par un mouvement du disque numéro un de la cheville A à la cheville C. Ils vont donc être reliés par un bord. Ce bord est une sorte de pont entre deux îles triangulaires différentes. En fait, ces deux triangles, ainsi que celui-ci, forment une sorte de méta-triangle quand on considère tous les mouvements du premier disque. Chaque petit groupe de trois nœuds représente ici une position différente pour le disque numéro un. Et le motif tri-force dans son ensemble représente toutes les configurations que vous pouvez obtenir en vous déplaçant autour des disques numéro un ou zéro.

Et de manière similaire, un mouvement du disque numéro deux vous donne un pont entre l’un de ces modèles de tri-force et un nouveau. Et les trois endroits possibles où le disque deux peut vivre nous donnent ces trois motifs de tri-force distincts, reliés chacun par un petit pont. Le fait qu’il n’y ait que deux nœuds dans l’un de ces motifs tri-force dont le bord sort du motif lui-même est simplement le reflet du fait qu’il est difficile de déplacer le disque numéro deux. Cela ne se produit que dans les configurations très spéciales où le disque un et le disque zéro sont tous deux hors de propos.

À mesure que vous envisagez de plus en plus de disques, ce modèle continue. La structure graphique des configurations des tours de Hanoï est un grand triangle de Sierpinski. N’est-ce pas fou ?! Voyons maintenant ce que cela signifie pour cette méthode de résolution du problème contraint en comptant, en temps voulu, dans toutes les configurations possibles. Cela nous donnera un moyen de parcourir ce graphique et d’atteindre chaque nœud une fois et une seule fois. C’est fou pour moi. Si vous ne regardez que la structure du graphe de Sierpinski, il n’est pas clair au début qu’un tel chemin est même possible. Et pourtant, nous en avons trouvé un en comptant. Si ce n’est pas beau, je ne sais pas ce que c’est.

Bien ! Donc, pour cette dernière animation, je vais montrer le chemin parcourant le graphe de Sierpinski en fonction de la manière dont le comptage ternaire résout le casse-tête contraint des Tours de Hanoï. Si je supprime ce graphique uniquement pour souligner le chemin, voici à quoi il ressemble pour les ordres les plus élevés, ce qui correspond aux tours de Hanoï avec de plus en plus de disques. Ce que vous voyez est très similaire à l’idée de courbes de remplissage d’espace dont j’ai parlé dans la vidéo de la courbe de Hilbert. C’est juste que la limite ici remplit une fractale au lieu du carré. N’est-ce pas fou ?! Vous pouvez avoir une courbe qui remplit le triangle de Sierpinski, ce que je ne considère absolument pas comme une chose de type courbe.

Nagwa utilise des cookies pour vous garantir la meilleure expérience sur notre site. En savoir plus sur notre Politique de Confidentialité.