Autor Tema: Consulta, camino más corto

0 Usuarios y 1 Visitante están viendo este tema.

04 Diciembre, 2020, 01:47 pm
Leído 1816 veces

msacchi

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 2
  • País: ar
  • Karma: +0/-0
Estimados,

Buen día, soy nuevo en el foro.
Soy ingeniero civil actualmente desarrollando proyecto de parques eólicos. Un porcentaje importante del costo del proyecto son los caminos que conectan el ingreso al predio con los molinos de viento.
Les consulto que teoría/método/software¿? recomiendan para encontrar el camino más corto para unir todos los molinos (Puntos con coordenadas específicas) y que sea el más corto posible (para ahorrar dinero).
Considerar que se ubican en coordenadas x,y,z, donde z es constante para todos los puntos.
Por ejemplo:
Para un parque de un molino, el camino más corto es una línea recta desde el acceso al molino
Para un parque de dos molinos, son tres puntos (sumando el acceso), se define un triángulo, el camino más corto se consigue descartando el lado más largo del triángulo.

Y si puedo sumarle complejidad a mi consulta, también les consulto para el caso de que hayan condiciones de borde. Por ejemplo: Caminos existentes que quiera aprovechar. Caminos existentes entre coordenadas (x1,y1;x2,y2) no necesariamente coordenadas iguales a alguno de los puntos que quiero conectar.

Espero se entienda, les agradezco sus comentarios.
Espero les guste el desafío.
Muchas gracias

Saludos,
Martín

04 Diciembre, 2020, 07:18 pm
Respuesta #1

mathtruco

  • Moderador Global
  • Mensajes: 5,354
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
  • El gran profesor inspira
Hola msacchi, bienvenido al foro. Me anima cuando un ingeniero reconoce un problema aplicado tan bonito y busca asesoría. Tu problema está en el contexto de teoría de grafos, optimización o investigación de operaciones. Hace unos años me tocó resolver un problema de programación lineal para una empresa eléctrica, fue una experiencia muy buena para ambas partes. En ese momento usamos el software GAMS, ya que era el que tenían en esa empresa, pero no sé si es una buena opción para tu problema. Quizás googleando puedas decidir que sirve, y si es así, creo que puedes descargarlo y probarlo. La versión de prueba tiene una limitación en número de variables, pero no creo que tu problema requiera tantas. Pero insisto, no estoy seguro si sirve para tu problema.

Me parece que problema no sería del camino más corto o vendedor viajero porque en esos problemas no podrías pasar dos veces por una misma arista sin que se sume el costo más de una vez.

Me parece que lo que buscas es un Árbol recubridor mínimo. En particular, el Método de Kruskal. Seguramente está implementado en algún software, pero lo desconozco. De todas formas, el algoritmo no parece difícil de programar.


Y si puedo sumarle complejidad a mi consulta, también les consulto para el caso de que hayan condiciones de borde. Por ejemplo: Caminos existentes que quiera aprovechar. Caminos existentes entre coordenadas (x1,y1;x2,y2) no necesariamente coordenadas iguales a alguno de los puntos que quiero conectar.


En el problema, el "peso" que conecta dos "vértices" (ciudades) es el coste de construir la "arista" (camino) entre ellos. Entonces, si existe un camino construido previamente que conecta dos ciudades, entonces el peso de la arista es es cero.

Por último, debes indicar todos los vértices (ciudades) del grafo y los pesos de las aristas (costos de cada camino). Si quieres puedes crear algunas ciudades artificiales, si tu intuición dice que en tal lugar podría pasar un camino aunque no haya una ciudad.

Cuéntanos cuando termines tu proyecto.

04 Diciembre, 2020, 11:23 pm
Respuesta #2

martiniano

  • Moderador Global
  • Mensajes: 1,619
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola tocayo. Bienvenido al foro.

Les consulto que teoría/método/software¿? recomiendan para encontrar el camino más corto para unir todos los molinos (Puntos con coordenadas específicas) y que sea el más corto posible (para ahorrar dinero).
Considerar que se ubican en coordenadas x,y,z, donde z es constante para todos los puntos.
Por ejemplo:
Para un parque de un molino, el camino más corto es una línea recta desde el acceso al molino
Para un parque de dos molinos, son tres puntos (sumando el acceso), se define un triángulo, el camino más corto se consigue descartando el lado más largo del triángulo.

Y si puedo sumarle complejidad a mi consulta, también les consulto para el caso de que hayan condiciones de borde. Por ejemplo: Caminos existentes que quiera aprovechar. Caminos existentes entre coordenadas (x1,y1;x2,y2) no necesariamente coordenadas iguales a alguno de los puntos que quiero conectar.

