Commesso viaggiatore con Algoritmo Held e Karp

Question

Sono ben consapevole della soluzione DP per il problema del commesso viaggiatore; noto anche come algoritmo Held e Karp per TSP.

ho implementato con maschera di bit, ed è qualcosa di simile:

int TSP(int pos, int bitmask) { 
    if (bitmask == (1<<(K+1))-1) 
     return dist[pos][0];    // Completing the round trip 

    if (memo[pos][bitmask] != -1) 
     return memo[pos][bitmask]; 

    int answer = INF; 
    for (int i = 0; i <= K; i++) { 
     if (i != pos && (bitmask & (1 << i)) == 0) 
      answer = Math.min(answer, dist[pos][i] + TSP(i, bitmask | (1 << i))); 
    } 

    return memo[pos][bitmask] = answer;  // Storing the best dist for the set of traveled cities and untraveled ones. 

}

Questo algoritmo è abbastanza veloce; il calcolo di 15 città è abbastanza veloce. Tuttavia, noto che potrebbe essere ulteriormente migliorato per ospitare circa 20 città.

1) Se la matrice dist è simmetrica, forse possiamo fare uso di questa proprietà per evitare calcoli ripetuti. (ad esempio a-> b-> c-> d-> a == a-> d-> c-> b-> a)

2) Utilizzare entrambi i limiti superiore e inferiore per potare. L'algoritmo di cui sopra è in grado di ottenere la sua prima soluzione ottimale possibile in un tempo molto breve, potrebbe essere in grado di usarlo.

Ho provato a migliorare l'algoritmo in base ai due principi sopra menzionati. Tuttavia, non ho un algoritmo migliore.

Sto tentando inutilmente di migliorare qualcosa di impossibile? Cosa ne pensi?

Answer 1

Penso che tu abbia ragione. Sotto il tuo metodo, il numero massimo di città può essere 20,21 o 22, ma non può essere nemmeno 25. Questo perché il numero di stato nell'algoritmo è n * (2^n), quando n = 20, è circa 10^7, quando n = 25, è circa 10^9, che è un numero molto grande. Con i computer moderni, può elaborare circa 10^7 calcoli in 1 secondo. Ma ci vorranno circa 100 secondi per elaborare il calcolo 10^9.

Quindi penso che se si desidera gestire più città, alcuni algoritmi di approssimazione possono essere utili, come algoritmo di annealing simulato, algoritmo genetico, ecc. Oppure è possibile utilizzare più macchine e ridimensionare il problema.