• Viernes 29 de Marzo de 2024, 14:26

Autor Tema:  Creando un algortimo con grafos.  (Leído 1812 veces)

arcus93

  • Nuevo Miembro
  • *
  • Mensajes: 1
    • Ver Perfil
Creando un algortimo con grafos.
« en: Jueves 24 de Marzo de 2011, 05:13 »
0
Buenas, como va gente ? Soy nuevo en el foro y queria saber si me podian ayudar a inventar un algortimo.

El codigo en cuestion tendria que hacer lo siguiente: dado un punto P cualquiera, y un conjunto de nodos o puntos N, el algoritmo debe hallar el camino mas corto o de menor costo, tomando como punto de inicio a P, que pase por todos los puntos del conjunto N.
Estuve probando diferentes cosas, pero todavia no llegue a mucho. Lei los algoritmos de Dijkstra (camino mas corto entre dos puntos), Prim / Kruskal (arboles de expansion minima), pero ninguno es lo que necesito.

Estoy programando en C# pero cualquier ayuda me viene bien :D . Esto es lo que tengo hasta ahora:

public Point[] EncontrarCamino(List<Point> PuntosAVisitar, Point PuntoDeInicio)
{
       int cantNodos = PuntosAVisitar.Count;
       Point[] ret = new Point[cantNodos];
       int[,] TablaCostos = new int[cantNodos, cantNodos];

       for (int i = 0; i < cantNodos; i++)
{
            for (int j = 0; j < cantNodos; j++)
             {
                 if (i == j)
                  {
                      TablaCostos[i, j] = 0;
                  }
                  else
                  {
                      TablaCostos[i, j] = ObtenerCosto(i, j);
                  }
             }
         }
}

Ese cacho de codigo genera una matriz con la tabla de costos desde un punto a otro.

Desde ya muchas gracias !

pucheto

  • Nuevo Miembro
  • *
  • Mensajes: 1
    • Ver Perfil
Re: Creando un algortimo con grafos.
« Respuesta #1 en: Jueves 31 de Marzo de 2011, 14:49 »
0
Me parece q ese problema es el "hamiltonian trail" o "camino hamiltoniano" y es np-completo...