OIA-Wiki

El enunciado típico dice: Dadas $n$ ciudades conectadas por $m$ caminos, cada uno con una cierta longitud, dar un camino que empiece en una ciudad inicial $s$, pase por todas las ciudades exactamente una vez, y vuelva a la ciudad inicial.

Este es un problema de mucho interés, básicamente porque en muchas situaciones de la vida real puede ser útil calcular la respuesta al enunciado. Por ejemplo, si una banda quisiera realizar un tour, sabe en qué ciudades quiere tocar (por la cantidad de fans que viven ahí), y saben cuánto salen los pasajes en avión de cada lugar a cada lugar (o la suma de las combinaciones de aviones si fuera necesario), y quieren decidir en qué orden recorrer las ciudades (por supuesto que tienen que volver a sus casas).

Hay muuuchas variantes de este problema, cada una con su particular interés: si ir de $A$ a $B$ no cuesta lo mismo que de $B$ a $A$; si no hay que volver a la ciudad inicial.

También hay muchas ideas probabilísticas, que andan en una gran cantidad de casos aunque no en todos, pero que tardan mucho menos en dar la respuesta. Pueden leer más sobre este problema en wikipedia.

Acá se transcribe la solución, pero recomendamos fuertemente pensar el problema antes de seguir leyendo. Para pensar en la solución, piensen que el límite es $n \leq 17$.

...

...

Primero, como comentario, veamos que hay $(n-1)!$ caminos posibles, ya que al principio podemos ir a cualquiera de las otra $n-1$ ciudades, desde allí a la restantes $n-2$, ectétera. Por lo que la complejidad del algoritmo más “bruto” posible, que mire todos los caminos, será $O(n*(n-1)!) = O(n!)$, ya que para implementarlo tenemos que guardar qué ciudades ya visitamos. Si bien la complejidad de nuestra solución, que será $O(2^n*n^2)$, parece grande, cuando $n=11$, $O(n!) = O(4*10^7)$, que es lo mismo que nuestra solución para $n=17$. Y la solución en tiempo $n!$ necesitaría aproximadamente $1$ año para resolver el problema, contra $1$ segundo de nuestra solución.

Ahora sí.

La solución a este problema usa programacion dinamica en subconjuntos.

El estado que guardaremos para los subproblemas de la dinámica será para un subconjunto de ciudades $S$, y una ciudad $c$, cuál es el camino más corto que empieza en $s$, recorre todas las ciudades de $S$ y termina en $c$.

¿Cómo calculamos un estado?

Para saber el mejor camino pasando por todas las ciudades de $S$ y terminando en $c$, lo que podemos hacer es mirar cuál nos conviene que sea la anteúltima, lo que nos deja con un subproblema donde el subconjunto de ciudades será $S - {c}$, es decir, queremos un camino que pase por todas las ciudades excepto por $c$, y después unirlo con $c$.

Entonces:

$mejorCamino(S, c) = min_{a\ en\ S-c}\{mejorCamino(S-c, a) + dist(a,c)\}$, donde $dist(a,c)$ es la longitud de la arista que une a $a$ con $c$.

Acá ya podemos ver que la complejidad es $\large O(2^n*n^2)$, ya que tenemos $2^n*n$ estados, y para calcular el valor de cada uno tenemos que hacer $O(n)$ pasos (los valores que usamos adentro ya fueron calculadas previamente).

Adónde tenemos guardada la respuesta?

Esto es algo que también pueden detenerse a pensar, que los va a ayudar a entender y a entender si entendieron.

...

...

Como queremos pasar por todas las ciudades, obviamente vamos a necesitar los subproblemas donde el subconjunto de las ciudades es el conjunto completo, con todas las ciudades. Pero adónde vamos a querer terminar?

Bueno, en la que nos de la mejor respuesta. Lo que vamos a hacer es buscar en qué ciudad $a$ nos conviene terminar, tal que la suma $mejorCamino(C, a) + dist(a,s)$ sea la menor.

