21/01/2019, 07:13:44 am *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Puedes practicar LATEX con el cómodo editor de Latex online
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Variaciones del algoritmo de Dijkstra.  (Leído 597 veces)
0 Usuarios y 1 Visitante están viendo este tema.
martiniano
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 627


Ver Perfil
« : 04/01/2019, 04:58:41 am »

Hola.

Reescribo un interesante problema que originalmente fue subido por una nueva usuaria llamada Pendeja. Al hacerlo violó unas cuantas de las reglas del foro y manooooh se tomó la molestia de indicárselo y de adaptar el mensaje a las reglas. Ambos mensajes fueron borrados no se sabe por qué. Por suerte, una de las reglas que Pendeja violó fue que adjuntó un pdf con el enunciado en lugar de teclearlo directamente y he encontrado ese pdf entre los archivos de mi móvil, por lo que voy a poder reproducir el enunciado tal cual.  :sonrisa_amplia: Allá va:

------------------------------------------------------------------------------------------------------------

Consideremos la siguiente red dirigida con 16 nodos y 33 aristas (los vértices están numerados del 1 al 16),



en la que, además, se supone dado el dato de la distancia de cada arista, que llamaremos [texx]d_{ij}[/texx], distancia de la arista [texx]i\rightarrow{j}[/texx].

Primero plantead el problema de la ruta mínima en esta red partiendo del nodo 1 y llegando al nodo
16. Es decir cuál es la ruta más corta que debe seguir un vehículo para llegar de 1 a 16.

Tras ello vais a plantear dos variaciones sobre el problema de la ruta mínima:

1. Considerar primero que son dos los vehículos que parten del nodo 1 y deben llegar al nodo 16, pero
deben seguir rutas diferentes, esto es, ambas rutas no pueden compartir aristas ni nodos (excepto
el 1 y el 16). Se busca minimizar la suma de las distancias de las dos rutas.

2. Volvemos al problema con un solo vehículo, pero ahora con la condición adicional de que, al menos,
debe atravesar 5 aristas, y se busca, como siempre, minimizar la distancia recorrida.

Se pide:

* Plantead cada versión del problema de forma genérica, es decir, sin valores concretos de las distancias.

* Resolved los tres problemas (ruta mínima y sus dos variaciones) con las siguientes distancias de
las aristas: [texx]d_{ij}=i+j[/texx]

* Proponed una asignación de distancias diferente que dé lugar a respuestas diferentes de los problemas.

Todo el contenido matemático debe estar completamente justificado.

----------------------------------------------------------------------------------

Pendeja dijo que le habían explicado y entendía el algoritmo original de ruta mínima (también llamado de Dijkstra) y también, con razón, que el apartado clave y en el que tenía dificultades era el primero, es decir, en el que se pide las dos variaciones del algoritmo de Dijkstra. Yo le he dado alguna que otra vuelta pero no he llegado a nada definitivo.

Un saludo.

* grafo_dijkstra.png (61.64 KB - descargado 103 veces.)
En línea
manooooh
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 1.721


Ver Perfil
« Respuesta #1 : 04/01/2019, 05:02:48 am »

Hola

¡Qué bueno que hayas podido encontrar el PDF! :sonrisa_amplia:.

¿Conocés propiedades, definiciones o lo que sea que hable sobre "rutas mínimas"? Es un problema interesante.

Saludos
En línea
sugata
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 2.188


Ver Perfil
« Respuesta #2 : 04/01/2019, 05:55:25 am »

Le echaré un ojo a mi libro de grafos. No he leído mucho de ello.
En línea
martiniano
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 627


Ver Perfil
« Respuesta #3 : 04/01/2019, 07:52:29 am »

Hola.

¿Conocés propiedades, definiciones o lo que sea que hable sobre "rutas mínimas"?

Con "ruta mínima" entre dos vértices el enunciado se refiere al camino que une los vértices de manera que la suma de las aristas por las que pasa sea la mínima de entre todos los caminos que unen los vértices.

Estoy un poco como Pendeja, la verdad, entiendo y he trabajado con el algoritmo de Dijkstra, y también con el de Floyd. Pero no consigo modificarlos con éxito para poder aplicar alguno de ellos al enunciado.

Le echaré un ojo a mi libro de grafos. No he leído mucho de ello.

¿Te importaría indicarme cómo se llama el libro de grafos que manejas?

Saludos y gracias.
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 7.625



Ver Perfil
« Respuesta #4 : 04/01/2019, 08:08:32 am »


Hola.

Yo esto no lo he estudiado pero lo he visto en el “cine” (en internet, en en páginas, en vídeos...) y los métodos son fáciles de entender pero muchas veces pesados. En el fondo, se trata del famoso problema del viajante, en el cuál, a medida que metemos más nodos, aumenta el tiempo de resolución exponencialmente.
Por los ejemplo que tengo vistos por ahí, 16 nodos son muchos, me parece, se van a traducir en mucho tiempo para encontrar el camino más corto mediante el algoritmo  Dijkstra y otros similares relacionados con el “vecino más cercano”; y no existe solución al problema del aumento tan grande del tiempo en la resolución (de momento; y el que dé la solución se gana un millón de dólares).

