Je comprends qu'ils ne sont pas réels et ils semblent pouvoir calculer une succursale chaque fois qu'il y a 2 options, au lieu de en choisir un. Mais, par exemple, si je dis cela:
"non déterministe devinez une bijection P de sommets du graphique g au graphique H" (contexte ici est l'isomorphisme graphique)
Qu'est-ce que c'est censé vouloir dire? Je comprends la bijection, mais cela dit "non déterministe". Si cela devine, comment est-ce une approche algorithmique? Comment cela peut-il garantir qu'il va fonctionner?
4 Réponses :
Je crois ce que l'on veut dire est "non déterministe de choisir une solution", puis testez que la solution est vraie. Étant donné que tous les choix possibles (suppositions) sont testés, la solution est garantie.
Une implémentation physique de la machine Turning non déterministe est l'ordinateur ADN. Par exemple, voici un aperçu de la façon de résoudre le problème du vendeur itinérant dans l'ADN:
Obtenez / faire un tas de séquences d'ADN, chacune avec une longueur proportionnelle au coût d'un bord de votre graphique et de vos extrémités collantes avec des séquences identifiant de manière unique l'un des sommets que le bord se connecte.
mélangez-les, avec ADN LIGASE dans un grand bécher. Ils se receler les uns aux autres dans des séquences qui représentent chaque chemin possible à travers le graphique (OK, pas les très longs).
Supprimez toutes les séquences qui manquent au moins un sommet. Pour ce faire, sélectionnez séquentiellement pour chaque sommet à l'aide d'une hybridation. Par exemple, si "ACGTACA" code Vertex 1, sélectionnez pour les séquences qui se lient à "Tgtacga". Puis répétez cette sélection pour tous les autres sommets.
Trier les séquences restantes de la taille à l'aide de l'électrophorèse sur gel. Puis séquencer le plus court. La séquence code le chemin le plus court via votre graphique.
Et rappelez-vous que, pour des problèmes importants, vous avez besoin d'un très gros bécher vraiment. Peut-être un qui ne va pas dans la galaxie. Ces problèmes deviennent plus gros vrais rapidement.
Il y a différentes façons de l'imaginer. On Je trouve utile est le modèle Oracle. Avez-vous déjà vu le dessin animé de la face lointaine où une dérivation sur le tableau noir a-t-elle "ici un miracle se produit" comme l'une des étapes intermédiaires? Dans cette version d'une NDTM, lorsque vous devez choisir quelque chose, l'Oracle écrit la version correcte sur la partie droite de la bande. (Ceci est tiré de garey et de Johnson, ordinateurs et intractabilité , leur livre classique sur les problèmes complets NP.) Vous n'êtes pas autorisé à supposer que vous avez le bon, cependant, et il peut y avoir ne pas être correct.
Par conséquent, lorsque vous devinez de manière non déterministe une bijection, vous obtenez la bécasse correcte à vos fonctions, à condition que l'une existe.
Ce n'est pas une bonne base d'un algorithme, car la complexité de la mise en œuvre d'une machine à troubles non déterministe est essentiellement exponentielle dans les états non déterministes et l'équivalent algorithmique de la supposion non déterministe est d'essayer toutes les bijection possibles.
d'un point de vue théorique, je le traduirais comme "s'il y a une béchage telle que ...". D'un point de vue algorithmique, trouvez un autre livre, ou un autre chapitre du même livre, puisque cette approche est inutile pour des graphiques même modérément importants.
Ils ne le font pas, ils illustrent simplement un point. Fondamentalement, ce qu'ils font, c'est deviner une réponse et vérifier si c'est raison (déterministe). Ce n'est pas le devinant la partie de réponse qui est importante cependant, il vérifie que la réponse est correcte. C'est comme si comme dire une solution arbitraire, est-ce correct? Ainsi, par exemple, il y a des problèmes qui prennent des problèmes exponentiels à calculer et certaines de leurs réponses peuvent être vérifiées dans du temps polynomial, mais certaines ne peuvent pas. Donc, ce que le TM non déterministe est-il divise ces deux, ceux qui peuvent être vérifiés rapidement de ceux qui ne peuvent pas. Et ensuite, cela soulève la plus grande question, si un groupe de solutions de questions peut être vérifié beaucoup plus rapidement qu'une autre, que leurs solutions peuvent-elles également être générées plus rapidement? Cette question n'a pas encore été répondue.