Un vendedor viajero debe visitar 5 ciudades para vender en ellas. Está al comienzo en una de las ciudades a visitar. La red muestra las tarifas más baratas disponibles entre cada par posible de ciudades, en ambas direcciones:
En la figura cada ciudad es un nodo signado con las letras: W (punto de partida), P, C, S y A.
Necesitamos encontrar una ruta que comience en "W" y que pase exactamente una vez por cada uno de los nodos y vuelva a "W". Cualquier ruta que pase por cada nodo exactamente una vez y termine en el punto de partida se le conoce como "Circuito Hamiltoniano".
Existe un método conocido como "Método de la Fuerza Bruta" que consiste en evaluar cada uno de los Circuitosa Hamiltonianos posibles y para encontrar por comparación el que sea más barato.
Por ejemplo Ud. puede comparar: WPCSAW y WPCASW y ver que el segundo:
WPCASW: 74 + 98 + 104 + 149 + 105 = 530 es más caro que el primero ....
Solución Técnica es conocida como el "Algoritmo del Vecino más cercano"
1) Escoja un nodo como punto de partida.
2) Desde ese nodo de partida recorra hasta el nodo que tiene la tarifa más barata. Llamaremos a este nodo el vecino más cercano. Si existe otro con igual tarifa escoja uno de los dos en forma arbitraria.
3) Repita el proceso con un nodo a la vez, viajando a los nodos que aun no han sido visitados. Continúe con este procedimiento hasta que todos los nodos han sido visitados.
4) Complete un Circuito Hamiltoniano regresando al punto de partida.
5) Calcule el costo del circuito.
muy claro y didáctica la explicación gracias.
ResponderEliminar