Autor Tema: Consulta, camino más corto

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

28 Diciembre, 2020, 07:12 am
Respuesta #10

mathtruco

  • Moderador Global
  • Mensajes: 5,401
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
  • El gran profesor inspira
En tu primer mensaje sólo has puesto un par de definiciones de conceptos que no sirven para nada porque no están relacionados con el problema. Cuando te pregunto qué relación tiene esas definiciones con el problema simplemente respondes algo inútil y sin relación con mis comentarios:


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.

Lo único que has puesto es que no estás de acuerdo con algunas cosas (más de una), pero sólo has indicado una: Sólo has puesto que no estás de acuerdo con que los caminos no sean rectos. Pero si miras el enunciado, hay caminos ya hechos, que tendrían costo cero, por lo que tiene sentido intentar usarlos, y estos sí pueden ser caminos no rectos. En el caso que no comiencen o terminen en vértices podría ser buena opción añadir vértices al problema.


28 Diciembre, 2020, 07:25 am
Respuesta #11

sugata

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,181
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
.

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

Cuando respondes tienes un botón que dice:"Notificarme nuevas respuestas"
Así no se te escapa nada.

28 Diciembre, 2020, 11:42 am
Respuesta #12

martiniano

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

¡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.

Además de lo que dice mathtruco, aquí abajo me cito a mí mismo en un ejemplo sencillo que puse en el que la red de caminos de longitud mínima no está formada por caminos rectos entre dos vértices.

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.

Un saludo.

28 Diciembre, 2020, 02:02 pm
Respuesta #13

geómetracat

  • Moderador Global
  • Mensajes: 2,662
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
El problema de unir \( n \) puntos dados del plano con caminos de longitud mínima parece que se conoce con el nombre de problema de Steiner euclídeo. En este documento parece que hay mucha información. En particular, el algoritmo de Melzak parece que resuelve el problema.

Lo que es fácil de ver con métodos elementales es que la solución debe ser un árbol, es decir, un conjunto de vértices (que incluye los puntos iniciales a unir, pero puede tener más) unidos por segmentos rectos. Por un lado, si tienes algún segmento curvo, puedes conseguir un camino más corto acortando por un segmento recto. Luego la solución debe ser un grafo. Además, no puede tener ciclos pues en ese caso puedes eliminar una arista del ciclo y obtienes un camino que une todos los puntos de longitud menor.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

28 Diciembre, 2020, 02:56 pm
Respuesta #14

martiniano

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

El problema de unir \( n \) puntos dados del plano con caminos de longitud mínima parece que se conoce con el nombre de problema de Steiner euclídeo. En este documento parece que hay mucha información. En particular, el algoritmo de Melzak parece que resuelve el problema.

Perfecto geómetracat.  :aplauso: Esto es lo que andaba yo buscando, ya que entendí que es el problema que propuso msacchi.

Gracias. Un saludo.

28 Diciembre, 2020, 03:32 pm
Respuesta #15

mathtruco

  • Moderador Global
  • Mensajes: 5,401
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
  • El gran profesor inspira
Efectivamente, parece que por ahí va la respuesta.

Sólo reafirmar que no parece tan mala idea añadir nodos/vértices, digo esto en relación al comentario de ancape (acá va un pantallazo del documento que compartió geómetracat)



postdata:


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.


Yo trataría de resolver el problema olvidándonos de los caminos existentes. Si la solución de este problema modificado usa los caminos preexistentes, entonces puede ser una solución suficientemente buena. Ojo que en este tipo de problemas puede existir más de una solución óptima, o pueden haber varias soluciones cercanas a la óptima, así que en la práctica no es necesario buscar "la" solución (si una solución cuesta en total 100 dólares más que otra, en la práctica ambas soluciones son igualmente buenas o malas).

Tienes razón que al considerar caminos preexistentes habría que pensar cómo modificar el algoritmo original para que resuelva tu problema. Al menos yo no veo una forma sencilla de hacer la modificación en este momento, pero sospecho no es difícil.

Quedaría pendiente sugerir un software. Como el algoritmo es famoso seguro existirá un software que lo traiga implementado, y si no puede ser que sea fácil de implementar. (No he revisado el algoritmo para decidir si es fácil de implementar).

28 Diciembre, 2020, 05:30 pm
Respuesta #16

mathtruco

  • Moderador Global
  • Mensajes: 5,401
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
  • El gran profesor inspira
Hola martiniano. Estaba releyendo el hilo completo y advertí que habías comentado algo relacionado a mi respuesta y yo no dije nada. Disculpa por no responderlo, no me había dado cuenta hasta ahora.

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.


A mí me parece que con la información que da es suficiente.

Por otra parte, no es el problema del camino mínimo, porque acá podemos ir de ida y vuelta de un punto a otro sin que el costo se multiplique por dos (una vez que construimos el camino podemos pasar por él sin costo). Me autocito.


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.