Es posible que todavía tengas el problema en fase de definición. No sé si esto te descuadrará mucho pero, por ejemplo, si tienes el acceso y dos molinos en los vértices de un triángulo equilátero de lado unidad y unes los tres puntos con el centro tienes que la longitud total de camino es \( \sqrt[ ]{3} \), que es menos que lo que se obtiene si los unes mediante dos de los lados del triángulo.

Es decir, un problema es el de tener una red de caminos entre un conjunto de vértices y que te tengas que quedar con los caminos que unen todos los vértices con la mínima longitud, que que tengas un conjunto de puntos del plano que tengas que unir mediante caminos y que la suma de las longitudes de estos caminos sea mínima. El primer problema es el que se resuelve como te ha indicado mathtruco, con el algoritmo de Kruskal. El segundo es un tanto más complejo. A este respecto, tal vez te pueda interesar este curioso vídeo divulgativo que se ha adjuntado ya alguna otra vez en el foro.

Un saludo.

23 Diciembre, 2020, 01:34 pm
Respuesta #3

msacchi

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 2
  • País: ar
  • Karma: +0/-0
Estimados,

Muchas gracias por las respuestas y por la orientación.
Excelente las explicaciones, voy a investigar el método que proponen.

Gracias por el Video y los enlaces.

Los mantengo al tanto!
Muchas felicidades,
Martín

23 Diciembre, 2020, 06:41 pm
Respuesta #4

ancape

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 292
  • País: es
  • Karma: +0/-5
  • Sexo: Masculino
El problema que planteas tiene el mismo aspecto que el de la distribución de antenas de telefonía o el control aéreo en un aeropuerto. Se tiene una serie de puntos en el plano y hay que unirlos de determinada manera (triangulación de Delaunay), cercarlos uno a uno (Diagramas de Voronoy)  o hacer una cerca convexa que los contenga a todos (Envoltura convexa). Puedes consultar el enlace

https://es.wikipedia.org/wiki/Triangulaci%C3%B3n_de_Delaunay

El programa gráfico 'Grasshopper' contiene rutinas que calculan los diagramas de Voronoy, triangulación de Delaunay y Envoltura convexa.

Un saludo

23 Diciembre, 2020, 08:51 pm
Respuesta #5

mathtruco

  • Moderador Global
  • Mensajes: 5,354
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
  • El gran profesor inspira
El problema que planteas tiene el mismo aspecto que el de la distribución de antenas de telefonía o el control aéreo en un aeropuerto. Se tiene una serie de puntos en el plano y hay que unirlos de determinada manera (triangulación de Delaunay), cercarlos uno a uno (Diagramas de Voronoy)  o hacer una cerca convexa que los contenga a todos (Envoltura convexa). Puedes consultar el enlace

https://es.wikipedia.org/wiki/Triangulaci%C3%B3n_de_Delaunay

El programa gráfico 'Grasshopper' contiene rutinas que calculan los diagramas de Voronoy, triangulación de Delaunay y Envoltura convexa.

Un saludo

- En la triangulación de Delaunay se crean aristas, y de ser necesario se añaden vértices, de tal forma de que si tomamos la circunferencia inscrita a un triángulo, ésta no contenga vértices de otros triángulos. ¿Qué relación tiene con el problema original?

- Tampoco veo que la definición de Diagramas de Voronoi tenga alguna relación con el problema.

- Mucho menos se está buscando la envoltura convexa, ¿para qué?

La única relación que veo entre el problema original y los tres conceptos que mencionas es que obtenemos un dibujo que conecta a todos los vértices.

23 Diciembre, 2020, 11:30 pm
Respuesta #6

ancape

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 292
  • País: es
  • Karma: +0/-5
  • Sexo: Masculino
El problema que planteas tiene el mismo aspecto que el de la distribución de antenas de telefonía o el control aéreo en un aeropuerto. Se tiene una serie de puntos en el plano y hay que unirlos de determinada manera (triangulación de Delaunay), cercarlos uno a uno (Diagramas de Voronoy)  o hacer una cerca convexa que los contenga a todos (Envoltura convexa). Puedes consultar el enlace

https://es.wikipedia.org/wiki/Triangulaci%C3%B3n_de_Delaunay

El programa gráfico 'Grasshopper' contiene rutinas que calculan los diagramas de Voronoy, triangulación de Delaunay y Envoltura convexa.

Un saludo


 

- En la triangulación de Delaunay se crean aristas, y de ser necesario se añaden vértices, de tal forma de que si tomamos la circunferencia inscrita a un triángulo, ésta no contenga vértices de otros triángulos. ¿Qué relación tiene con el problema original?

