Podróżujący sprzedawca z algorytmem wstrzymującym i karpowym

Question

Dobrze zdaję sobie sprawę z rozwiązania DP dla problemu komiwojażera; znany również jako algorytm wstrzymany i Karp dla TSP.

I wprowadziły go maskę bitową, i to jest coś takiego:

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. 

}

Algorytm ten jest bardzo szybki; obliczenie 15 miast jest stosunkowo szybkie. Zauważam jednak, że można go jeszcze poprawić, aby pomieścić około 20 miast.

1) Jeśli macierz dystansowa jest symetryczna, być może będziemy mogli wykorzystać tę właściwość, aby zapobiec powtarzającym się obliczeniom. (np. a-> b-> c-> d-> a == a-> d-> c-> b-> a)

2) Używanie górnej i dolnej granicy do przycinania. Powyższy algorytm jest w stanie uzyskać pierwsze możliwe optymalne rozwiązanie w bardzo krótkim czasie, może być w stanie go użyć.

Próbowałem poprawić algorytm w oparciu o wyżej wymienione dwie zasady. Jednak nie mam lepszego algorytmu.

Czy podejmuję daremne próby udoskonalenia czegoś niemożliwego? Co myślisz?

Answer 1

Myślę, że masz rację. Zgodnie z twoją metodą maksymalna liczba miast może wynosić 20, 21 lub 22, ale nie może być nawet 25. Jest tak dlatego, że liczba statusu w twoim algorytmie wynosi n * (2^n), gdy n = 20, to około 10^7, gdy n = 25, to około 10^9, co jest bardzo dużą liczbą. W przypadku nowoczesnych komputerów może on przetwarzać około 10^7 obliczeń w ciągu 1 sekundy. Ale przetwarzanie 10^9 zajmie około 100 sekund.

Myślę więc, że jeśli chce się obsłużyć więcej miast, przydatne mogą być pewne algorytmy aproksymacyjne, takie jak algorytm symulowanego wyżarzania, algorytm genetyczny itp. Można też użyć wielu maszyn i zmniejszyć problem.