masud
Me gustaría encontrar un mejor algoritmo para resolver el siguiente problema:
Existen norte puntos de partida (púrpura) y norte puntos de destino (verde) en 2D. Quiero un algoritmo que conecte los puntos de inicio con los puntos de destino mediante un segmento de línea (marrón) sin que ninguno de estos segmentos se cruce (rojo) y al mismo tiempo que minimice la longitud acumulada de todos los segmentos.
Mi primer esfuerzo en C++ fue permutar todos los estados posibles, encontrar estados libres de intersecciones y, entre ellos, el estado con la longitud total mínima del segmento. ¡En!) . Pero creo que tiene que haber una mejor manera.
¿Alguna idea? ¿O buenas palabras clave para la búsqueda?
Esto es Coincidencia euclidiana mínima en 2D. El enlace contiene una bibliografía de lo que se sabe sobre este problema. Dado que desea minimizar la longitud total, la restricción de no intersección es redundante, ya que la longitud de cualquier par de segmentos que se crucen se puede reducir descruzándolos.
-
@Walkerneo, no es cruzar las piernas, porque la distancia entre los pies y la distancia entre las caderas es más corta que la longitud de las piernas.
– zzzzBov
26 de marzo de 2012 a las 0:34
-
@qq3: Estrictamente hablando, creo que esto es Bipartito Coincidencia euclidiana mínima, un subconjunto mencionado en su enlace.
– RBarryYoung
27 de marzo de 2012 a las 14:22
-
@dmckee: qq3 dijo que la regla de no intersección era redundante bajo la restricción de longitud total mínima, no “en conflicto” con ella (matemáticamente, estos son muy cosas diferentes). Y para Bipartito los problemas (que es este) las mejoras localmente separables también son siempre mejoras globalmente válidas, por lo que la regla local de cruce de longitudes también se aplica globalmente. (Sin embargo, no estoy seguro de si esto se aplica a los casos no bipartitos, bipartitos es mucho más simple).
– RBarryYoung
27 de marzo de 2012 a las 14:30
-
@RBarryYoung> Ah….mi comentario (que ahora eliminaré) ya no tiene sentido porque el comentario al que estaba respondiendo se eliminó. Estamos de acuerdo.
– dmckee — gatito ex-moderador
27 de marzo de 2012 a las 15:11
saeed amiri
Puede seleccionar una conexión aleatoria y luego, cada vez, eliminar una cruz cambiando las conexiones de sus puntos finales. Esta operación reduce la longitud total (por desigualdad triangular). Dado que el número de formas en que las líneas se cruzan entre sí es finito, en un número finito de pasos llegamos a una solución que no se cruza. En la práctica, debería converger rápidamente.
-
@MasoudM. Estoy 100% seguro de que el cambio de cruces finalmente se detendrá (la longitud total disminuye). Si le importa el tiempo (cuántas veces debe hacer esto), debido a que su programa se ejecuta en máquinas finitas (PC), no tienen algo como épsilon (que podría ser muy pequeño), su precisión está predefinida (por ejemplo 30 bits), por lo que puede completarse pronto. También puede agregar algunas heurísticas en cada paso, para tener una mejor selección en los cambios. Le sugiero que implemente esto (necesita algunas bases en todos los demás algoritmos, como encontrar intersecciones y cambiar algunas de ellas son necesarias en todos los algoritmos).
– Said Amiri
26 de marzo de 2012 a las 14:27
-
La longitud total disminuye pero es finita porque al menos será cero.
– Said Amiri
26 de marzo de 2012 a las 14:29
-
@MasoudM. Una heurística útil es encontrar todos los conflictos en cada paso y resolverlos, luego buscar conflictos nuevamente. Además, si lee los documentos sugeridos de qq3, por supuesto obtendrá una mejor respuesta que esta.
– Said Amiri
26 de marzo de 2012 a las 20:15
-
@MasoudM. Además, si está interesado en esta forma de resolución de problemas, esto se llama “Invarianza” en matemáticas e informática, puede echar un vistazo a Curso KTH sobre esto.
– Said Amiri
26 de marzo de 2012 a las 20:27
-
@AaronJohnSabu, en realidad espero ver el tiempo esperado aleatorio de n^2 o n^3. ¡norte! Creo que no puede ser ni siquiera el peor de los casos, ya que para hacer el peor de los casos, uno tiene que comenzar desde alguna posición X y visitar casi todas las combinaciones posibles mientras resuelve los cruces. Esto suena imposible y demasiado pesimista.
– Said Amiri
23 de marzo de 2021 a las 13:40
Parece que te vendría bien un tipo BSP algoritmo.
masud
Siguiendo la respuesta de qq3 que dice la restricción de intersección es redundante, sólo hay un paso más. Asignar puntos de inicio a puntos finales mientras se minimiza la longitud total. Afortunadamente hay un algoritmo de tiempo polinomial para esto:
algoritmo húngaro es un algoritmo de optimización combinatoria que resuelve el problema de asignación en tiempo polinomial.
Reduce el orden del tiempo de ¡En!) a En3).
¿Quizás algún tipo de tipo topológico?
– KerrekSB
25 de marzo de 2012 a las 19:11
Tampoco sé la respuesta, pero crearía cualquier solución (ignorando los conflictos) y luego resolvería el conflicto individualmente: cuando dos líneas entran en conflicto, parece que cambiar un par de puntos finales resuelve el conflicto. Sin embargo, no estoy seguro de cómo garantizar el progreso.
– Dietmar Kühl
25 de marzo de 2012 a las 19:15
@DietmarKühl: cambiar los puntos finales podría causar que aparezca un conflicto diferente.
–Oliver Charlesworth
25 de marzo de 2012 a las 19:17
@OliCharlesworth: sí, me doy cuenta de esto. Esa es la parte de garantizar el progreso: no funcionará si las cosas se resuelven en una forma creando un ciclo.
– Dietmar Kühl
25 de marzo de 2012 a las 19:21
@Masoud M: ¿Hasta cuántos pares de puntos espera manejar?
– RBarryYoung
25 de marzo de 2012 a las 19:48