- Tampoco veo que la definición de Diagramas de Voronoi tenga alguna relación con el problema.

- Mucho menos se está buscando la envoltura convexa, ¿para qué?

La única relación que veo entre el problema original y los tres conceptos que mencionas es que obtenemos un dibujo que conecta a todos los vértices.

Creo que no estás muy informado de que los tres conceptos están muy relacionados y que la triangulación de Delaunay es un problema dual de la partición de Voronoy. El problema de la envoltura convexa. que también está relacionado íntimamente con ambos permite construir el mínimo polígono convexo que contiene a una familia de puntos del plano y así cercarlos con una valla con longitud mínima posible.

En cuanto a la triangulación de Delaunay, permite unir los puntos de un conjunto plano mediante segmentos de forma que los triángulos formados sean lo mas equiláteros posible o lo que es equivalente a la existencia de los círculos de que hablas. El triángulo equilátero es el que tiene menos perímetro con igual área. ¿Tiene algo que ver el problema planteado o son imaginaciones mías?.

Ah¡¡ ¿qué es eso de crear aristas y en caso necesario añadir vértices?

Saludos

24 Diciembre, 2020, 08:44 am
Respuesta #7

martiniano

  • Moderador Global
  • Mensajes: 1,619
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

Ciertamente parece que msacchi todavía no tenía el problema muy bien definido al abrir el hilo. Aún así, por el contexto que expone, yo creo que el problema que quiere resolver es el de hallar un camino de longitud mínima que una una serie de puntos. También entiendo que el camino no tiene por qué ser recto entre dos vértices contiguos.

La verdad es que no veo como le puede ayudar a eso ni el algoritmo de Kruskall ni el de Delaunay. Si alguien cree que sí, podría explicar cómo resolver algún caso particular sencillo del problema de msacchi a partir de su propuesta, por ejemplo, al caso de un triángulo.

Ancape. Deberías evitar ciertas fórmulas a la hora de defender tus posturas. La comunicación por canales telemáticos ya tiene de por sí sus carencias, lo que hace que tengamos que ser especialmente cuidadosos si queremos conseguir unos mínimos de armonía y equilibrio en la convivencia del foro. Concretamente, veo que te cuesta mantener una cierta horizontalidad con el receptor de tus mensajes.

Creo que no estás muy informado de que los tres conceptos están muy relacionados y que la triangulación de Delaunay es un problema dual de la partición de Voronoy.

En esta frase haces dos cosas. Una, hacer una presuposición sobre la información que tiene mathtruco con respecto a los algoritmos que propones y otra, exponer que existe una relación concreta entre dos problemas diferentes. La primera claramente sobra.

En cuanto a la triangulación de Delaunay, permite unir los puntos de un conjunto plano mediante segmentos de forma que los triángulos formados sean lo mas equiláteros posible o lo que es equivalente a la existencia de los círculos de que hablas. El triángulo equilátero es el que tiene menos perímetro con igual área. ¿Tiene algo que ver el problema planteado o son imaginaciones mías?.

La pregunta del final del párrafo es desafiante. Más cuando en realidad no has aportado argumentos que evidencien claramente una relación entre el problema de msacchi y el de Delaunay. Lo mejor es que intentes aplicarlo a un caso concreto y lo comentemos. Al margen de esto, si uno contesta adoptando tu misma actitud podrían esperarse respuestas tan desafortunadas como tu pregunta. A lo que nuevamente se esperarían contrarréplicas semejantes por tu parte. Y de ese bucle no saldríamos.

Ah¡¡ ¿qué es eso de crear aristas y en caso necesario añadir vértices?

Ahí substituyes algo que ha dicho mathtruco por un "eso" un tanto despectivo, que al substituirlo también por un "qué" suena más despectivo todavía. Una fórmula alternativa que mantiene la horizontalidad de la que te hablo podría ser: "No he acabado de entender qué quieres decir con lo de crear aristas y en caso necesario añadir vértices". Fíjate que aquí se deja abierta una posibilidad de que al emisor se le haya escapado algo. Dejar abierta esa posibilidad es siempre muy deseable, por muchas evidencias que haya de que es el receptor el que está confundido.

Espero que entiendas todo esto.

Un saludo.

28 Diciembre, 2020, 12:24 am
Respuesta #8

mathtruco

  • Moderador Global
  • Mensajes: 5,354
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
  • El gran profesor inspira

Creo que no estás muy informado de que los tres conceptos están muy relacionados y que la triangulación de Delaunay es un problema dual de la partición de Voronoy.


