y a-t-il une solution pour les tours de Hanoi dont le temps de fonctionnement est inférieur à O (2 n ) où n est le nombre de disques bouger? Ma solution prend O (2 n ) heure. En outre, la solution ci-dessous est avec la récursivité. Pouvons-nous utiliser la programmation dynamique avec le concept de mémoisation pour résoudre ceci dans une fois de moins? aussi, y a-t-il des variations du même problème? mystack est une version étendue de de la pile classe en java qui ajoute un champ nom et accessoir.
5 Réponses :
Étant donné que la résolution des tours de Hanoi prend toujours 2 ^ n - 1 marches ... Non, vous n'allez pas trouver un algorithme plus rapide, car il prend o (2 ^ n) juste pour imprimer les étapes, beaucoup moins les calculer.
Je ne prouverai pas (comme Stephen l'a fait), mais je vais essayer d'expliquer intuitivement que 2 ^ n-1 sont min: Dans chaque état, il n'y a que trois mouvements possibles pour les disques. Représenter l'état actuel comme commandé SEQ (1, 1, .., 1) tel que le premier numéro indique que le disque de largeurs est et le dernier numéro indique où le plus petit disque est. (1, 1, .., 1) signifie que tous les disques sont allés à la position 1. Aussi de (1, 1, ..1) Il n'y a que deux états descendants: (1, 1, ... 2) et ( 1, 1, .... 3). De (1, 1, ... 2) Il existe trois états descendants:
Si vous continuez, vous obtiendrez un graphique pour lequel les nœuds sont les états possibles et les bords (transitions) sont des "mouvements de disque".
Vous obtiendrez une image comme indiqué ci-dessous (si vous continuez, il ressemblera à un triangle et au sommet des sommets (1, 1, ... 1), (2, 2 ,.2), (3, 3, ... 3)). Le nombre d'étapes est en réalité le chemin du graphique.
Si vous marchez le long du bord du triangle, le nombre d'étapes dans 2 ^ n-1. Tous les autres chemins ont la même longueur ou plus longtemps.
Si vous utilisez la stratégie: déplacez tous les disques, à l'exception du plus grand à la place 3, puis déplacez les larges sur 2 et déplacez enfin tout le formulaire 3 à 2, la formule peut être conçue de la manière suivante:
f (n) =
f (n -1) // déplace tout sauf de 1 à 3
+ 1 // Déplacer le plus grand de 1 à 2
+ F (N -1) // Déplacer tous de 3 à 2
->
F (n) = 1+ 2 * F (N-1)
La solution de cette équation récurrente vous donne le nombre d'étapes requises par cette stratégie (qui se trouve être le nombre minimum d'étapes)
La solution aux tours de Hanoi est inévitable 2 n . Dans une solution de programmation dynamique, toutefois, chaque sous-programme n'est calculé qu'une seule fois, puis le problème est résolu en combinant la première solution de sous-globe, le déplacement actuel du disque et la deuxième solution de sous-programme.
Ainsi, il existe deux composants dans la génération de chaque solution: allouant la mémoire de la solution actuelle, puis remplissez cette mémoire. L'allocation de la mémoire est approximativement indépendante de la taille de la mémoire allouée et constitue le composant coûteux. La copie de la mémoire est linéaire de la taille de la mémoire copiée, ce qui, bien que rapide, est exponentielle en N comme solution aux tours.
Time = C 1 * N + C 2 * 2 N , où c 1 > 2 . C'est-à-dire, il commence linéaire et se termine exponentielle.
Lien vers l'article figurant dans l'article SIGCSE de ACM inadades Magazine (septembre 2012)
Excellente perspicacité pour ce sujet! Au début, je ne suis pas tout à fait convanencé, jusqu'à ce que je l'applique moi-même avec l'inspiration de Ce site web trouvé par Recherche Google , puis j'ai commencé à réaliser à la fois le programme exemple et le répondeur est la même personne. Merci, @ Tim-Rolfe! Je me sens chanceux de pouvoir suivre votre trace sur le Web. :-)
Les tours standard de Hanoi Problange traitent de 3 piquets.
Cependant, si nous avons des k-piquets, la complexité de temps serait O (2 ^ (N / (K-2))).
J'ai résolu ce problème avec 4 piquets et 5 piquets et la complexité du temps résultait d'O (2 ^ (n / 2)) et O (2 ^ (n / 3)) respectivement
Celui-ci est d'environ 7% plus rapide que la récursive. Il stocke les mouvements dans une liste afin que vous puissiez l'utiliser après autrement, vous pouvez mettre un impression si vous préférez et supprimez le conteneur.
```
unsigned long i;
static const int MAXNUMBEROFDISKS = 32;
vector<int> pow2Vec;
uint_fast32_t mPinFrom = 0;
uint_fast32_t mNumDisk = 0;
unsigned long numDiskLong = 0;
uint_fast32_t mOffset[MAXNUMBEROFDISKS];
uint_fast32_t mDir[MAXNUMBEROFDISKS] = { 0 };
uint_fast32_t mPositionDisk[MAXNUMBEROFDISKS] = { 0 };
const uint_fast32_t mRedirectArr[5] = { 2, 0, 1, 2, 0 };
Algos::Algos()
{
for (int i = 0; i < MAXNUMBEROFDISKS; ++i)
{
pow2Vec.push_back(pow(2, i));
mOffset[i] = 1;
}
for (int i = 1; i < MAXNUMBEROFDISKS; i += 2)
{
mDir[i] = 2;
}
mOffset[0] = 0;
}
void Algos::calculListBinExperiment(vector<tuple<int, int, int>>& listeFinale, int nbDisk)
{
listeFinale.resize(pow2Vec[nbDisk] - 1);
_BitScanForward(&i, nbDisk);
for (int noCoup = 1; noCoup < pow2Vec[nbDisk] ; ++noCoup)
{
_BitScanForward(&numDiskLong, noCoup);
mNumDisk = numDiskLong;
mPinFrom = mPositionDisk[mNumDisk];
mPositionDisk[mNumDisk] = mRedirectArr[mPositionDisk[mNumDisk] + mDir[mNumDisk +
mOffset[i]]];
listeFinale[noCoup - 1] = make_tuple(mNumDisk, mPinFrom, mPositionDisk[mNumDisk]);
}
}
```
Votre code est incomplet, mais il apparaît que CalcullistBineXperiment a une boucle où nocoup est exécuté à partir de 1 à 2 ^ n , où n est le nombre de disques. C'est O (2 ^ N), pas une amélioration de O (2 ^ N). Tous les performances ne sont pas un gain de complexité algorithmique.
"Y a-t-il une solution pour la tour de Hanoi dont le temps de fonctionnement est inférieur à O (2 ^ n) où n est le nombre de disques à déplacer?" - Ouais. Ça s'appelle Triche :-)
... vous prenez la pile entière et déplacez-la à la fois. Non, il n'y a pas de moyen qui suit les règles meilleures que 2 ^ n.