SoloCodigo
Programación Específica => Diseño de Algoritmos => Mensaje iniciado por: arcus93 en Jueves 24 de Marzo de 2011, 05:13
-
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 !
-
Me parece q ese problema es el "hamiltonian trail" o "camino hamiltoniano" y es np-completo...