Semplice percorso più lungo

Question

Quindi, ho capito il problema di trovare il percorso semplice lungo in un grafico è NP-difficile, dal momento che si potrebbe quindi facilmente risolvere il problema del circuito hamiltoniano impostando pesi bordo a 1 e vedere se la lunghezza del percorso semplice lungo uguale il numero di spigoli.

La mia domanda è: che tipo di percorso vorresti ottenere se hai preso un grafico, trovato il peso massimo bordo, m, sostituita ogni bordo peso w con m - w, e corse un algoritmo di percorso più breve serie su questo? Non è chiaramente il percorso più lungo semplice, dal momento che se così fosse, allora NP = P, e penso che la prova per una cosa del genere sarebbe stato un po 'più complicato = P.

Answer 1

alt text http://dl.getdropbox.com/u/317805/path2 .jpg

Il grafico sopra si trasforma in seguito utilizzando l'algoritmo.

Il percorso più lungo è la linea rossa nella graph.And sopra a seconda di come i legami sono rotti e l'algoritmo si utilizza, il percorso più breve nel grafico trasformato potrebbe essere la linea blu o la linea rossa. Così trasformando pesi bordo grafico utilizzando la costante che lei ha citato i rendimenti senza risultati significativi. Questo è il motivo per cui non è possibile trovare il percorso più lungo utilizzando gli algoritmi di cammino minimo non importa quanto sei intelligente. Una trasformazione più semplice potrebbe essere quella di negare tutti i pesi di bordo ed eseguire l'algoritmo. Non so se ho risposto alla tua domanda, ma per quanto riguarda la proprietà percorso passa per la squadra di grafico trasformato avere tutte le informazioni utili per quanto riguarda la distanza.

Tuttavia questa particolare trasformazione è utile in altri settori. Per esempio si potrebbe forzare l'algoritmo per selezionare un peso particolare vantaggio in corrispondenza bipatrite se si dispone di più di un vincolo con l'aggiunta di un enorme costante.

• Modifica: Mi è stato detto di aggiungere questa affermazione: Il grafico di cui sopra non è solo la distanza fisica. Essi non devono tenere la disuguaglianza triangolare. Grazie.

Answer 2

Se si potesse risolvere i problemi più breve percorso con pesi negativi si dovrebbe trovare un percorso più lungo, i due sono equivalenti, questo potrebbe essere fatto mettendo un peso di -w invece di w

L'algoritmo standard per i pesi negativi è la Bellman-Ford algoritmo. Tuttavia l'algoritmo non funziona se c'è un ciclo nel grafo tale che la somma dei bordi è negativo. Nel grafico che si crea, tutti questi cicli hanno pesi somma negativa e così l'algoritmo non funzionerà. A meno che, naturalmente, non si hanno cicli, nel qual caso si dispone di un albero (o una foresta) e il problema è risolvibile tramite la programmazione dinamica.

Se sostituiamo un peso di w da m-w, che garantisce che tutti i pesi saranno positivi, allora il percorso più breve possono essere trovati tramite algoritmi standard. Se il più breve percorso P in questo grafico è k bordi allora la lunghezza è k * m-w (P) dove w (P) è la lunghezza del percorso con i pesi originali. Questo percorso non è necessariamente il più lungo, tuttavia, di tutti i percorsi con bordi k, P è la più lunga.