Decir que ese problema es el dual de otro no ayuda en nada a la respuesta, porque la pregunta original es otra.

¿Cómo representarías los caminos existentes en lo que propones? (lee nuevamente la pregunta).


El problema de la envoltura convexa. que también está relacionado íntimamente con ambos permite construir el mínimo polígono convexo que contiene a una familia de puntos del plano y así cercarlos con una valla con longitud mínima posible.


Esto tampoco tiene relación con la pregunta original. No se está buscando un camino que conecte a todos los nodos de la frontera (que sería la envoltura convexa que mencionas, la "valla").

Por otra parte, ¿Por qué estaríamos interesados en el el polígono que encierra todos los puntos sea convexo?



En cuanto a la triangulación de Delaunay, permite unir los puntos de un conjunto plano mediante segmentos de forma que los triángulos formados sean lo mas equiláteros posible o lo que es equivalente a la existencia de los círculos de que hablas. El triángulo equilátero es el que tiene menos perímetro con igual área. ¿Tiene algo que ver el problema planteado o son imaginaciones mías?.

Ah¡¡ ¿qué es eso de crear aristas y en caso necesario añadir vértices?

Saludos

La única forma de que tengan sentido los comentarios es que vayamos respondiendo a lo que se pregunta. Te pregunté qué relación eso de construir triángulos "lo más equiláteros posibles" con el problema original, ¿Puedes responderlo?

Sobre lo que me comentas, al hacer un dibujo del problema, las aristas serían los caminos y los vértices serían las ciudades (por donde sí o sí debe pasar un camino). No veo razón para no añadir vértices (ciudades ficticias), lo que sería equivalente a imponer que el camino debe pasar por ahí.


Nota que yo respondí uno a uno los comentarios que me hiciste. Espero que repondas a cada comentario que hice, uno a uno.


28 Diciembre, 2020, 12:44 am
Respuesta #9

ancape

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 292
  • País: es
  • Karma: +0/-5
  • Sexo: Masculino

Creo que no estás muy informado de que los tres conceptos están muy relacionados y que la triangulación de Delaunay es un problema dual de la partición de Voronoy.


Decir que ese problema es el dual de otro no ayuda en nada a la respuesta, porque la pregunta original es otra.

¿Cómo representarías los caminos existentes en lo que propones? (lee nuevamente la pregunta).


El problema de la envoltura convexa. que también está relacionado íntimamente con ambos permite construir el mínimo polígono convexo que contiene a una familia de puntos del plano y así cercarlos con una valla con longitud mínima posible.


Esto tampoco tiene relación con la pregunta original. No se está buscando un camino que conecte a todos los nodos de la frontera (que sería la envoltura convexa que mencionas, la "valla").

Por otra parte, ¿Por qué estaríamos interesados en el el polígono que encierra todos los puntos sea convexo?



En cuanto a la triangulación de Delaunay, permite unir los puntos de un conjunto plano mediante segmentos de forma que los triángulos formados sean lo mas equiláteros posible o lo que es equivalente a la existencia de los círculos de que hablas. El triángulo equilátero es el que tiene menos perímetro con igual área. ¿Tiene algo que ver el problema planteado o son imaginaciones mías?.

Ah¡¡ ¿qué es eso de crear aristas y en caso necesario añadir vértices?

Saludos

La única forma de que tengan sentido los comentarios es que vayamos respondiendo a lo que se pregunta. Te pregunté qué relación eso de construir triángulos "lo más equiláteros posibles" con el problema original, ¿Puedes responderlo?

Sobre lo que me comentas, al hacer un dibujo del problema, las aristas serían los caminos y los vértices serían las ciudades (por donde sí o sí debe pasar un camino). No veo razón para no añadir vértices (ciudades ficticias), lo que sería equivalente a imponer que el camino debe pasar por ahí.


Nota que yo respondí uno a uno los comentarios que me hiciste. Espero que repondas a cada comentario que hice, uno a uno.

Cuando se propone un problema a desarrollar como tema de tesis, la labor del director de la tesis no es darle el problema resuelto completamente. Ni siquiera se le pide al tesinando que haga un problema que previamente el director ya haya resuelto pero no publicado. La ayuda consiste en emplear los años de experiencia que uno tiene para prever que los caminos que se indican tienen el aspecto que hace presagiar buenos resultados.
¡Ah! no estoy de acuerdo con algún comentario que he visto en este hilo como que tal vez los caminos de mínima distancia no sean rectos.

Saludos y perdón por no responder antes. No había reparado en que tenía respuestas pendientes.