Ho intenzione di provare questo dai primi principi basati sulla mia comprensione dai documenti che ho letto. Attenzione: ho lasciato un falso avvio.
Fase di inizializzazione 1
Ai tuoi 32 nodi di nodi aggiungiamo un nodo sorgente S e un nodo sink T . Quindi miriamo a costruire cose tali che un taglio che partiziona i nodi in insiemi disgiunti, uno contenente S e l'altro contenente T , abbia una capacità pari all'energia della partizione corrispondente.
Quindi iniziamo aggiungendo i bordi da S a ogni segmento p con capacità D_p(1) (questi bordi vengono tagliati se i segmenti sono nella metà di T ) e da ogni segmento% da% a p con capacità T (questi bordi vengono tagliati se i segmenti si trovano nella metà di D_p(0) ).
Fase di inizializzazione 2
Quindi eseguiamo un ciclo attraverso il% non trascurabile di% co_de aggiornando il sottografo generato da S , V_{p,q} , S e p . Aggiungiamo un margine q e un margine T , e aggiorniamo anche le capacità di p->q , q->p , S->p , S->q . Il nostro obiettivo è di rendere questi aggiornamenti in modo tale che ogni taglio abbia un aumento della capacità totale di p->T per i corrispondenti valori di q->T , V_{p,q}(x_p, x_q) . Disegniamo una tabella del bordi tagliati da ciascuno dei quattro casi:
x_p x_q Edges cut
0 0 p->T, q->T
0 1 p->T, S->q, p->q, (q->p)
1 0 S->p, q->T, (p->q), q->p
1 1 S->p, S->q
(I bordi tra parentesi sono i bordi posteriori e quindi non influenzano la capacità del taglio).
I valori dei delta
Quindi se la capacità cambia del nostro aggiornamento è x_p deriviamo le equazioni simultanee
c_pT + c_qT = V_{p,q}(0,0)
c_pT + c_Sq + c_pq = V_{p,q}(0,1)
c_Sp + c_qT + c_qp = V_{p,q}(1,0)
c_Sp + c_Sq = V_{p,q}(1,1)
Questo è sottodeterminato. L'approccio semplice sembra essere quello di impostare x_q ed eliminare efficacemente i bordi tra i vicini. Tuttavia, questo è ovviamente singolare. Il prossimo approccio facile è impostare c_{vertex,vertex} . Quindi otteniamo:
c_Sq = V_{p,q}(1,1)
c_qT = V_{p,q}(0,0)
c_pq = V_{p,q}(0,1) - V_{p,q}(1,1)
c_qp = V_{p,q}(1,0) - V_{p,q}(0,0)
ottimizzazione
Abbiamo finito?
L'obiettivo era quello di ottenere il taglio uguale all'energia. Vogliamo ridurre al minimo l'energia, il che significa trovare un taglio minimo e siamo assolutamente d'accordo, purché tutte le variazioni di capacità sopra riportate siano non negative. Per qualsiasi ragionevole funzione di penalizzazione della transizione possiamo aspettarci che una transizione sia penalizzata più di una non transizione, quindi va bene.
Tuttavia, vi è una piccola ottimizzazione che richiede l'approccio standard. Se assicuriamo che ogni taglio aggiunga lo stesso valore costante c_pq = c_qp = 0 all'energia, allora non cambia quale input fornisce la soluzione minima. Quindi possiamo aggiungere c_Sp = c_pT = 0 alle nostre equazioni simultanee e ottenere
c_pT + c_qT = K + V_{p,q}(0,0)
c_pT + c_Sq + c_pq = K + V_{p,q}(0,1)
c_Sp + c_qT + c_qp = K + V_{p,q}(1,0)
c_Sp + c_Sq = K + V_{p,q}(1,1)
Ora, l'approccio standard a un determinato sistema è di impostare K , riducendo a
c_qT - K' = V_{p,q}(0,0)
+ c_pq - K' = V_{p,q}(0,1)
c_Sp + c_qT - K' = V_{p,q}(1,0)
c_Sp - K' = V_{p,q}(1,1)
con soluzione
K' = V_{p,q}(1,0) - V_{p,q}(0,0) - V_{p,q}(1,1)
c_Sp = V_{p,q}(1,0) - V_{p,q}(0,0)
c_qT = V_{p,q}(1,0) - V_{p,q}(1,1)
c_pq = V_{p,q}(0,1) + V_{p,q}(1,0) - V_{p,q}(0,0) - V_{p,q}(1,1)
Questo richiede solo un margine aggiuntivo tra K e c_Sq = c_qp = c_pT = 0 , che darà una piccola ottimizzazione nell'impostazione e nel calcolo del flusso del grafico. Ovviamente, induce dei vincoli di disuguaglianza leggermente diversi sui valori che p può assumere.
Mettere tutto insieme
Per ogni q , aggiungiamo gli spigoli
S->p with weight D_p(1) + SUM_q (V_{p,q}(1,0) - V_{p,q}(0,0))
p->T with weight D_p(0) + SUM_q (V_{q,p}(1,0) - V_{q,p}(1,1))
Per ogni V_{p,q} aggiungiamo il bordo
p->q with weight V_{p,q}(0,1) + V_{p,q}(1,0) - V_{p,q}(0,0) - V_{p,q}(1,1)