Si todavía no leyeron el link que dejé arriba de programación dinámica en subconjuntos, léanlo ahora. Ahí se ve cómo formar los subconjuntos, cómo saber si una ciudad está en un subconjunto, cómo escribir subconjuntos con un solo elemento y todo lo necesario para entender el código y la breve explicación de acá abajo.

Veamos que para un estado, siempre vamos a necesitar muchos estados donde el subconjunto tiene una ciudad menos que el estado actual. Entonces, si calculamos las respuestas recorriendo en orden según la cantidad de elementos del subconjunto, vamos a poder obtener bien todas las respuestas. En vez de recorrerlos ordenados por tamanio, podemos simplemente recorrer desde el número $1$ en adelante, que si lo vemos como subconjuntos estamos mirando: $00\ldots.001$, $00\ldots.010$, $00\ldots.011$, $00\ldots.101$, $00\ldots.110$, $00\ldots.111$. ...

Entonces cuando vemos un subconjunto, todos los subconjuntos de ese subconjunto ya los habremos visto, ya que sabemos que un subconjunto de un conjunto se representa como el conjunto inicial menos la suma de $2$ elevado a la posición de cada elemento que sacamos, por lo que en esta representación el subconjunto será menor, y si vamos en orden como dijimos, garantizamos haber visto a todos los subconjuntos del subconjunto.

También, hay que tener el cuidado de que todos los subconjuntos que nos interesan deben incluir a nuestra ciudad $s$. Y además, cuando tengamos $2$ ciudades, vamos a querer como anteúltima ciudad a $a$; pero si estamos en un subconjunto con más de $2$ ciudades, no tiene sentido decir que la ciudad $s$ está como anteúltima porque debe estar primera. Esto lo podemos manejar o en un $if$, ver que la anteúltima no sea $s$ o sea $s$ y el subconjunto tenga $2$ ciudades, o podemos definir al principio los valores de la dinámica cuando el subconjunto tiene $2$ ciudades, que será simplemente la distancia entre $s$ y cada ciudad, y luego prohibir que la anteúltima sea $s$.

TSP.cpp

#include<bits/stdc++.h>
 
using namespace std;
 
#define forn(i,n) for(int i=0; i<(int)(n); i++)
#define forsn(i,s,n) for(int i=(int)(s); i<(int)(n); i++)
 
int main(){
    int n, m;
    cin>>n>>m;
    const int INF = 2e9;
    vector< vector<int> > matriz(n, vector<int>(n, INF));
    forn(i, m){ // Ingresamos aristas
        int u, v, d;
        cin>>u>>v>>d;
        matriz[u][v]=d;
        matriz[v][u]=d;
    }
    int s=0; // seteamos la ciudad desde la cual queremos empezar
    vector< vector<int> > mejorCamino((1<<n), vector<int>(n, INF));
    mejorCamino[(1<<s)][s]=0;
    forn(i, n){
        if(i!=s){
            mejorCamino[(1<<s)+(1<<i)][i]=matriz[s][i];
        }
    }
    forsn(i, 1, (1<<n)){ // no tiene sentido ver el conjunto vacio
        int subcon=i|(1<<s); // Si o si tengo que incluir a s
        forn(c, n){ // quiero terminar en c
            if( c!=s && (subcon & (1<<c)) ){ // tiene sentido terminar ahi solo si esta en subcon
                int best = INF;
                forn(a, n){ // pruebo que la ciudad a sea la anteultima
                    if( a!=c && (subcon & (1<<a)) ){
                        best=min(best, mejorCamino[subcon-(1<<c)][a] + matriz[a][c]);
                    }
                }
                mejorCamino[subcon][c]=best;
            }
        }
    }
    int ans=INF;
    int ultima;
    forn(i, n){
        if(i!=s){
            int terminandoAca = mejorCamino[(1<<n)-1][i] + matriz[i][s];
            if(ans>terminandoAca){
                ans=terminandoAca;
                ultima=i;
            }
        }
    }
    cout<<"El camino más corto mide "<<ans<<" y termina en la ciudad "<<ultima<<endl;
}

Pensar cómo se podría reconstruir el camino. Intenten usar estrategias similares a las de Dijkstra por ejemplo para la reconstrucción del camino.