Ciclo peso medio minimo - Spiegazione intuitiva

Question

In un grafico orientato, stiamo cercando il ciclo con i pesi di bordo medi più bassi. Ad esempio, un grafico con i nodi 1 e 2 con percorso da 1 a 2 di lunghezza 2 e da 2 a 1 di lunghezza 4 avrebbe un ciclo medio minimo di 3.

Non cercando un metodo complicato (Karp), ma un semplice backtracking con una soluzione di potatura. Viene fornita una spiegazione come "Risolvibile con backtracking con potatura importante quando la media corrente è maggiore del costo del ciclo di peso medio trovato migliore."

Tuttavia, perché questo metodo funziona? Se siamo a metà del ciclo e il peso è più della media trovata, non è possibile che con piccoli bordi di peso possiamo raggiungere una situazione in cui il nostro ciclo attuale può scendere al di sotto della media migliore trovata?

Edit: Ecco un problema di esempio: http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2031

Answer 1

Consente soluzione ottimale per grafo essere un ciclo con bordo medio peso X.

C'è qualche ciclo ottimale con bordi e_1, e_2 ... e_n , tale che avg(e_i) = X.

Per la mia dimostrazione, presumo tutti gli indici modulo n, quindi è .

Diciamo che la nostra euristica non riesce a trovare questa soluzione, che significa: per ogni i (qualunque bordo abbiamo preso prima) esiste come j (abbiamo seguito tutti i bordi i-j finora) che il peso medio vantaggio nel sequenza e_i ... e_j è maggiore di X (euristica prugna questa soluzione).

Quindi è possibile mostrare che il peso del bordo medio non può essere uguale a X. Consente una sottosequenza di contiguos più lunga che non viene sfoltita da euristica (con un peso del bordo medio non superiore a X per ogni elemento). Almeno uno e_i <= X, quindi esiste una tale sottosequenza. Per il primo elemento e_k di tale sottosequenza, vi è p tale che avg(e_k ... e_p) > X. Prendiamo prima tale p. Ora lascia prendere k' = p + 1 e ottenere un altro p'. Ripeteremo questo processo fino a quando non avremo colpito di nuovo il nostro k iniziale. L'p finale potrebbe non superare l'iniziale k, ciò significa che la sottosequenza finale contiene [e_k, e_p - 1] iniziale, che contraddice la nostra costruzione per e_k. Ora la nostra sequenza e_1 ... e_n è completamente coperta da sottosequenze non sovrapposte e_k ... e_p, e_k'...e_p' ecc., Ognuna di queste ha un peso di bordo medio maggiore di X. Quindi abbiamo una contraddizione che è avg(e_i) = X.

Per quanto riguarda la tua domanda:

Se siamo a metà di un ciclo e il peso è superiore al miglior trovato media, non è possibile che con bordi peso piccoli siamo in grado di raggiungere una situazione dove il nostro ciclo attuale può andare al di sotto del miglior valore di trovato?

Ovviamente lo è. Ma possiamo sfoltire questa soluzione in sicurezza, poiché in seguito scopriremo lo stesso ciclo a partire da un altro bordo, che non verrà potato. La mia dimostrazione afferma che se consideriamo ogni possibile ciclo nel grafico, prima o poi troveremo un ciclo ottimale.