Je cherche un moyen de prouver que le problème du plus court chemin de bicriteria est np complet. qui est, étant donné un graphique avec des longueurs et des poids, je dois savoir s'il existe un chemin dans le graphe de s à t avec une longueur totale < = L et poids < = W.Réduction simple (complétude NP)
Je sais que je dois prendre un problème complet NP et le réduire à celui-ci. Nous avons à notre disposition les problèmes suivants: 3-SAT, ensemble indépendant, couverture de vertex, cycle hamiltonien et adaptation en trois dimensions.
Des idées sur lesquelles peut-être viable?
merci
Vous pouvez vous arrêter aux heures d'ouverture de votre professeur. 1-1 temps avec les sciences informatiques PhD est une partie inestimable de votre éducation. Vous devriez en profiter pendant que vous le pouvez. –
Malheureusement, je n'ai pas ici ma copie de Garey et Johnson, et je ne me souviens pas de certains de ces problèmes. Si vous éditez votre question pour donner des définitions rapides, cela pourrait aider les gens à les trouver. (Exemple: 3-SAT: Étant donné un ensemble de variables booléennes, et un ensemble de clauses OU ensemble trois variables, dont certaines peuvent être annulées, pouvez-vous assigner des valeurs de vérité aux variables telles que toutes les clauses sont vraies?) –