Pourquoi le backtracking rend-il un algorithme non déterministe?

je cite wikipedia:

un langage de programmation non déterministe est un langage qui peut spécifier, à certains points de l'émission (appelés "points de choix"), diverses alternatives pour le flux de l'émission. Contrairement à une instruction if-then, la méthode de choix entre ces alternatives n'est pas directement spécifiée par le programmeur; le programme doit décider à l'exécution entre les alternatives, via une méthode générale appliquée à tous les points de choix. Un programmeur spécifie un nombre limité de solutions de rechange, mais le programme doit choisir plus tard entre eux. ("Choisir" est, en fait, un nom typique pour l'opérateur non déterministe.) Une hiérarchie des points de choix peut être formée, avec des choix de niveau supérieur conduisant à des branches qui contiennent des choix de niveau inférieur à l'intérieur d'eux.

une méthode de choix est incorporée dans les systèmes de retraçage, dans lesquels certaines solutions de rechange peuvent "échouer", ce qui fait que le programme fait marche arrière et essaie d'autres solutions. Si toutes les alternatives échouent à un point de choix particulier, puis une branche entière échoue, et le programme va revenir en arrière plus loin, à un point de choix plus ancien. Une complication est que, parce que n'importe quel choix est provisoire et peut être refait, le système doit être en mesure de restaurer les anciens états de programme en annulant les effets secondaires causés par l'exécution partielle d'une branche qui a finalement échoué.

de la Programmation Non Déterministe l'article.

Envisager un algorithme pour colorier une carte du monde. Aucune couleur ne peut être utilisée sur les pays adjacents. L'algorithme commence arbitrairement à un pays et le colore d'une couleur arbitraire. Donc il se déplace le long, colorant les pays, changeant la couleur sur chaque pas jusqu'à, "uh oh", deux pays adjacents ont la même couleur. Maintenant, on doit revenir en arrière, et faire un nouveau choix de couleur. Maintenant, nous ne faisons pas un choix comme un algorithme non déterministe, ce n'est pas possible pour nos déterministe ordinateur. Au lieu de cela, nous simulons l'algorithme non-déterministe avec rétrotracking. Un algorithme non déterministe aurait fait le bon choix pour chaque pays.

le temps de fonctionnement du backtracking sur un ordinateur déterministe est factoriel, i.e. il est en O (N!).

Lorsqu'un ordinateur non déterministe peut deviner instantanément correctement à chaque étape, un ordinateur déterministe doit essayer toutes les combinaisons possibles de choix.

Puisqu'il est impossible de construire un ordinateur non-déterministe, ce que votre professeur a probablement voulu dire est le suivant:

inégalement dur problème dans la classe de complexité NP (tous les problèmes qu'un ordinateur non-déterministe peut résoudre efficacement en devinant toujours correctement) ne peuvent pas être résolus plus efficacement sur des ordinateurs réels que par des retours en arrière.

l'énoncé ci-dessus est vrai, si les classes de complexité P (Tous les problèmes qu'un ordinateur déterministe peut résoudre efficacement) et NP ne sont pas les mêmes. C'est le fameux problème P vs. NP. L'Institut de mathématiques de L'argile a offert un prix de 1 million de dollars pour sa solution, mais le problème a résisté à la preuve pour beaucoup an. Toutefois, la plupart des chercheurs croient que P n'est pas égal à NP.

une façon simple de le résumer serait: les problèmes les plus intéressants qu'un ordinateur non déterministe pourrait résoudre efficacement en devinant toujours correctement, sont si difficiles qu'un ordinateur déterministe devrait probablement essayer toutes les combinaisons possibles de choix, c.-à-d. utiliser le retracage.

expérience de Pensée:

1) cachée de la vue il y a une certaine distribution de charges électriques dont vous sentez une force et vous mesurez le champ potentiel qu'elles créent. Dites-moi exactement la position de tous les frais.

2) prendre certaines charges et les organiser. Dites-moi exactement le champ potentiel qu'ils créent.

seule la deuxième question a une réponse unique. C'est la non-unicité de champs de vecteurs. Cette situation peut être par analogie avec certains algorithmes non déterministes que vous envisagez. Considèrent de plus en limites mathématiques qui n'existent pas parce qu'ils ont des réponses différentes selon la direction dans laquelle vous vous approchez d'une discontinuité.

j'ai écrit un labyrinthe runner qui utilise le backtracking (bien sûr), que je vais utiliser comme exemple.

vous traversez le labyrinthe. Lorsque vous arrivez à une bifurcation, vous tournez à pile ou Face pour décider quel chemin suivre. Si vous choisissez une impasse, remontez jusqu'à la jonction et empruntez une autre route. Si vous les avez tous essayés, retournez à la jonction précédente. Cet algorithme n'est pas déterministe, non à cause du retour en arrière, mais à cause du retournement de pièce.

Maintenant modifier l'algorithme: lorsque vous atteignez une bifurcation, essayez toujours la route la plus à gauche que vous n'avez pas encore essayé en premier. Si cela mène à une impasse, revenez à la jonction et essayez à nouveau la route la plus à gauche que vous n'avez pas encore essayé. Cet algorithme est déterministe. Il n'y a aucune chance, c'est prévisible: vous suivrez toujours la même route dans le même labyrinthe.

si vous autorisez le retracking vous autorisez la boucle infinie dans votre programme ce qui le rend non déterministe puisque le chemin réel pris peut toujours inclure une boucle de plus.

les machines de Turing non déterministes (Ndtm) peuvent prendre plusieurs branches en une seule étape. D'autre part, les DTM suivent un processus d'essai et d'erreur.

vous pouvez penser aux DTMs comme des ordinateurs réguliers. En revanche, les ordinateurs quantiques sont semblables à NDTMs et peuvent résoudre des problèmes non déterministes beaucoup plus facile (voir leur application dans la cryptographie de rupture). Donc, le retraçage serait en fait un processus linéaire pour eux.

j'aime l'analogie du labyrinthe. Pensons au labyrinthe, pour la simplicité, comme un arbre binaire, dans lequel il n'y a qu'un seul chemin de sortie.

maintenant vous voulez essayer une première recherche en profondeur pour trouver la bonne façon de sortir du labyrinthe.

un ordinateur non déterministe, à chaque point de ramification, se dupliquerait / se clonerait et exécuterait chaque calcul supplémentaire en parallèle. C'est comme si la personne dans le labyrinthe se dupliquerait/se clonerait (comme dans le film Prestige) à chaque branchement point et envoyer une copie de lui-même dans la gauche subbranch de l'arbre et l'autre copie de lui-même dans le droit subbranch de l'arbre.

les ordinateurs / personnes qui finissent dans une impasse meurent (se terminent sans réponse).

un seul ordinateur survivra (terminez avec une réponse), celui qui sort du labyrinthe.

la différence entre le rétractation et le non-déterminisme est la suivante.

en cas de rétractation, il y a seul un ordinateur vivant à un moment donné, il fait le tour traditionnel de résolution de labyrinthe, marquant simplement son chemin avec une craie et quand il arrive à une impasse, il revient tout simplement à un point de ramification dont les sous-branches, il n'a pas encore exploré complètement, tout comme dans une première recherche en profondeur.

IN CONTRAST:

un ordinateur non détéministe peut se cloner à chaque point de ramification et vérifier la sortie en effectuant des recherches de paralell dans les sous-ramifications.

ainsi l'algorithme de retraçage simule / émule la capacité de clonage de l'ordinateur non-déterministe sur un ordinateur séquentiel/non-parallèle/déterministe.