Sí existen otros algoritmos que dan una solución óptima en poco tiempo, pero no siempre tendremos la suerte que sea la más corta, será una de las más cortas.

Ahora bien, ese mapa tiene una simetría, es un rectángulo, y quizá exista algún algoritmo-atajo, no lo sé; sólo conozco esto como curioso, un poco por encima.

Saludos.
En línea

Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 43.466


Ver Perfil
« Respuesta #5 : 04/01/2019, 08:26:02 am »

Hola

 Si no me equivoco es el apartado (b) de este problema:

http://www.me.utexas.edu/~jensen/or_site/problems/unit/net_mod/problem/netmod545.html

 Y viene resuelto aquí:

https://s2.smu.edu/~olinick/emis8374/assignments/assignments06/HW4/hw4sol.pdf

Saludos.
En línea
sugata
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 2.188


Ver Perfil
« Respuesta #6 : 04/01/2019, 08:41:41 am »

Hola.

¿Conocés propiedades, definiciones o lo que sea que hable sobre "rutas mínimas"?

Con "ruta mínima" entre dos vértices el enunciado se refiere al camino que une los vértices de manera que la suma de las aristas por las que pasa sea la mínima de entre todos los caminos que unen los vértices.

Estoy un poco como Pendeja, la verdad, entiendo y he trabajado con el algoritmo de Dijkstra, y también con el de Floyd. Pero no consigo modificarlos con éxito para poder aplicar alguno de ellos al enunciado.

Le echaré un ojo a mi libro de grafos. No he leído mucho de ello.

¿Te importaría indicarme cómo se llama el libro de grafos que manejas?

Saludos y gracias.

Es el libro de matemáticas discretas de la UNED. Contiene teoría de números, combinatoria y grafos, así que no creo que lo trate muy en profundidad.
En línea
martiniano
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 627


Ver Perfil
« Respuesta #7 : 04/01/2019, 09:56:44 am »

Hola.

Yo esto no lo he estudiado pero lo he visto en el “cine” (en internet, en en páginas, en vídeos...) y los métodos son fáciles de entender pero muchas veces pesados. En el fondo, se trata del famoso problema del viajante, en el cuál, a medida que metemos más nodos, aumenta el tiempo de resolución exponencialmente.

Creo que estás confundido. No veo que se trate del problema del viajante. El problema del viajante busca el camino de costo mínimo que pasa por todos los vértices de un grafo, que es el problema que tiene un viajante que quiere visitar unas ciertas ciudades y quiere hacerlo recorriendo la mínima distancia por carretera.


¡Qué buena! Gracias. Me lo miraré tranquilamente este fin de semana.

Parece que la respuesta a esto:

2. Volvemos al problema con un solo vehículo, pero ahora con la condición adicional de que, al menos,
debe atravesar 5 aristas, y se busca, como siempre, minimizar la distancia recorrida.

Es también el apartado d)

Es el libro de matemáticas discretas de la UNED. Contiene teoría de números, combinatoria y grafos, así que no creo que lo trate muy en profundidad.

Gracias.

Un saludo a todos.
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 7.625



Ver Perfil
« Respuesta #8 : 04/01/2019, 10:57:03 am »


Creo que estás confundido. No veo que se trate del problema del viajante. El problema del viajante busca el camino de costo mínimo que pasa por todos los vértices de un grafo, que es el problema que tiene un viajante que quiere visitar unas ciertas ciudades y quiere hacerlo recorriendo la mínima distancia por carretera.


Ah, que no me fijé; ya veo, es un grafo dirigido y además con todas las distancias iguales (bueno, no todas, pero con dos distancias distintas nada más) perdón.

Saludos y feliz año.
En línea

martiniano
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 627


Ver Perfil
« Respuesta #9 : 10/01/2019, 05:45:30 am »

Hola.


Vale, ya lo he entendido. La clave estaba en lo del problema de flujo a coste mínimo y en la programación lineal. Claro, claro... Estaba yo empepinado en modificar el algoritmo de Dijkstra, que en realidad resuelve un caso particular del anterior.

De todas maneras, si no se me ha escapado nada, en el apartado b) del archivo al que va el enlace anterior se les ha olvidado añadir al grafo [texx]G'[/texx] la arista [texx](1,6')[/texx] con un costo igual a [texx]t(1,6)[/texx], ¿me equivoco?

Saludos.
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 43.466


Ver Perfil
« Respuesta #10 : 10/01/2019, 06:47:46 am »

Hola

De todas maneras, si no se me ha escapado nada, en el apartado b) del archivo al que va el enlace anterior se les ha olvidado añadir al grafo [texx]G'[/texx] la arista [texx](1,6')[/texx] con un costo igual a [texx]t(1,6)[/texx], ¿me equivoco?

Si, estoy de acuerdo.

Saludos.
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!