tu prend ton graphe .
Tu le visualise en 3D (par exemple , ou une dimension R^(n) de tel sorte qu'aucun arc ne coupe un autre arc).
et pour chaque arc tu lui attribue un poid en fonction de ses coordonnées dans R3 (ou dans R^(n)).
Ce n'est pas un probleme du voyageur de commerce : je ne demande nulle part de trouver une optimisation.
Je demande déja de trouver un parcours hamiltonien dans un graphe inconnu (NP-complet)
et j'ai rajouter un truc histoire de faire bonne mesure (je sais pas si ce probleme est P ou NP ou P-approx ou ...)
Enfin je demande de faire tout ca dans P (P-approx est accepté , on demande pas le systeme optimum).
Bref 3 lignes, et pas pour autant trés simple à résoudre :)
[^] # Re: HP
Posté par briaeros007 . En réponse à la dépêche L'UFC Que Choisir contre la vente liée. Évalué à 2.
Tu le visualise en 3D (par exemple , ou une dimension R^(n) de tel sorte qu'aucun arc ne coupe un autre arc).
et pour chaque arc tu lui attribue un poid en fonction de ses coordonnées dans R3 (ou dans R^(n)).
Ce n'est pas un probleme du voyageur de commerce : je ne demande nulle part de trouver une optimisation.
Je demande déja de trouver un parcours hamiltonien dans un graphe inconnu (NP-complet)
et j'ai rajouter un truc histoire de faire bonne mesure (je sais pas si ce probleme est P ou NP ou P-approx ou ...)
Enfin je demande de faire tout ca dans P (P-approx est accepté , on demande pas le systeme optimum).
Bref 3 lignes, et pas pour autant trés simple à résoudre :)