Problema del commesso viaggiatore - distanze negativi consentite

Question

Sono interessato nella seguente versione di TSP:

Assunzione: TSP dove le distanze sono non negativo. Sappiamo che l'algoritmo A che calcola la soluzione opzionale per questi casi di TSP.
Compito: Stato un algoritmo che utilizza l'algoritmo A e calcola un solition ottimale per i casi in cui non sono permessi distanze negative.

Answer 1

Suggerimento: Ogni TSP tour ha lo stesso numero di spigoli. Utilizzare questa opzione per modificare i pesi nel grafico in un modo che colpisce tutti i tour TSP nello stesso modo.