Trouver des chaînes les plus longues de dispositifs d'adaptation

Question

Set A a n appareils. Set B a des dispositifs m. Certains appareils en A sont compatibles avec les appareils en B, et certains appareils en B sont compatibles avec ceux de A.

Je veux que de nombreux appareils compatibles connectés les uns aux autres que possible. (Il est pas nécessaire d'avoir un dispositif dans A et B à B pour être mutuellement compatibles.)

Modifier pour plus de clarté :. Tout dispositif peut être lié à 0, 1 ou 2 autres dispositifs, mais pas elle-même

Finalement, tous les appareils (ou tout sauf deux, si les « fins » ne réunissez pas) devraient être reliés entre eux 1 sur 1. Il est possible de relier tout un appareil à un autre appareil. Mais aucun appareil en A sont compatibles avec tous les appareils en A (mais ils sont liable ), et est de même pour les appareils en B.

If I have A = {a1,a2,a3}, B = {b1,b2,b3} and n=m=3

a1 is compatible with b1,b2
a2 is compatible with b1
a3 is compatible with b1
b1 is compatible with a1,a3
b2 is compatible with a1
b3 is compatible with a1

Ensuite, le graphe G

a1 <-> b2 <-> a2 <-> b1 <-> a3 <-> b3 <-> a1

est un graphique optimal.

G ne doit pas être cyclique, mais il peut être.

Y a-t-il des moyens astucieux pour aborder ce sujet?

Answer 1

Je crois que ce problème est NP-difficile par une réduction du problème le plus long chemin non orienté, qui est connu pour être NP-dur par une réduction du problème du chemin hamiltonien non orienté (voir la fiche Sipser Introduction à la théorie de calcul pour plus de détails sur les raisons).

Dans le problème de trajet le plus long undirected, nous sont donnés en entrée un graphe non orienté G = (V, E), et aussi d'une paire de noeuds u et v et un nombre k, et veut déterminer si oui ou non il y a un simple (pas de noeud apparaît deux fois) chemin de u à v de longueur au moins k. Nous pouvons convertir en votre problème en utilisant une réduction du temps polynomiale comme suit:

• Pour chaque noeud v _i ? V, il y a un dispositif dans un (appelons-d _i ).
• Pour chaque arête {v _i , v _j } ? V, il existe un dispositif à B (appelons-e _{i, j} ).
• Pour chaque noeud v _i et arête {v _i , v _j }, Dispositif d _i est compatible avec le dispositif e _{i, j} .

Cette réduction a une taille polynomiale, puisque le nombre total d'appareils générés est de taille | V | + | E | et le nombre de connexions est 2 | E |. En outre, on peut voir qu'il existe un chemin de longueur k de V _i to v _j dans le graphique G ssi il existe une chaîne de dispositifs de longueur 2k + 1 à partir d _i de d _j . Plus précisément, si ((v _{i 1} , v _{i 2} ), (v _{i 2} , v _{i 3} ), ..., (v _{i k - 1} , v _{i k} )) est un simple chemin de v _i to v _j , puis la chaîne d _{i 1} ? e _{i 1 , i 2} ? d < sub> i ₂ ? e _{i 2 , i 3} ? d _{i < sub> 3} ? ... ? e _{i k - 1 , i k} ? d _{i k} et vice-versa. Nous avons donc une réduction du temps polynomiale de plus long chemin undirected vous problème comme suit:

• Etant donné que l'entrée (G, v _i , v _j , k) le problème de la trajectoire la plus longue undirected:
  • Construction d'ensembles A et B ci-dessus, avec les compatibilités C comme ci-dessus.
  • Vérifiez s'il y a une chaîne de dispositifs de longueur 2k + 1 à partir d _i de d _j .
  • Si oui, sortie "oui"
  • Dans le cas contraire, la sortie "non".

Cette réduction permet de résoudre le problème le plus long chemin undirected en temps polynomial non déterministe à l'aide d'un solveur pour votre problème, et si votre problème est NP-dur. Par conséquent, vous ne devriez pas vous attendre à trouver un algorithme polynomial pour votre problème; trouver une réponse exacte est de prendre le temps exponentielle probable à moins que P = NP.

Désolé de donner une réponse négative de, mais j'espère que cela aide!

Answer 2

Ceci est np dur mais je pense que des approximations de problèmes de couverture du cycle maximal peut vous aider (dans chaque dispositifs de liaison de groupe avec bord de taille 0), vous pouvez également ajouter un nœud supplémentaire qui connecté à tous les autres noeuds en poids 0) , par exemple cet article: Approximation Covers cycle Poids maximum dans des graphes avec des poids zéro et un vous aider.