La verdad es que no veo como le puede ayudar a eso ni el algoritmo de Kruskall


No tiene sentido crear ciclos, porque habríamos creado un camino extra. Por esto lo que se busca es un árbol. Y un árbol recubridos, porque debe conectar todos los vértices. Y un árbos recubridor mínimo porque el costo debe ser mínimo. Y el algoritmo que cito busca eso: el árbol recubridor mínimo.

No tengo problema si adviertes un error en mi razonamiento, pero yo lo veo claro.

28 Diciembre, 2020, 05:42 pm
Respuesta #17

geómetracat

  • Moderador Global
  • Mensajes: 2,662
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
El problema que veo yo con el algoritmo de Kruskal y los árboles recubridores mínimos, es que eso asume que tienes ya de entrada un grafo que une todos los puntos. Pero por lo menos en la versión original del problema, sin caminos construidos, la cuestión es más bien encontrar el árbol en el plano de entre todos los árboles posibles que tengan los puntos originales como vértices de longitud mínima.
Es decir, en el algoritmo de Kruskal tienes un grafo de entrada y encuentras el árbol recubridor que tiene longitud total mínima, mientras que en este problema solamente tienes los puntos y debes construir tú el árbol.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

28 Diciembre, 2020, 07:41 pm
Respuesta #18

ancape

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 292
  • País: es
  • Karma: +0/-5
  • Sexo: Masculino
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

A pesar de todas las criticas que he recibido en este hilo del foro, creo que los conceptos Diagrama de Delaunay, Voronoy y Envoltura convexa, son aplicables al problema que planteas y existen rutinas en Grasshopper o Geogebra que los calculan de manera sencilla sin recurrir a temas un poco esotéricos para ti como la Teoría de Grafos que para un matemático están muy bien (si los entiende) pero no para un ingeniero que debe preocuparse de cosas mas tangibles.

Hipótesis previas
1-   La frase “el camino mas corto” indica que debe buscarse un camino que haga que podamos acceder a todos los molinos y que tenga la longitud total lo más corta posible. Un camino que pase por un molino de forma que se vea muy cerca otro molino pero que para llegar a él tengamos que dar un rodeo pues no hay camino trazado entre los dos molinos cercanos entre sí, se desecha si hay otro más corto que recorre todos los molinos.
2-   La complejidad que pueda sumarse a la consulta, como aprovechamiento de caminos existentes o recorridos prohibidos forman un segundo problema que no hay que mezclar con el primero.

Propuesta de solución
1-   Elegimos un molino como punto inicial del recorrido
2-   De todos los triángulos que barren un área, el triángulo equilátero es el que tiene menor perímetro, esto no da idea de hacer de los molinos los vértices de una red de triángulos lo mas parecidos a triángulos equiláteros que cubran todo el predio de los molinos. Esta red de triángulos es precisamente el Diagrama de Delaunay de los puntos que representan los molinos.
 [attachment id=0]
3-   Ahora eliminamos los segmentos comunes a cada dos triángulos, cuidando de no dejar puntos interiores a la envoltura convexa (que también será la valla de longitud mínima si queremos cercar el predio) aislados. Obtenemos algo así:
  [attachment id=1]
He hecho varias pruebas con Geogebra y el camino que señalo en verde tiene longitud total mas pequeña que cualquier otro que haga posible ir desde la entrada hasta cualquier molino, pero matemáticamente no lo puedo afirmar. La afirmación de que como el triángulo equilátero es el que ocupa mayor área con un perímetro dado, la mejor descomposición de un área es con este tipo de triángulos, es intuitiva pero no matemáticamente rigurosa.

El vídeo de las pompas de jabón que adjunta martiniano es bastante superficial. Por ejemplo, cuando habla y enseña la mejor manera de unir tres puntos con pompas de jabón, no tiene en cuenta que en no todos los triángulos podemos encontrar un punto que vea los vértices bajo ángulo de 120º. En el artefacto que enseña los tres ejes de acero forman un triángulo equilátero.
 
  [attachment id=2]
  [attachment id=3]

Cómo verás el recorrido fundamental del camino es la valla que debe cercar los molinos del predio y que es la envoltura convexa de los puntos que representan los molinos, lo cual es lógico pues la envoltura convexa es la poligonal que cerca un conjunto de puntos dado de la forma mas económica posible.


28 Diciembre, 2020, 08:47 pm
Respuesta #19

martiniano

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

Hola martiniano. Estaba releyendo el hilo completo y advertí que habías comentado algo relacionado a mi respuesta y yo no dije nada. Disculpa por no responderlo, no me había dado cuenta hasta ahora.

Por supuesto, no faltaba más  ;).

Por otra parte, no es el problema del camino mínimo, porque acá podemos ir de ida y vuelta de un punto a otro sin que el costo se multiplique por dos (una vez que construimos el camino podemos pasar por él sin costo). Me autocito.

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.

