La connexion des îles avec pontons est-elle complète?

10

J'ai un problème dans mon esprit, je pense que c'est un problème de PNJ mais je ne sais pas comment le prouver.

Voici le problème:

Il y a k îles dans un lac très grand, et il y a n pontons en forme d' éventail. Ces pontons sont de la même taille mais ont des directions initiales différentes et sont dans des positions originales différentes dans le lac. Les pontons peuvent tourner librement autour de son centre de masse, sans aucun coût associé à la rotation.

Maintenant, nous devons déplacer ces pontons afin que toutes les îles du lac puissent être connectées. Nous pouvons garantir que le nombre de pontons est suffisant pour relier toutes les îles.

[Note]: Nous ne pouvons pas réutiliser les pontons !!

La tâche est de trouver la solution ayant la distance totale minimale des pontons en mouvement afin de connecter toutes les îles. La distance de déplacement d'un ponton peut être calculée comme la distance entre la position d'origine du centre de masse et sa position déployée.

Pour être clair, j'ai dessiné un tel chiffre. Supposons que nous ayons 3 îles A, B et C. Elles sont situées quelque part dans le lac. Et j'ai plusieurs pantalons en forme d'éventail. Maintenant, la solution consiste à trouver une somme minimale de distance de déplacement pour connecter A, B et C, indiquée dans la partie inférieure de la figure. J'espère que cela vous aidera à comprendre le problème. :)

entrez la description de l'image ici

Il semble que le problème soit un PNJ, mais je ne sais pas le prouver. Quelqu'un peut-il m'aider à ce sujet?

Tsuyoshi Ito
la source
@vsaxena Non, je ne pense pas que la solution finale soit une ligne droite, parfois si elle forme déjà une arche, mais nous n'avons besoin de déplacer aucune d'entre elles. Dans la plupart des cas, une ligne droite sera bonne, mais comme les pontons se densifient, la solution peut ne pas être une ligne droite. La figure n'est qu'un exemple. :)
1
Semble très proche de Steiner Tree. Dans un espace métrique, de nombreuses techniques pour résoudre le travail sur les deux. en.wikipedia.org/wiki/…
Nicholas Mancuso
@NicholasMancuso les ponts sont nœud à nœud, ce n'est donc pas un arbre Steiner classique où le pont relie plusieurs nœuds. Il existe de nombreux problèmes dans la disposition VLSI qui ont des caractéristiques similaires.
VSOverFlow
1
@vsaxena: Le problème est sous-spécifié. Supposons que j'ai trois îles A, B, C dans un triangle équilatéral et que les pontons forment initialement une forme en Y connectée avec les îles aux extrémités. Ne rien faire est-il une solution valable ou faut-il déplacer les pontons plus loin? Si cette solution n'est pas valable, alors qu'est-ce qui constitue précisément une configuration valide des pontons?
JeffE
1
@vsaxena: Et pendant que nous y sommes, les îles ne sont-elles que des points, ou des cercles, ou une forme plus compliquée spécifiée dans l'entrée? Les segments de ligne des pontons, ou les ellipses, ou une autre forme? Toutes les îles ont-elles la même taille et la même forme, ou peuvent-elles être différentes? Tous les pontons ont-ils la même taille et la même forme, ou peuvent-ils être différents?
JeffE

Réponses:

1

Premièrement: ce n'est pas le problème du voyageur de commerce. Le TSP nécessite l'identification d'un cycle hamiltonien de poids minimal; ce cycle ne nécessite pas de cycle, ni même de parcours de poids minimal. Il nécessite une construction à coût minimal d'un ensemble de bords de connexion, où le coût de construction est basé sur le déplacement des pontons.

Deuxièmement: ce n'est pas le problème de l'arbre couvrant de poids minimal. Voir ci-dessus - nous avons besoin d'une construction à coût minimal et non d'une identification de poids minimale.

Troisièmement: Il semble que le chemin construit sera un arbre couvrant, mais pas nécessairement un poids minimal. L'alternative est qu'il s'agirait d'un arbre couvrant plus quelques arêtes supplémentaires résultant en un cycle; mais si nous commençons dans une configuration sans arêtes, chaque arête a un coût positif et nous pouvons toujours trouver un arbre couvrant de poids inférieur en ne construisant simplement pas les arêtes supplémentaires.

