Version imprimable
Bonjour,
Dans le problème des K plus courts chemins dans un graphe avec un(1) début « D » et une(1) fin « F » ? (bien que dans mon cas je cherche les K plus longs chemins)
je ne pense pas que le seul fait que cette algo soit connu type «Dijkstra, Ford-Bellman, Floyd-Warshall » qu’il soit directement casait comme un problème NP-Complet ?
Cordialement
bilred
Le problème d'optimisation "plus courts chemins" peut se transformer en une suite de problèmes de décision "chemins de longueur X". Chaque problème de décision peut être réduit a un problème SAT (Boolean satisfiability). Les problèmes SAT ont été démontrés comme étant NP-complet (theoreme de Cook–Levin).
Merci pour ta raiponce. :mur:
j'ai aussi trouvais cette raiponce sur un poste
Comment savoir que le problème est (ou non) NP-complet ?
tu pourrai pas simplifier un peut !Citation:
il faut prouver qu'il est complet dans la classe NP, c'est à dire qu'il permet (si on sait le résoudre) de résoudre tous les autres problèmes avec au plus un surcoût polynomial.
La classe NP est constituée de tous les problèmes résolubles avec un algorithme polynomial non-déterministe. Elle veut dire Non-deterministic Polynomial Time et pas, comme on le croit trop souvent, Non Polynomial Time. On ne sait pas si les problèmes de NP sont résolubles en temps polynomial (c'est la fameuse question "P = NP").
La méthode la plus simple pour prouver qu'un problème donné est NP-complet est souvent de montrer qu'on peut en déduire (polynomialement) la solution d'un autre problème NP-complet (on "réduit" le problème NP-complet connu vers notre problème). On utilise en général SAT ou 3-SAT qui sont des problèmes NP-complets "typiques" et souvent adaptés au problème donné. Il faut aussi montrer que le problème est dans NP, c'est-à-dire exhiber un algorithme non-déterministe polynomial (c'est là que les connaissances positives, comme les algorithmes que le PO cite, sont utiles).
(je vais comment voire sa de plus prés avec les indice que ta données)
cordialement
bilred
un problème est NP-complet s'il se réduit polynomialement à un problème NP complet déjà connu ...c'est la caractérisation la plus importante des problème NP Complet...
Réduire un problème A polynomialement à B c'est de prouver que toute instance de A peut se résoudre de façon polynomiale ( rapide ) s'il existait un algorithme qui résout B de façon polynomial ... d'où l'intérêt de cette classe ie si on résout un seul problème de façon polynomiale on résout tout les autres.