Ciclo di peso massimo in un grafico

Question

Dato un grafo pesato (orientato o non orientato) Ho bisogno di trovare il ciclo del grafico con il peso massimo.

Il peso di un ciclo essendo la somma del peso dei bordi del grafico.

Può essere qualsiasi ciclo, non solo il ciclo di base per i quali siamo in grado di

• trova tutto il ciclo di base (vedi Algoritmi identificare tutte le basi del ciclo in un grafico non orientato )
• calcolare il peso di ciascun ciclo di base e trovare il massimo

I può tentare di enumerare tutti i cicli del grafico e quindi calcolare il massimo ma il numero totale di cicli possono essere molto grandi (se il grafico è completo allora qualsiasi sequenza di vertici in cui il primo e ultimo sono identici è un ciclo ).

Avete qualche idea per trovare quel ciclo di peso massimo senza enumerare tutti i cicli?

Se avete bisogno di ipotesi sul grafico (positivi pesi, per esempio) si prega di indica.

Answer 1

Questa è NP-hard.

problema Hamiltonian ciclo può essere ridotto a questo.

Dato un grafo che dobbiamo controllare se esiste un ciclo hamiltoniano o meno, in peso assegnare a ciascun bordo 1.

Ora eseguire l'algoritmo per ottenere il ciclo di peso massimo. Se il peso è

Answer 2

Se si riesce a trovare il percorso ponderata minima nel vostro caso specifico, basta invertire i segni di tutti i pesi e applicare l'algoritmo. Naturalmente si stanno facendo alcune ipotesi non dichiarate, perché l'argomento di Moron è corretta (no pun intended). Le ipotesi che si stanno facendo potrebbe essere pesi positivi o nessun cicli peso negativo. Penso che si dovrebbe fare uno sforzo per affermare loro, invece di lasciare che la gente cerca nello spazio infinito di possibili ipotesi. Come ai risultati della durezza, è anche difficile da approssimare in un numero di modo, controlla questo documento . Lo stesso documento contiene diversi risultati positivi per importanti tipi di grafici, ma è preoccupato con lunghi percorsi non ponderati così la mia ipotesi è che la maggior parte degli algoritmi nella carta non sarà direttamente aiuto nel tuo caso. Se si cerca "cicli pesanti" troverete una serie di documenti interessanti, ma sono più di carattere matematico. Se i pesi sono interi piccoli (fino a un polinomio nella dimensione del grafico), si può provare e sostituire ogni bordo con un percorso non ponderata per ridurre il problema al caso non ponderata. Spero che questo aiuta in una certa misura, ma si potrebbe avere un problema di ricerca aperto sulle vostre mani.