no se cortan segmentos de línea y reducir al mínimo la longitud acumulada

me gustaría encontrar un mejor algoritmo para resolver el siguiente problema:no se cortan segmentos de línea y reducir al mínimo la longitud acumulada

Hay N puntos de partida (púrpura) y N puntos de destino (verde) en 2D. Quiero un algoritmo que conecte los puntos de partida con los puntos objetivo por un segmento de línea (marrón) sin que ninguno de estos segmentos se intersecte (rojo) y minimice la longitud acumulativa de todos los segmentos.

Mi primer esfuerzo en C++ fue permutar todos los estados posibles, encontrar estados libres de intersección, y entre ellos el estado con longitud mínima de segmento total O (n!). Pero creo que tiene que haber una mejor manera.

enter image description here

Alguna idea? O buenas palabras clave para la búsqueda?

Fuente

2012-03-25 deepmax

¿Tal vez algún tipo de tipo topológico? –

No sé la respuesta tampoco, pero crearía cualquier solución (ignorando conflictos) y luego resolvería el conflicto individualmente: cuando dos líneas entran en conflicto, parece que el cambio de un par de puntos finales resuelve el conflicto. Aunque no estoy seguro de cómo garantizar el progreso. –

@ DietmarKühl: Cambiar los puntos finales podría causar que aparezca un conflicto diferente. –

Esto es Minimum Euclidean Matching in 2D. El enlace contiene una bibliografía de lo que se sabe sobre este problema. Dado que se 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 descruzando.

Fuente

2012-03-25 19:37:23 qq3

@Walkerneo, no está cruzando las piernas, porque la distancia entre tus pies y la distancia entre tus caderas es más corta que la longitud de tus piernas. – zzzzBov

@ qq3: Estrictamente hablando, creo que esto es * Concordancia euclidiana mínima * bipartita *, un subconjunto mencionado en su enlace. – RBarryYoung

@dmckee: qq3 dijo que la regla sin intersección era * redundante * bajo la restricción de longitud total mínima, no "en conflicto" con ella (matemáticamente, estas son * muy * cosas diferentes). Y para los problemas * bipartitos * (que este es), las mejoras separables localmente también son siempre mejoras globalmente válidas, por lo que la regla local de cruce de longitud también se aplica globalmente. (No estoy seguro si esto se aplica a los casos no bipartitos, sin embargo, Bipartite es mucho más simple). – RBarryYoung

Parece que se podría utilizar un algoritmo BSP-type.

Fuente

2012-03-25 19:11:50 Krumelur

Puede seleccionar una conexión aleatoria, luego cada vez que borre una cruz (de hecho, cambie la conexión de sus puntos finales), este algoritmo funciona y finaliza en pasos finitos. puede ser que digas que al cambiar de cruces causa una cruz nueva, no importa, cada vez que cambias una cruz, vas a minimizar la duración total de tu respuesta y de esta manera no puede ser infinita (porque la longitud total de las líneas es finita). En realidad funciona en O (F * n^2) donde F= sum of all line segments * power of 10 (para hacerlo entero). Este O es muy optimista, creo que si pruebas este simple algoritmo, funcionará bien. Claro que es mucho mejor que la fuerza bruta en general.

Fuente

2012-03-25 22:14:42

@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 hacerlo), porque su programa se ejecuta en máquinas finitas (PC), no tiene algo como epsilon (que podría ser muy pequeño), su precisión está predefinida (por ejemplo, 30 bit), 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. Sugiero que implemente esto (necesita algunas bases en todos los otros algoritmos, como encontrar intersección y cambiar algunos de ellos, que son necesarios en todos los algoritmos). –

La longitud total disminuye pero es finita porque al menos será cero. –

@MasoudM. Una heurística útil es encontrar todos los conflictos en cada paso y resolverlos, luego buscar conflictos otra vez. Además, si lees los artículos sugeridos de qq3, por supuesto obtendrás una mejor respuesta que esta. –

Uso este algoritmo con el fin O (n):

Hungarian algorithm es un algoritmo de optimización combinatoria que resuelve el problema de la asignación en tiempo polinómico.

¿Cómo puede ayudar? Bueno, encontrará la longitud mínima acumulativa. Pero ...

CUANDO LA LONGITUD TOTAL ES MÍNIMA, NO HAY INTERSECCIÓN.

Así que, como @ QQ3 dijo que la restricción de intersección es redundante y después de eliminar esta limitación, se puede reducir el orden de O (n!)-O (n).

Fuente

2013-03-19 17:13:24 deepmax

no se cortan segmentos de línea y reducir al mínimo la longitud acumulada

Respuesta

Cuestiones relacionadas