Estamos de acuerdo. No creo que sea ninguno de esos problemas el que propuso msacchi.

No tiene sentido crear ciclos, porque habríamos creado un camino extra. Por esto lo que se busca es un árbol. Y un árbol recubridos, porque debe conectar todos los vértices. Y un árbos recubridor mínimo porque el costo debe ser mínimo. Y el algoritmo que cito busca eso: el árbol recubridor mínimo.

No tengo problema si adviertes un error en mi razonamiento, pero yo lo veo claro.

Un poco en la línea de lo que te dice geómetracat, lo que yo veo es que la red de caminos buscada no tiene por qué ser recta entre dos de los vértices dados. Esto último es, precisamente, lo que yo pienso que no quedaba del todo claro en el planteamiento de msacchi. Otra cosa es que después de introducir nuevos vértices a los dados por el enunciado, sí que la solución la pueda arrojar el algoritmo de Kruskall, pero el algoritmo que buscamos debe decir cuáles son esos vértices que debemos añadir.

El contraejemplo que pensaba que iba a ilustrar todo esto es el que propuse unas respuestas atrás en el que se nos dan los vértices de un triángulo equilátero de lado unidad. Si asumimos que la red de caminos buscada está formada sólo por segmentos que unan esos vértices, es decir, los lados del triángulo en sí, y aplicamos al grafo correspondiente el algoritmo de Kruskal, obtendremos un árbol formado por dos de los lados del triángulo, es decir, una red de caminos de longitud total dos. Sin embargo, si unimos cada vértice del triángulo con el centro del mismo obtenemos una red de longitud \( \sqrt[ ]{3}<2 \). ¿Me he explicado bien? Si hay algo que no ha quedado del todo claro, por favor insiste.

A pesar de todas las criticas que he recibido en este hilo del foro, creo que los conceptos Diagrama de Delaunay, Voronoy y Envoltura convexa, son aplicables al problema que planteas y existen rutinas en Grasshopper o Geogebra que los calculan de manera sencilla sin recurrir a temas un poco esotéricos para ti como la Teoría de Grafos que para un matemático están muy bien (si los entiende) pero no para un ingeniero que debe preocuparse de cosas mas tangibles.

Las presuposiciones que haces sobre qué es esotérico para msacchi o qué le debe preocupar son irrelevantes, parecen infundadas y están algo fuera de lugar.

Hipótesis previas
1-   La frase “el camino mas corto” indica que debe buscarse un camino que haga que podamos acceder a todos los molinos y que tenga la longitud total lo más corta posible. Un camino que pase por un molino de forma que se vea muy cerca otro molino pero que para llegar a él tengamos que dar un rodeo pues no hay camino trazado entre los dos molinos cercanos entre sí, se desecha si hay otro más corto que recorre todos los molinos.
2-   La complejidad que pueda sumarse a la consulta, como aprovechamiento de caminos existentes o recorridos prohibidos forman un segundo problema que no hay que mezclar con el primero.

Propuesta de solución
1-   Elegimos un molino como punto inicial del recorrido
2-   De todos los triángulos que barren un área, el triángulo equilátero es el que tiene menor perímetro, esto no da idea de hacer de los molinos los vértices de una red de triángulos lo mas parecidos a triángulos equiláteros que cubran todo el predio de los molinos. Esta red de triángulos es precisamente el Diagrama de Delaunay de los puntos que representan los molinos.
 [attachment id=0 msg=459137]
3-   Ahora eliminamos los segmentos comunes a cada dos triángulos, cuidando de no dejar puntos interiores a la envoltura convexa (que también será la valla de longitud mínima si queremos cercar el predio) aislados. Obtenemos algo así:
  [attachment id=1 msg=459137]
He hecho varias pruebas con Geogebra y el camino que señalo en verde tiene longitud total mas pequeña que cualquier otro que haga posible ir desde la entrada hasta cualquier molino, pero matemáticamente no lo puedo afirmar. La afirmación de que como el triángulo equilátero es el que ocupa mayor área con un perímetro dado, la mejor descomposición de un área es con este tipo de triángulos, es intuitiva pero no matemáticamente rigurosa.

Me temo que la condición de cercar el predio la acabas de introducir ahora mismo. Sin esa condición está bastante claro que tu propuesta no funciona ya que si eliminas cualquiera de las aristas de la envoltura convexa sigues teniendo todos los vértices unidos por una red de longitud menor. Pero aún teniendo en cuenta la condición de que debemos incluir en la solución la envoltura convexa, el algoritmo que propones no funciona. Fíjate que en tu enunciado particular podríamos suponer \( BG<EG \), por lo que si en la solución que propones substituimos una arista por la otra la longitud total de la red disminuye manteniéndose todos los vértices unidos.

Un saludo.