5
Inspirado por este cómic http://xkcd.com/173/Algoritmo para encontrar una 'ruta de expansión mínima'?
Sé que hay muchos algoritmos para encontrar el árbol de expansión mínimo de un grafo ponderado, sin embargo he estado luchando para encontrar cualquiera que pueda encontrar la expansión mínima 'camino'.
Para el cómic, si ponderamos cada borde en función de la relación de cada pareja, entonces la disposición socialmente óptima sería la "trayectoria" mínima de expansión, es decir, una ruta que abarque todos los vértices. ¿Alguien puede ayudar?
¿Es esto diferente de encontrar un mínimo [camino de Hamilton] (http://en.wikipedia.org/wiki/Hamiltonian_path)? –
La observación correcta, por supuesto. Otro caso interesante donde los problemas relacionados difieren en complejidad: MST = fácil, MSP/HP = difícil. –
Si puede hacer algunas suposiciones sobre las restricciones sociales, es posible que pueda resolver esto con un algoritmo huffman modificado. –