¿Conectar islas con pontones es NP completo?

10

Tengo un problema en mi mente, creo que es un problema NPC pero no sé cómo probarlo.

Aquí está el problema:

Hay k islas en un lago muy grande, y hay n pontones en forma de abanico. Esos pontones son del mismo tamaño pero tienen diferentes direcciones iniciales y están en diferentes posiciones originales en el lago. Los pontones pueden girar libremente alrededor de su centro de masa, y sin costo asociado con la rotación.

Ahora tenemos que mover esos pontones para que todas las islas del lago puedan conectarse. Podemos garantizar que la cantidad de pontones es suficiente para conectar todas las islas.

[Nota]: ¡No podemos reutilizar los pontones!

La tarea es encontrar la solución que tenga la distancia total mínima de los pontones móviles para que todas las islas estén conectadas. La distancia de mover un pontón se puede calcular como la distancia entre la posición original del centro de masa y su posición desplegada.

Para que quede claro, he dibujado esa figura. Supongamos que tenemos 3 islas A, B y C. Están ubicadas en algún lugar del lago. Y tengo varios pantis en forma de abanico. Ahora la solución es encontrar una suma mínima de distancia de movimiento para conectar A, B y C, que se muestra en la parte inferior de la figura. Espero que ayude a entender el problema. :)

ingrese la descripción de la imagen aquí

Parece que el problema es un NPC, pero no sé para probarlo. ¿Puede alguien ayudarme con esto?

Tsuyoshi Ito
fuente
@vsaxena No, no creo que la solución final sea una línea recta, en algún momento si ya forma un arco, pero no necesitamos mover ninguno de ellos. La mayoría de los casos, una línea recta será buena, pero a medida que los pontones se vuelven más densos, la solución puede no ser una línea recta. La figura es solo un ejemplo. :)
1
Parece muy cerca de Steiner Tree. En un espacio métrico, muchas técnicas para resolver funcionan en ambos. en.wikipedia.org/wiki/…
Nicholas Mancuso
@NicholasMancuso los puentes son nodo a nodo, por lo que no es un árbol clásico de Steiner donde el puente conecta múltiples nodos. Hay muchos problemas en el diseño VLSI que tienen características similares.
VSOverFlow
1
@vsaxena: El problema está poco especificado. Supongamos que tengo tres islas A, B, C en un triángulo equilátero, y los pontones inicialmente forman una forma de Y conectada con las islas en los extremos. ¿No está haciendo nada una solución válida, o los pontones deben moverse más? Si esta solución no es válida, ¿qué constituye precisamente una configuración válida de los pontones?
JeffE
1
@vsaxena: Y mientras estamos en ello, ¿las islas son solo puntos, o círculos, o alguna forma más complicada especificada en la entrada? ¿Son los pontones segmentos de línea, o elipses, o alguna otra forma? ¿Son todas las islas del mismo tamaño y forma, o pueden ser diferentes? ¿Todos los pontones tienen el mismo tamaño y forma, o pueden ser diferentes?
JeffE

Respuestas:

1

Primero: Este no es el problema del vendedor ambulante. El TSP requiere la identificación de un ciclo hamiltoniano de peso mínimo; Este ciclo no requiere un ciclo, o incluso una ruta de peso mínimo en absoluto. Requiere un costo mínimo de construcción de un conjunto de bordes de conexión, donde el costo de construcción se basa en mover los pontones.

Segundo: este no es el problema del árbol de expansión de peso mínimo. Ver arriba: requerimos una construcción de costo mínimo, no una identificación de peso mínimo.

Tercero: Parece que el camino construido será un árbol de expansión, pero no necesariamente un peso mínimo. La alternativa es que sería un árbol de expansión más algunos bordes adicionales que darían como resultado un ciclo; pero si comenzamos en una configuración sin bordes, entonces cada borde tiene un costo positivo y siempre podemos encontrar un árbol de expansión de menor peso simplemente no construyendo los bordes adicionales.

Cuarto: dices que los pontones giran libremente; Supongo que eso significa que no hay costos asociados con la rotación de los pontones. Sin embargo, no especifica sobre qué giran los pontones: ¿sus puntos? ¿Sus centros de masa? Cualquier punto interno? (Si hay algún punto externo, entonces tendríamos construcciones de peso cero, ¿sí?)

Esto es un poco sutil, porque si estamos girando 90 grados sobre un punto interno, digamos, el centro de masa, ¿cuál es el costo? ¿Nada, porque es una rotación? ¿Alguna cantidad finita porque el punto se movió? Ahora también necesitamos saber el tamaño de los pontones.

Quinto: ¿Se supone que tanto los pontones como las islas están incrustados en el Plano Euclidiano?

Novak
fuente
Gracias por tu respuesta. La rotación está alrededor del centro de masa y no hay costo asociado con la rotación, solo el movimiento implica un costo. Sí, tanto los pontones como las islas están incrustados en el plano euclidiano. Modificaré la publicación para que quede clara.
No estoy de acuerdo con que este no sea esencialmente el TSP. Todo este post está envuelto alrededor del eje en terminología, pero el hecho es que si uno dibujó una línea entre cada pontón y cada posición final del pontón final, y calculó la distancia de cada línea para que sea su peso, entonces con la excepción desde el punto final volviendo al punto de partida, el gráfico que se forma se ve casi exactamente (a un tee) como el TSP. Un pontón o una posición final es un nodo en el gráfico, y los pesos están formados por las distancias. El ciclo hamiltoniano SOLO significa que termina donde comenzó.
2
Esta no es una respuesta, sino una serie de comentarios.
Raphael
1

