Come dimostrare che una strategia di programmazione dinamica funziona per un algoritmo?

In linea di principio, qualsiasi problema di ottimizzazione multistadio è risolvibile usando la programmazione dinamica, se riesci a trovare la nozione giusta dello stato . Non parli di quale classe di problemi stai lavorando, quindi è difficile dare delle linee guida generali. Farò qui le seguenti ipotesi:

• Stai osservando i problemi di ottimizzazione deterministica (al contrario dei problemi di ottimizzazione stocastica).
• Devi scegliere un numero finito di decisioni e alla fine vuoi massimizzare i premi che dipendono da tutte le tue decisioni (l'argomento funziona anche se sei interessato a minimizzare i costi).
• Puoi scomporre la ricompensa totale in una somma di premi individuali, idealmente, in modo tale che la decisione n influenzi la ricompensa totale per la prima volta solo da n -th termine in poi.

Per risolvere questo problema con la programmazione dinamica, devi trovare uno stato _n che soddisfi le seguenti proprietà:

state_n+1 = function(state_n, decision_n)

e

reward_n = function(state_n, decision_n)

Se queste condizioni sono soddisfatte, la programmazione dinamica offre una soluzione ottimale. Per prima cosa definisci le funzioni value

V_n(state_n) = max_decisionn[ reward_n + V_n+1(state_n+1)]

e risolvere ricorsivamente queste funzioni di valore in modo arretrato.

NOTA : questi sono i tipi più semplici di problemi che possono essere risolti utilizzando la programmazione dinamica. Per ulteriori dettagli, consulta qualsiasi libro standard sulla programmazione dinamica, ad es. Berksekas .

In generale, la soluzione di programmazione dinamica può essere dimostrata mostrando che la soluzione presenta la proprietà della sottostruttura ottimale.

Fondamentalmente, si formula il problema reale come composto da sottoproblemi più piccoli e quindi si combinano le soluzioni per ottenere la risposta finale. Nella combinazione, se la dimensione del problema aumenta, la soluzione per sottoproblemi più piccoli deve essere ancora ottimale affinché la combinazione funzioni effettivamente.

Ad esempio, se in un grafico stai cercando di trovare il percorso più breve tra A e C e sai già (in qualche modo) che quel percorso passa attraverso un punto intermedio B, e sai già il modo più breve per ottenere da A a B, quindi devi solo trovare un modo più breve per arrivare a C da B. Non devi preoccuparti di trovare un nuovo modo da A a C, questo è ciò che significa la proprietà di sottostruttura ottimale. Per una prova di correttezza della programmazione dinamica, dimostrare questa proprietà è sufficiente per dimostrare che il tuo approccio è corretto.

Il modo in cui provi l'algoritmo di Greedy mostrando che mostra che la struttura matroid è corretta, ma non sempre funziona. Alcuni algoritmi greedy non mostreranno la struttura di Matroid, tuttavia sono algoritmi corretti di Greedy. Ad esempio, lo schema di codifica di Huffman è un approccio avido, ma non mostra una struttura matroid.

Per dimostrare un algoritmo ingordo, in generale, devi dimostrare che la tua soluzione esibisce -1) proprietà di sottostruttura ottimali come in DP e 2) La scelta fatta da un approccio avido non è sub-ottimale (in pratica mostra che è ottimale o una delle scelte ottimali che possono essere fatte in quel momento)