El problema que indicas se parece mucho a un problema tipo "camino de coste mínimo" que se resuelve con un algoritmo bien conocido: el algoritmo de Dijkstra. También hay otro algoritmo que podría tener cierta similitud: el algoritmo de Prim (o alternativamente el de Kruskal) para determinar árboles de recubrimiento mínimo en grafos.
Aquí tienes una imagen que explica cómo se resuelve el algoritmo de Dijkstra. Puedes considerar que el punto 1 es el punto donde se encuentra el taxi, mientras que los puntos 2, 3, 4, 5 y 6 son los puntos de destino de los viajeros, es decir, los puntos a los que debe llegar el taxista recorriendo la mínima distancia posible. En realidad el algoritmo no está planteado para visitar todos los nodos, sino para ir de un nodo a otro con el coste mínimo (en la imagen el objetivo es ir del nodo 1 al 5 con coste mínimo). Esto podría modificarse para una vez alcanzado el nodo de destino, fijar como nuevo destino un nodo no visitado... y así hasta visitarlos todos.
(http://upload.wikimedia.org/wikipedia/commons/thumb/5/57/Dijkstra_Animation.gif/270px-Dijkstra_Animation.gif)
Si te fijas en la imagen verás la lógica del algoritmo. Los nodos se dividen en dos grupos: por una lado los que ya están en el recorrido (seleccionados) y por otro lado los que todavía no están en el recorrido. Inicialmente el único nodo en el recorrido es el nodo 1. Desde el punto 1 se evalúan los nodos adyacentes que no estén en el recorrido y se elige aquel que se encuentra a una menor distancia. Ese nodo pasa a ser el nodo actual y ya forma parte del conjunto de nodos del recorrido. Seguidamente se repite el proceso, siempre hay que tener en cuenta qué nodos están en el recorrido y cuáles no ya que no puedes volver a tomar un nodo que ya esté en el recorrido.
El algoritmo de Prim (o el de Kruskal) lo que te dice es dado un conjunto de nodos, cuál es el conjunto de aristas o conexiones entre nodos que suman el coste mínimo. En esta imagen se ve:
(http://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Minimum_spanning_tree.svg/220px-Minimum_spanning_tree.svg.png)
De todas formas antes de plantear el algoritmo pienso que debe estar claro cuáles son los datos del problema. Tal y como yo lo veo los datos sería las distancias entre los puntos que se ven en la imagen que pongo como archivo adjunto (mira ese archivo), es decir, tendrías 10 datos de distancias. Con esos 10 datos de distancias, tendrías que definir cuáles son los movimientos que debería hacer el taxista para recorrer la menor distancia posible.
Si se confirma que estos son los datos, a partir de ahí puedes empezar a pensar en el algoritmo para solucionarlo.
En el pseudocódigo que has planteado queda definida la matriz de adyacencia del grafo que representa el problema con la mitad de los datos, ya que la otra mitad es igual y por tanto no hace falta introducirla. Por ejemplo para este grafo:
(http://upload.wikimedia.org/wikipedia/commons/thumb/3/30/Weighted_K4.svg/220px-Weighted_K4.svg.png)
Voy a ir planteando el problema con la solución que conozco, que es basada en grafos y ramificación y poda, esto es una solución compleja, se supone que se deben tener conocimientos previos.
Por si te sirvieran, aquí algunas referencias de wikipedia:
Sobre el problema en sí: http://es.wikipedia.org/wiki/Problema_del_viajante
Sobre la estrategia algorítmica: http://es.wikipedia.org/wiki/Ramificaci%C3%B3n_y_poda
Con la solución que conozco, partiríamos de la matriz de adyacencia completa, aunque tenga los datos repetidos (se supone que de la introducción de datos se ha encargado un programa o función previa)
El pseudocódigo de carga de datos quedaría así:
Función CARGA_DATOS () : matriz [1..n, 1..n] de enteros
Var grafo: matriz [1..n, 1..n] de enteros
Var i, j: entero;
Inicio
Para i ← 1 hasta 6 hacer
Para j ← 1 hasta 6 hacer
Leer (A[i,j])
Fin_para;
Fin_para;
Devolver grafo
Fin_función.
Para el grafo de la imagen anterior (suponiendo que la letra A es 1, la letra B 2, la letra C 3, la letra 4 D) la matriz quedaría así:
(0 20 42 35
20 0 30 34
42 30 0 12
35 34 12 0)
De forma que grafo[1,1] representa la distancia del punto 1 al punto 1, que es cero. grafo [1,2] representa la distancia del punto 1 al punto 2 que es 20, grafo[1,3] representa la distancia del punto 1 al punto 3 que es 42 y así sucesivamente.
El valor -1 significa que entre dos nodos del grafo no hay camino. Por ejemplo en este grafo:
(http://upload.wikimedia.org/wikipedia/commons/thumb/5/57/Dijkstra_Animation.gif/270px-Dijkstra_Animation.gif)
tendríamos que grafo[1,4] = -1
¿Por qué coger el valor -1? Pues no hay un motivo concreto, también podríamos coger 0 ó coger -22 ó -99, simplemente es un valor que permita distinguir.
Para empezar a plantear el problema harían falta estructuras de datos auxiliares que permitan plantear el algoritmo. En esta solución usaríamos:
tipo Tnodo = registro
ruta = Tvector //Sirve para almacenar la solución parcial
asignados: TvectorB //vector de booleanos que indica los nodos del grafo que ya están incluidos en un camino que se está probando
k: entero //índice de número de elemento fijado en la ruta para este nodo
costeT: entero //Coste acumulado
estOpt: entero //Estimación optimista de mejor coste que se puede obtener a partir de la ruta
finRegistro
Supuesto el grafo que tiene 6 nodos anterior y que la ruta que estamos probando es 1, 2, 4. Los elementos del tipo registro serían:
ruta = [1, 2, 4, - , -, -]
asignados = [1, 1, 0, 0, 0, 1]
k: 3
costeT: 7+15 = 22
estOpt: un valor seguro se obtiene multiplicando el número de aristas que faltan por el peso mínimo de una arista en el grafo. Para cerrar un ciclo hacen falta tantas aristas como vértices, en este caso 6. Tenemos definidias 2 aristas (de 1 a 2 y de 2 a 4).
Nos faltan 4 aristas para completar el recorrido, así que viendo cuál es la arista de peso mínimo en el grafo la estimación optimista sería 4*2 = 8
Nos hace falta una función para calcular la arista de peso mínimo en el grafo. Intenta plantearla, no sé si me estoy enrollando mucho.