Substruttura ottimale

Question

Sto cercando di ottenere un quadro più completo dell'uso della proprietà di sottostruttura ottimale nella programmazione dinamica, ma sono andato cieco sul perché dobbiamo dimostrare che qualsiasi soluzione ottimalmente al problema contiene soluzioni ottimali per i problemi secondari.

Non sarebbe sufficiente mostrare che alcuni soluzione ottimale al problema ha questa proprietà, e quindi utilizzare questo per sostenere che poiché la soluzione costruita dal nostro algoritmo ricorsivo è almeno buono come Una soluzione ottimale, sarà sé ottimale? In altre parole, non riesco a individuare dove nell'argomento della correttezza per il nostro algoritmo abbiamo bisogno che tutte le soluzioni ottimali contengano soluzioni ottimali a problemi secondari.

per chiarire:

La definizione del CLRS di sottostruttura ottimale afferma che "un problema presenta una sottostruttura ottimale se qualsiasi soluzione ottimale per il problema contiene all'interno di soluzioni ottimali ai sottoproblemi".

Perché non sarebbe abbastanza da dire che "un problema presenta una sottostruttura ottimale se alcuni soluzione ottimale al problema contiene all'interno di soluzioni ottimali a sottoproblemi"?

Answer 1

Sono stato infastidito un po 'a questo nella mia ricerca sugli algoritmi di approssimazione, che coinvolge programmi dinamici che trovano approssimativamente soluzioni ottimali. Il modo giusto per pensare alla correttezza dei programmi dinamici, credo, è una riduzione (nel senso della teoria della complessità) da un problema a un subproblem. Questa riduzione spesso viene applicata in modo ricorsivo e con la memoizzazione, ma quelle sono dettagli in questo momento.

Lascia che sia il problema e B sia il subproblem. C'è solo un sottoproblem perché possiamo combinare più sottoproblemi indipendenti in uno tramite un prodotto cartesiano generalizzato. La riduzione è composta da due funzioni: F, da un'istanza a un'istanza B e H, da una soluzione B a una soluzione A. La proprietà di correttezza di cui abbiamo bisogno è che, per ogni funzione G da ogni B-istanza a una corrispondente soluzione B ottimale (l'Oracle), la composizione h. g. f è una funzione da ciascuna a-istanza a una soluzione a-soluzione ottimale corrispondente. (Se H ha bisogno di accedere all'istanza A-istanza, quindi estendere B in modo che le sue istanze contengano un'istanza a istanza che deve essere copiata verbatim nella corrispondente soluzione B.)

Per effettuare il tuo punto, per una particolare a-istanza e una soluzione A ottimale, non è necessario esistere un Oracle G tale che la pipeline h. g. F produce tale soluzione dall'istanza data. (In altre parole, H non è necessario non aver bisogno di essere individuato.) D'altra parte, H deve essere in grado di gestire ogni possibile soluzione B ottimale da G per la B-istanza costruita da f.

Una strategia comune per garantire che H è corretta è trovare una funzione "sottostruttura" K da A-Solutions a soluzioni B e un modo per la sottostruttura "Split", cioè una prova che, data una soluzione A X e una soluzione B y non peggio di k (x), esiste una soluzione A-soluzione x 'non peggiore di x tale che k (x')= y. Quindi H può ottimizzare tutto nell'immagine inversa sotto K del suo input. Non è necessario che la giunzione si applica a tutte le soluzioni X, solo una ottimale.

Answer 2

Nella programmazione dinamica abbiamo suddiviso il problema con problemi più piccoli, fare qualche manipolazione e fornire una risposta per una risposta più grande - molto simile all'approccio di ricorsione (e senza alcuna coincidenza).

Ora, quando arriviamo a dimostrare formalmente la correttezza di tale algoritmo, questo è fatto per induzione. Dimostriamo che la nostra "clausola di base" è corretta (di solito molto facile), e poi assumiamo che qualsiasi problema più piccolo di quello attuale - sia anche ottimale. Utilizziamo quindi questa ipotesi per dimostrare la correttezza del problema più grande.

Se non sapevamo che tutte le soluzioni sono ottimali - non saremmo in grado di dimostrare che l'utilizzo di un ulteriore passo in più, siamo stati in grado di modificare una soluzione ottimale per un problema più piccolo per una soluzione ottimale al problema più grande - non ci sarebbe semplicemente Informazioni sufficienti per dimostrare questo reclamo.

Se sapessimo che alcuni dei sottoproblemi sono una soluzione ottimale - non sarebbe sufficiente a garantire che l'utilizzo di questo subproblem, che abbiamo una soluzione ottimale per - effettivamente è quella che dobbiamo ottenere la soluzione ottimale al problema più grande .

---

.

Dai un'occhiata a Knaffa per esempio, e diamo un'occhiata al suo DP Step:

f(x,i) = max(f(x-weight[i],i-1) +val[i], f(x,i-1))

.

Se sapevamo solo uno di loro è ottimale - non siamo stati in grado di dimostrare che l'algoritmo è corretto, perché avremmo potuto aver bisogno del caso "altro", dove non abbiamo una soluzione ottimale a.

Se abbiamo scelto f(x,i-1) nel max() - potrebbe essere stata la scelta sbagliata. Assicurando che abbiamo una soluzione ottimale a tutti i subproblemi, ci assicuriamo che questo non possa accadere.