Discussion:Algorithme de Davis-Putnam
Dernier commentaire : il y a 12 ans par Groumphy dans le sujet Évaluation
Autres discussions [liste]
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Évaluation
modifierBonjour,
J'ai supprimé l'évaluation informatique. Bien à vous,
Heuristique
modifierIl s'agit d'un problème NP-Complet et cet algorithme est donc une heuristique, il faudrait le mentionner.
Non, cette algorithme n'est pas heuristique, il cherche la solution en faisant une recherche systématique.
Par contre, j'ai modifié un peu la description de l'algo mais j'ai des doutes:
- comme dans la version que j'ai modifier j'ai utiliser union entre les deux recherche, mais ça ne serais pas plutôt un ou ?
- il n'y a pas une méthode pour choisir la variable ?
- dans le première algorithme, je ne suis pas sur de comprendre ce qu'on veux dire par "résoudre C et N"
Vanicat (d) 7 mai 2008 à 10:36 (CEST)
- Alors pour le premier algorithme, en fait je l'avais directement traduit de l'article anglophone quand j'avais créé l'article ici, mais je dois reconnaître que je n'ai pas plus attention que ça à la manière dont il fonctionne. Pour le reste, n'ayant plus utilisé l'algorithme de Davis-Putnam depuis un certain temps, je ne me rappelle plus vraiment des détails de cet algo. À l'occasion, si j'ai le temps, je reprendrai mes notes sur le sujet pour apporter des précisions à l'article. PieRRoMaN 8 mai 2008 à 01:21 (CEST)
Algorithme récursif
modifierCet algorithme récursif ne ressemble pas du tout à l'algorithme de Davis-Putnam mais plutôt à l'Algorithme de Davis-Putnam-Logemann-Loveland. L'algorithme DP est une simple boucle (ou n'a qu'un appel récursif terminal) et n'a pas de backtracking comme l'algorithme DPLL.