Autor Tema: Consulta, camino más corto

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

28 Diciembre, 2020, 09:18 pm
Respuesta #20

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 50,046
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

 No conozco demasiado sobre el asunto. Pero buscando un poco en internet la bibliografía sobre el tema, parece que debido a la complejidad computacional del problema de Steiner euclídeo, se usan también métodos que devuelven soluciones aproximadas pero cuyo cálculo es más rápido. Algunos de ellos utilizan triangulaciones de Delaunay y polígonos de Voronoi.

 Puede leerse sobre el asunto, por ejemplo,  en estos documentos:

Geoffrey Ross Grimwood. "The Euclidean Steiner Tree Problem:Simulated Annealing and Other Heuristics" Tesis, 1994.

Van Laarhoven, Jon William. "Exact and heuristic algorithms for the Euclidean Steiner tree problem." PhD(Doctor of Philosophy) thesis, University of Iowa, 2010.

 Hay también algunos artículos en revistas especializadas pero no los he encontrado en acceso libre.

Saludos.

28 Diciembre, 2020, 09:58 pm
Respuesta #21

martiniano

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

Interesantísimo aporte, Luis. El problema euclídeo de Steiner (hasta que geómetracat lo dijo no sabía que se llamaba así) me está pareciendo muy interesante ya que al parecer admite algoritmos muy diferentes. Estoy francamente encantado de haberme encontrado con él en el foro y con todos estos métodos de resolución.

Gracias. Un saludo.

28 Diciembre, 2020, 11:31 pm
Respuesta #22

ancape

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

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.


Efectivamente, tienes razón en que eliminando uno de los lados de la envoltura convexa, obtenemos menor recorrido. Tomo nota. Si no hiciese falta cercar el predio, tu solución es mejor.

En todo caso, me alegra ver que mi mensaje inicial respecto a Delaunay, Voronoy y Envoltura no iba muy descaminado.

No sabía que estábamos ante un problema aún abierto y del que sólo se conocen soluciones aproximadas que utilizan entre otros métodos, como dice Luis que ha visto en revistas especializadas, Delanauy y Voronoy.

Si sustituyes BG por EG cuando este último segmento es menor, ganas ahorro. En cualquier caso, primero haces toda la red de Delaunay (ver figura 1) y luego se hace la supresión de vértices eligiendo cuando hay varios candidatos al más pequeño.

Sería una buena investigación tratar de buscar una solución exacta bien utilizando Delaunay, Voronoy, Envoltura, bien los de Steiner.

Saludos

29 Diciembre, 2020, 10:03 am
Respuesta #23

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 50,046
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

No sabía que estábamos ante un problema aún abierto y del que sólo se conocen soluciones aproximadas que utilizan entre otros métodos, como dice Luis que ha visto en revistas especializadas, Delanauy y Voronoy.

Un pequeño matiz; de manera precisa, no se trata de que sólo se conocen soluciones aproximadas; de hecho (según entiendo de los documentos adjuntados) se conocen algoritmos que proporcionan soluciones exactas. El problema es que su complejidad computacional es exponencial, \( O(2^n) \). Esto los hace poco eficientes para aplicarlos en la práctica. De ahí que se busquen alternativas heurísticas.

Saludos.

29 Diciembre, 2020, 03:35 pm
Respuesta #24

mathtruco

  • Moderador Global
  • Mensajes: 5,399
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
  • El gran profesor inspira
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.


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.


Ahora comprendí bien lo que mencionan. Efectivamaente, si no añadimos vértices entonces el problema es buscar el árbol recubridor mínimo (algoritmo de Kruskal). Pero, si permitimos poder añadir vértices, entonces es posible hallar caminos de menor costo, y ahí el problema se complica, porque como bien dices no tenemos el grafo inicial para aplicar el algoritmo de Kruskal.



Y bueno, aunque los algoritmos para resolver el problema puedan ser complejos desde el punto de vista de costo computacional, sospecho que el problema original planteado por msacchi puede no ser demasiado grande, y quizás en su problema incluso un algoritmo ineficiente pueda hallar la solución en un tiempo razonable.

29 Diciembre, 2020, 06:13 pm
Respuesta #25

ancape

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

No sabía que estábamos ante un problema aún abierto y del que sólo se conocen soluciones aproximadas que utilizan entre otros métodos, como dice Luis que ha visto en revistas especializadas, Delanauy y Voronoy.

Un pequeño matiz; de manera precisa, no se trata de que sólo se conocen soluciones aproximadas; de hecho (según entiendo de los documentos adjuntados) se conocen algoritmos que proporcionan soluciones exactas. El problema es que su complejidad computacional es exponencial, \( O(2^n) \). Esto los hace poco eficientes para aplicarlos en la práctica. De ahí que se busquen alternativas heurísticas.

Saludos.

Gracias por el matiz. No sabia que el problema matemático estaba resuelto pero la complejidad de la solución es tremenda. ¿La situación es igual que la solución del problema de los cuatro colores?

Saludos