[ Foro de C# ]

Guardar rutas c#

14-Aug-2013 14:38
Miguel Areales Font
4 Respuestas

Ante todo gracias por leer mi pregunta y aviso que quizás pregunto algo obvio, pero soy  muy novato.

El problema que tengo es que quiero hacer rutas (por ejemplo obtenidas aplicando HEURÍSTICA DEL VECINO MÁS PRÓXIMO), y no sé cómo guardar, o que variable crear para tenerlas almacenadas en un programa de consola en C#.

Por ahora tengo los puntos en una "struct", y las distancias entre ellos en una matriz (simétrica).

El caso es que me gustaría poder guardar las rutas que construya aplicando esa heurística teniendo para cada una de ellas, el orden de los puntos y ya guardar información como la distancia, el tiempo etc.
Y no solo eso, sino que fueran agrupando distinto número de puntos. Por ejemplo:
Ruta1: 1,2(pasa por esos puntos), su distancia es 3 y su tiempo 20.
Ruta2: 1,3(pasa por 1 y  3), y su  distancia es 6 y  su tiempo 40.
......
Ruta234: 3,5,8,4,1 (pasa por el punto 3, siguiendo 5,8,4 y acabando en 1), y su distancia es 134 y su tiempo 231.

Había pensado en algo estilo:

struct Ruta
        {
            public Ordren p;
            public float l;
            public float t;            
           

        }

        y luego crear un vector o lo que fuese llamado "Orden" en el cual almaceno el orden de los puntos.

Lo he probado y no me sale, ni el construir las rutas ni el crearme las variables.

Vuelvo a darles las gracias y  espero sus respuestas.


15-Aug-2013 13:04
Nacho Cabanes (+31)

Yo te diría de crear una clase que represente cada nodo de la ruta (con atributos que dependerán de lo que quieras hacer: quizá sus coordenadas, quizá su peso, quizá la lista de elementos adyacentes...)

También otra clase para cada ruta, que tendrá la lista de nodos que la forman y quizá algún dato adicional, como si es solución válida (aunque quizá no óptima) o no lo es (y en ese caso habría que descartarla).

Y luego estará la lógica del "¿cómo buscar rutas?".

Hace pocos meses, escribí un par de artículos sobre algo parecido para mis alumnos, hablando de búsquedas exhaustivas (backtracking) y de algoritmos voraces. Puedes echar un vistazo, por si te dan alguna idea, y preguntar en este mismo foro las dudas que te surjan:

http://nachocabanes.blogspot.com.es/2013/04/busqueda-exhaustiva-acercamiento.html

http://nachocabanes.blogspot.com.es/2013/04/algoritmos-voraces.html


15-Aug-2013 18:20
Miguel Areales Font

Muchas gracias Nacho Cabanes por su respuesta. Lo he hecho haciendo una lista, creo que eso me lo soluciona.

Ahora el siguiente paso de mi problema, es a manera de establecer estas rutas, a ver si alguien me puede ayudar siguiendo este mismo hilo.

Las rutas que pretendo encontrar son todas las que existan obtenidas aplicando la heurística del vecino más próximo. Quiero guardar todos los casos para luego trabajar  con ellos, las rutas no deben repetir puntos.
Por ejemplo si tengo 4 puntos más el inicial que llamo 0:
Las de solo un punto, que siempre las tendré: 0-1-0, 0-2-0, 0-3-0, 0-4-0.
Las de dos puntos, que también las deberé coger todas: 0-1-2-0, 0-1-3-0, 0-1-4-0, 0-2-3-0, 0-2-4-0, 0-3-4-0.
Y a partir de aquí sí que el orden es importante. En las rutas con tres puntos, necesito en cada caso la más corta:
Para mí no es lo mismo en 1,2,3: 0-1-2-3-0, que 0-3-1-2-0 o 0-2-3-1-0. Y de estas solo necesito la más corta según distancias. Lo mismo con los conjuntos 1,2,4; 1,3,4; 2,3,4.
Luego en este ejemplo de 4 puntos, me quedaría hacer la ruta de menos distancia  con 1,2,3,4.

Ahora la parte del programa resumida sería esta:

 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
 
namespace ConsoleApplication1
{
    class Program
    {
        static int ne, nr;
        static int i;
        static float cv;
        static int nposibilidades, ContadorRutas1, ContadorRutas2, nclientesruta, puntoactual;
 
        static double[,] Mdist;
 
 
        struct tipoPunto
        {
 
            public int Y;
            public int Z;
            public float p;
        }
 
        struct InfoRuta
        {
            public List<int> o;
            public float l;
            public float t;
            public float p;
        }
 
 
        private static void Main(string[] args)
        {
 
            //Introducción de datos            
 
            i = 1;
 
 
            Console.WriteLine(" Numero de puntos:");
            ne = Convert.ToInt32(Console.ReadLine());
 
            tipoPunto[] punto = new tipoPunto[ne + 1];
 
            Console.WriteLine(" Velocidad:");
            cv = Convert.ToSingle(Console.ReadLine());
 
 
            //Introducción de los datos del punto de partida.
 
 
            Console.WriteLine(" Y:");
            punto[0].Y = Convert.ToInt32(Console.ReadLine());
 
            Console.WriteLine(" Z:");
            punto[0].Z = Convert.ToInt32(Console.ReadLine());
 
            Console.WriteLine(" p:");
            punto[0].p = Convert.ToSingle(Console.ReadLine());
 
 
 
            //Introducción de datos de los otros puntos.
 
 
            while (i <= ne)
            {
 
                Console.WriteLine(" Entrar nuevo punto");
                Console.WriteLine(" Y:");
                cliente[i].Y = Convert.ToInt32(Console.ReadLine());
 
                Console.WriteLine(" Z:");
                cliente[i].Z = Convert.ToInt32(Console.ReadLine());
 
                Console.WriteLine(" p:");
                cliente[i].cs = Convert.ToSingle(Console.ReadLine());
 
 
 
                i = i + 1;
 
            }
 
            //Calculo de la matriz de distancias.
 
            Mdist = new double[ne + 1, ne + 1];
 
            for (int f = 0; f < Mdist.GetLength(0); f++)
            {
                for (int c = 0; c < Mdist.GetLength(1); c++)
                {
 
                    Mdist[f, c] = Math.Sqrt(Math.Pow(cliente[c].Y - cliente[f].Y, 2) + Math.Pow(cliente[c].Z - cliente[f].Z, 2));
                    Console.WriteLine(Mdist[f, c]);
 
 
                }
            }
 
            //Calculo número de rutas.
            nr = CalculaNumRutas(ne);
 
            //Calculo de rutas.
 
            ContadorRutes1 = 1;
            InfoRuta[] ruta = new InfoRuta[nr];
            nclientsruta = 1;
            ContadorRutes2 = 1;
 
            while (ContadorRutes1 <= nr)
            {
 
                nposibilitats = CalculPosibilitats(ne, nclientsruta);
                ContadorRutes2 = 1;
 
                while (ContadorRutes2 <= nposibilitats)
                {
                    ruta[ContadorRutes1].p = new List<int>();
 
                    for (int j = 0; j < nclientsruta & puntactual <= ne; j++)
                    {
 
ruta[ContadorRutes1] = RutaSeleccionada(nclientsruta, puntactual, ruta[ContadorRutes1]);
 
                        puntactual = puntactual + 1;
 
                    }
 
                    ContadorRutes2 = ContadorRutes2 + 1;
                    ContadorRutes1 = ContadorRutes1 + 1;
 
                }
 
                nclientsruta = nclientsruta + 1;
 
            }
 
        }
 


Y es  RutaSeleccionada(nclientsruta, puntactual, ruta[ContadorRutes1]); donde tenía pensado resolver el tema de las rutas.
Com ya dige, mis conocimientos son muy limitados y posiblemente haya maneras de optimizarlo, pero por eso pido ayuda.

Gracias de nuevo.


15-Aug-2013 22:07
Nacho Cabanes (+31)

Me has hecho caso... pero sólo en parte.

Yo no usaría "struct", sino clases, de modo que cada una pueda tener métodos, además de datos, y así "repartes responsabilidades".

De este modo, cada ruta podría tener un método "Añadir" que incluya en ella un nuevo nodo... pero sólo si no existe en ella todavía (es básicamente comprobar el "Contains" de la lista que almacena todos los nodos que ya tiene).

En cuanto a recorrer todas las posibilidades, generalmente se hace que la lista vaya creciendo con una llamada recursiva. Mira los enlaces que te he puesto en la respuesta anterior, sobre todo los de backtracking.

Veo que lo de del "vecino más próximo" lo haces directamente a partir de la distancia euclídea. Pero insisto, veo "demasiado código" para Main. Deberías repartir trabajo entre varias clases, y la lógica sería más fácil de analizar.


16-Aug-2013 13:22
Miguel Areales Font

Como ya dije soy muy nuevo en esto, empiezo desde cero, y necesito hacerlo, usé struct, porque es lo que he entendido más fácilmente.
La verdad es que no se ni como empezar para hacerlo con una Class.
De todos modos, el método para conseguir las rutas debe ser parecido, no?
Cómo sería lo que usted propone con class y backtracking en el caso que yo pido?






(No se puede continuar esta discusión porque tiene más de dos meses de antigüedad. Si tienes dudas parecidas, abre un nuevo hilo.)