Algoritmo de camino mínimo

[briast]

Hola. Quiero implementar en delphi un algoritmo de camino mínimo pero pasando por una serie de coordenadas.
He estado mirando los típicos algoritmos de caminos mínimos (Dijkstra, etc), pero ninguno es lo que necesito. Se trata de obtener el recorrido de coste mínimo pero pasando obligatoriamente por una serie de nodos.
El grafo contiene una serie de nodos. La distancia entre dos nodos continuos tiene valor 1. Se trata de calcular el recorrido mínimo partiendo de un nodo, llegando a todos los nodos de una lista determinada (que no tienen porque ser todos los nodos del grafo) y acabando en otro nodo determinado. Por un nodo se podría pasar más de una vez si fuera necesario.
Para implementarlo se pueden hacer diferentes opciones, pero ¿alguien sabe que algoritmo podría utilizar que sea el más eficiente?
Gracias.

[nlsgarcia]

briast,


...Quiero implementar en Delphi un algoritmo de camino mínimo pero pasando por una serie de coordenadas...Se trata de obtener el recorrido de coste mínimo pero pasando obligatoriamente por una serie de nodos...Por un nodo se podría pasar más de una vez si fuera necesario...


Revisa estos links:

Problema del camino más corto : http://es.wikipedia.org/wiki/Problema_del_camino_m%C3%A1s_corto

Camino Mínimo : http://www.youtube.com/watch?v=Slug5KVb-yI

Dijkstra's Shortest Path Search algorithm : http://delphiforfun.org/programs/Math_Topics/ShortestPath.htm
Te sugiero revisar los links sugeridos, en ellos encontraras información relevante a tu requerimiento y con dicha base puedes realizar las adaptaciones necesarias a tu problema particular. Otra forma más compleja es por medio de algoritmos genéticos.

Revisa la siguiente información:

Matemáticas Evolutivas: Algoritmos Genéticos (http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3&ved=0CDIQFjAC&url=http%3A%2F%2Fwww.rsme.es%2Fcomis%2Fmujmat%2Fmujer-ciencia%2Fpresentacion%2FPresentacionMTIglesias.pdf&ei=HYzzUs-sKITsyQG01YCACw&usg=AFQjCNFmF-AjLvVX6ygaKSgvX6xOPhza2w&bvm=bv.60799247,d.eW0&cad=rja)

Curso de Algoritmos Genéticos y Optimización Heurística (http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=5&cad=rja&ved=0CD4QFjAE&url=http%3A%2F%2Fwww.herrera.unt.edu.ar%2Fgapia%2FCurso_AG%2FCurso_AG_08_Clase_Ants.pdf&ei=F43zUuvgEKH4yQHjvYFY&usg=AFQjCNEidNZkbe6fIdRxSRAxzJjthc8K8w)

Tesis-ESTUDIO COMPARATIVO DE DIFERENTES TÉCNICAS BIO – INSPIRADAS PARA ENCONTRAR EL CAMINO MÁS CORTO DE UN ROBOT MÓVIL DENTRO DE UN LABERINTO (http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=9&ved=0CFUQFjAI&url=http%3A%2F%2Fwww.cic.ipn.mx%2Fposgrados%2Fimages%2Fsources%2Fcic%2Ftesis%2FB081504.pdf&ei=F43zUuvgEKH4yQHjvYFY&usg=AFQjCNF96Eyv4C1AJ_m-Ib2j4Xgc7DZwhw&cad=rja)
Espero sea útil :)

Nelson.

[briast]

Gracias Nelson.
Como comentaba, no se traba de encontrar el camino mínimo utilizando algoritmos conocidos, como el de Dijkstra.
Lo que pasa es que no daba con el nombre del problema, que seguro que estaba ya resuelto. Pero ya lo he encontrado. Lo que necesitaba es una variante del problema del viajante (TSP), en el que se debe recorrer un conjunto de nodos y obtener el camino óptimo. (http://es.wikipedia.org/wiki/Problema_del_viajante)
El proceso, por tanto, tratará de encontrar el circuito hamiltoniano con suma de etiquetas (distancias) mínima.
Un saludo