Quatrièmement: vous dites que les pontons tournent librement; Je suppose que cela signifie qu'aucun frais n'est associé à la rotation des pontons. Cependant, vous ne précisez pas sur quoi tournent les pontons: leurs points? Leurs centres de masse? Un point interne? (S'il y avait un point externe, alors nous aurions des constructions de poids nul, oui?)

C'est un peu subtil, car si nous tournons de 90 degrés autour d'un point interne, disons le centre de masse, quel est le coût? Rien, parce que c'est une rotation? Une certaine quantité finie parce que le point a bougé? Maintenant, nous devons également connaître la taille des pontons.

Cinquièmement: on suppose que les pontons et les îles sont tous deux intégrés dans le plan euclidien?

Novak
la source
Merci pour votre réponse. La rotation est autour du centre de masse et aucun coût n'est associé à la rotation, seul le mouvement implique un coût. Oui, les pontons et les îles sont intégrés dans le plan euclidien. Je vais modifier le message pour qu'il soit clair.
Je ne suis pas d'accord que ce n'est pas essentiellement le TSP. Tout ce poteau est enroulé autour de l'essieu dans la terminologie, mais le fait est que si l'on a tracé une ligne entre chaque ponton et chaque position potentielle de ponton d'extrémité, et calculé la distance de chaque ligne pour être son poids, alors à l'exception du point final revenant au point de départ, le graphique qui est formé ressemble presque exactement (à un tee) au TSP. Un ponton ou une position finale est un nœud dans le graphique, et les poids sont constitués par les distances. Le cycle hamiltonien signifie UNIQUEMENT qu'il se termine là où il a commencé.
2
Ce n'est pas une réponse, mais une série de commentaires.
Raphael
1

Après avoir regardé les nouveaux diagrammes, je constate que vous pourriez avoir besoin de plusieurs pontons pour traverser les îles. Cela étant, vous pouvez vous rapprocher très près d'une solution au problème de l' arbre de Steiner en transformant les nœuds en îles et en créant une collection suffisamment diversifiée de pontons avec de petits arcs. Wikipedia dit qu'il existe en fait un PTAS pour le problème de l'arbre Steiner, donc je ne peux pas dire immédiatement que cela le rend NP-complet. Cependant, en regardant les détails de l'arbre Steiner, vous pouvez soit obtenir une bonne solution approximative, soit montrer que le problème est NP-Complete.

mcdowella
la source
Ce que vous décrivez est un algorithme approximatif pour arriver à une solution presque optimale. Mais comment vérifiez-vous même que la solution est optimale?
Je pense que le vrai problème est que vous avez besoin de plusieurs pontons pour traverser les îles, ce qui ressemble beaucoup à un arbre Steiner. Jetez un œil à Branch and Bound pour savoir comment passer d'une borne inférieure (générée par exemple en négligeant une contrainte) à une solution optimale connue.
mcdowella
2
@mcdowella Ce n'est pas un arbre Steiner puisque chaque ponton ne peut apparaître que sur un seul pont; c'est un système point à point. De plus, puisque la fonction de coût est le mouvement des pontons, vous pouvez avoir un cas où le pont est formé en arcs larges qui ont toujours un coût inférieur à la solution en ligne droite.
VSOverFlow
Cela ne peut pas être le steiner d'un autre point de vue. NOUS NE POUVONS PAS AJOUTER DE POINTS juste pour répondre à nos besoins.
trumpetlicks
1
Si les jonctions Y sont autorisées, cela est au moins aussi difficile que le problème de l'arbre Steiner, car tout problème d'arbre Steiner peut être transformé en l'un d'eux - il suffit de créer beaucoup de pontons et de les placer si loin des îles qu'il ne le fait pas importe vraiment quel ponton vous utilisez où. Ensuite, si vous pouviez résoudre ce problème, vous pourriez résoudre le problème de l'arbre Steiner: pour cet argument, peu importe qu'il existe certaines configurations de pontons qui ne provoquent pas de problèmes d'arbre Steiner. Si les jonctions Y ne sont pas autorisées, nous devons savoir exactement quelles sont les règles. Les chemins se croisent-ils à la jonction?
mcdowella
0

Après le dessin, il s'agit toujours d'un problème de PNJ. Même si nous réduisons le problème à chaque ponton, nous pouvons prendre 1 position sur n (c.-à-d. Des lignes de connexion connues. Pour obtenir la réponse la plus optimale, nous devons essayer chaque ponton dans chaque position, en ajoutant leur distance pour atteindre chacune de ces positions respectives. temps et en se comparant à tous les autres. Si chaque ponton doit être testé dans chaque position, alors il n'y a pas de combinaisons à tester.

Ive a choisi de modifier les images de l'affiche originale avec quelques ajouts pour montrer les idées de graphique derrière ce problème.

L'image ci-dessous montre tous les pontons (moins 2 pour le simplifier) ​​de couleurs différentes, avec tous les emplacements potentiels d'extrémité de ponton en ROUGE. Je n'ai tracé que les lignes entre 3 pontons et tous les emplacements finaux, mais on pouvait voir comment cela pouvait être fou.

Disons que juste pour le plaisir, nous choisissons que le ponton turquoise soit placé à l'emplacement final le plus proche comme première étape (bien que DEPUIS LE TSP, nous savons que cela peut ne pas être optimal à la fin).

Ci-dessous, nous voyons exactement cela, le ponton et la distance (aka distance de déplacement pondérée) qu'il devra parcourir.

entrez la description de l'image ici

De là, un nœud virtuel avec les deux emplacements d'extrémité à côté de l'emplacement qui vient d'être placé peut être créé. La distance du nœud défini et les deux nœuds adjacents au sein du nœud virtuel ont une distance de déplacement virtuelle de 0.

Ci-dessous, nous voyons le nœud virtuel créé avec TOUS les poids de distance de déplacement potentiels qui peuvent y être placés.

entrez la description de l'image ici

Pour voir comment cela continuerait et comment la solution la plus optimale (comme on l'a vu plusieurs fois avec le TSP) ne serait pas toujours en choisissant la distance la plus courte pour chaque choix, il faudrait tester essentiellement tous les chemins pour tous les nœuds / nœuds virtuels.

En fin de compte, le premier nœud du problème (TSP) pourrait être n'importe lequel des points de ponton d'extrémité potentiels, et les lignes qui en sont tirées sont les distances de ce point d'extrémité à tous les autres pontons. tous les autres nœuds deviennent ensuite des nœuds virtuels comme je l'ai représenté avec leurs lignes se détachant comme les distances / poids à tous les pontons restants, et ainsi de suite. Comment ce problème de graphique n'est PAS EXACTEMENT le problème des vendeurs itinérants sans l'exigence LAST JUMP du cycle hamiltonien me dépasse. Afin d'avoir la réponse exacte, il faut tester tous les chemins à travers le graphique.

trompettes
la source
1
Laissant de côté s'il s'agit d'un modèle raisonnable du problème déclaré ou s'il s'agit même d'un modèle de PST, ce n'est pas ainsi que fonctionnent les réductions de NP. Vous ne montrez pas que votre problème cible peut être défini comme une instance d'un problème NPC. Vous devez montrer qu'une instance d'un problème NPC peut être définie comme votre problème cible.
2
Oh cher. Si vous aviez pris la peine de lire mon commentaire et le lien que j'ai fourni, vous aviez appris que l'algorithme référencé est exact (ils le prouvent) et contredit donc votre compréhension. Notez que votre opinion suggère que P! = NP - c'est toujours une question ouverte. Alors non, vous ne l'avez pas compris, désolé. (Même s'il était vrai que les problèmes NP-complets ne pouvaient pas être mieux résolus que naïvement, le raisonnement que vous utiliseriez serait faux.)
Raphael
2
O(1.3n)n
3
@JeffE: En d'autres termes, cette réponse prouve seulement que le problème est probablement NP-complet.
Tsuyoshi Ito