Percorso non ciclico a tutti i nodi

Question

Esiste un algoritmo o un insieme di algoritmi che consentono di trovare la distanza di cammino più breve da un nodo di avvio arbitrario in modo che ogni nodo venga visitato in un peso, un grafico non orientato? Non è un commesso viaggiatore, perché non mi interessa se un nodo viene visitato più di una volta. (Non importa nemmeno se si ritorna all'inizio - il walker può finire in un nodo lontano purché fosse l'ultimo necessario per visitare tutti i nodi.) Non è un albero spanning minimo, perché potrebbe essere che andare A -> B -> C -> A -> D è un percorso (non univoco) più breve per visitare A, B, C e D. La mia intuizione dice che questo non è È un bel problema di NP, perché non ha le restrizioni che rendono i problemi di NP così complicati. Potrei, naturalmente, essere completamente sbagliato.

Answer 1

Dall'articolo di Wikipedia su Travelling Salesman Problem:

rimozione della condizione di visitare ogni città "solo una volta" non rimuovere la NP-difficile, dal momento che è facilmente visibile che nel caso planare c'è un tour ottimale che visita ogni città una sola volta (altrimenti, per la disuguaglianza del triangolo, una scorciatoia che salta una visita ripetuta non aumenterebbe la durata del tour).

Answer 2

Non so quale sia l'etichetta per aggiungere una risposta a una domanda con una risposta già accettata.

Aggiungo questa risposta solo per non dover saltare a un'altra pagina, per non avere a che fare con grafici planari e disuguaglianze triangolari e il fatto che sia semplice e probabilmente più facile da capire.

Hamiltoniana problema Path può essere ridotta a questo:

Supponiamo di avere un algoritmo di tempo polinomiale per risolvere il nostro problema di trovare un minimo di passeggiata di peso che visita tutti i vertici.

Dato un grafico di cui abbiamo bisogno di decidere se esiste o meno un percorso hamiltoniano, lo alimentiamo così com'è, all'algoritmo del problema, impostando i pesi del bordo = 1. Se l'algoritmo restituisce un valore> n- 1, quindi non vi è alcun percorso hamiltoniano nel grafico originale, altrimenti non esiste.

Quindi questo problema è NP-Hard.