Trovare il costo ottimale di una soluzione commesso viaggiatore

Question

Sto lavorando a questo problema:

TSP:
Input: A matrix of distances; a budget b
Output: A tour which passes through all the cities and has length <= b, 
if such a tour exists.

TSP-OPT
Input: A matrix of distances
Output: The shortest tour which passes through all the cities.

Mostra che, se TSP può essere risolto in tempo polinomiale, allora così può TSP-OPT.

Ora, la prima cosa che salta in mente è che se sapevo che il costo della soluzione ottimale, ho potuto solo set b per questo e voilà. E, vorrei non lo sai, altrove nel mio libro che contiene un suggerimento per questo problema:

  

Come facciamo a trovare il costo ottimale? Facile:. Dalla ricerca binaria

Penso che potrei essere equivoco qualcosa di molto male qui. La ricerca binaria è destinata a trovare la posizione di un determinato elemento in una lista ordinata. Come funziona esattamente poteva che mi aiutano a trovare il costo ottimale? Sto veramente confuso. Gli autori non elaborare ulteriormente, purtroppo.

L'unica altra cosa che potrei pensare di risolvere questo problema è quello di dimostrare che entrambi riducono a un altro problema che è NP-completo, che io possa finire per fare, ma ancora ... questo mi bug.

Answer 1

Si supponga che avete un po 'più bassa l limite (ad esempio 0) e superiore u tenuti (ad esempio, la somma di tutti i pesi di bordo). In primo luogo, il tentativo di trovare una soluzione di costo totale <= (l + u) / 2. Se ci riesci, prova di nuovo per un valore inferiore: (3L + u) / 4; altrimenti provare per un valore superiore: (l + 3u) / 4

.

Lo definirei un metodo di bisezione (Wikipedia) piuttosto che la ricerca binaria, ma l'idea è la stessa. Vogliamo cercare qualche intervallo per il valore ottimale, quindi iniziamo a metà e salire se siamo troppo basso e verso il basso se siamo troppo alta.