Después de mirar los nuevos diagramas, veo que puede necesitar varios pontones para cruzar entre islas. Dado eso, podría acercarse mucho a una solución del problema del árbol Steiner al convertir los nodos en islas y crear una colección suficientemente diversa de pontones con arcos pequeños. Wikipedia dice que, de hecho, hay un PTAS para el problema del árbol Steiner, por lo que no puedo decir de inmediato que esto hace que NP-complete. Sin embargo, mirar los detalles del árbol Steiner podría brindarle una buena solución aproximada o mostrar que el problema es NP-Complete.

mcdowella
fuente
Lo que está describiendo es un algoritmo aproximado para llegar a una solución casi óptima. Sin embargo, ¿cómo se verifica que la solución sea óptima?
Creo que el verdadero problema es que necesita varios pontones para cruzar entre islas, lo que hace que se parezca mucho a un árbol Steiner. Eche un vistazo a Branch and Bound para saber cómo pasar de un límite inferior (por ejemplo, generado al descuidar una restricción) a una solución óptima conocida.
mcdowella
2
@mcdowella No es un árbol Steiner ya que cada pontón puede aparecer en un solo puente; Es un sistema punto a punto. Además, puesto que la función de costo es el movimiento de los pontones, puede tener un caso donde se forma el puente en amplios arcos que todavía tiene un costo menor que la solución línea recta ..
VSOverFlow
Esto no puede ser el steiner desde otra perspectiva. NO PODEMOS AGREGAR PUNTOS solo para satisfacer nuestras necesidades.
trumpetlicks
1
Si se permiten las uniones en Y, esto es al menos tan difícil como el problema del árbol Steiner, porque cualquier problema del árbol Steiner se puede convertir en uno de estos, simplemente cree muchos pontones y colóquelos tan lejos de las islas que no lo haga. realmente importa en qué pontón usas dónde. Entonces, si pudiera resolver esto, podría resolver el problema del árbol Steiner: para este argumento, no importa que haya algunas configuraciones de pontones que no generen problemas con el árbol Steiner. Si las uniones en Y no están permitidas, necesitamos saber exactamente cuáles son las reglas. ¿Se cruzan los caminos en el cruce?
mcdowella
0

Después del dibujo, esto sigue siendo un problema de NPC. Incluso si reducimos el problema a cada pontón, podemos asumir 1 de n posiciones (es decir, líneas de conexión conocidas. Para obtener la respuesta más óptima, tendríamos que probar cada pontón en cada posición, sumando su distancia para llegar a esas posiciones respectivas) tiempo, y comparándolo con todos los demás, si cada pontón tiene que ser probado en cada posición, entonces hay n! combinaciones que necesitan ser probadas.

Elegí editar las imágenes del póster original con algunas adiciones para mostrar las ideas gráficas detrás de este problema.

La imagen a continuación muestra todos los pontones (menos 2 para hacerlo más simple) en diferentes colores, con todas las ubicaciones potenciales de los extremos del pontón en ROJO. Solo he dibujado las líneas entre 3 pontones y todas las ubicaciones finales, pero uno podría ver cuán LOCO podría ser esto.

Digamos que solo por el gusto de hacerlo, elegimos que el pontón turquesa se coloque en la ubicación final más cercana como el primer paso (aunque desde el TSP sabemos que esto puede no ser óptimo al final).

A continuación vemos exactamente eso, el pontón y la distancia (también conocida como distancia de viaje ponderada) que tendrá que viajar.

ingrese la descripción de la imagen aquí

Desde aquí se puede hacer un nodo virtual con las dos ubicaciones finales al lado de la ubicación recién colocada. Distancia desde el nodo establecido, y los dos nodos adyacentes dentro del nodo virtual tienen una distancia de viaje virtual de 0.

A continuación, vemos el nodo virtual creado con TODOS los pesos de distancia de viaje potenciales que se pueden colocar allí.

ingrese la descripción de la imagen aquí

Al ver cómo esto continuaría, y cómo la solución más óptima (como se ve muchas veces con el TSP) no siempre será elegir la distancia más corta para cada elección, tendríamos que probar esencialmente todas las rutas para todos los nodos / nodos virtuales.

Al final, el primer nodo del problema (TSP) podría ser cualquiera de los puntos de pontón finales potenciales, y las líneas dibujadas a partir de eso son las distancias desde ese punto final a todos los demás pontones. todos los demás nodos se convierten en nodos virtuales como lo he descrito con sus líneas saliendo como las distancias / pesos a todos los pontones restantes, y así sucesivamente. Cómo este problema de gráfico NO ES EXACTAMENTE el problema del vendedor ambulante sin el requisito de ÚLTIMO SALTO del ciclo hamiltoniano está más allá de mí. Para tener la respuesta exacta, uno debe probar todas las rutas a través del gráfico.

trompetas
fuente
1
Dejando a un lado si este es un modelo razonable del problema planteado o si este es realmente un modelo TSP, no es así como funcionan las reducciones de NP. No demuestras que tu problema objetivo puede enmarcarse como una instancia de un problema NPC. Debe mostrar que una instancia de un problema de NPC puede enmarcarse como su problema objetivo.
2
Oh querido. Si se había molestado en leer mi comentario y el enlace que le proporcioné, habría aprendido que el algoritmo al que se hace referencia es exacto (lo prueban) y, por lo tanto, contradice su comprensión. Tenga en cuenta que su opinión sugiere que P! = NP, esta sigue siendo una pregunta abierta. Entonces no, no has entendido esto, lo siento. (Incluso si fuera cierto que los problemas de NP completo no podrían resolverse mejor que ingenuamente, el razonamiento que usa sería incorrecto)
Raphael
2
O(1.3n)n
3
@JeffE: En otras palabras, esta respuesta solo prueba que el problema probablemente sea NP-completo.
Tsuyoshi Ito