Impossibile risolvere la programmazione dinamica

-2

Ho avuto un incarico sulla programmazione dinamica a causa della scorsa notte, ma ho dovuto renderlo incompleto perché non riuscivo a capire come risolvere l'ultimo problema:

The state wants to monitor traffic on a highway n miles long. It costs ci to install a monitoring device on mile i of the highway. The maximum distance between monitoring devices should not be more than d miles. That is, if there is a monitoring device on mile i, then there must be one monitoring device from mile i + 1 to mile i + d (or it is the case that i + d > n). The state wants a plan that will minimize the cost. Assume there is an array C[1..n] of costs.

Let vk be the cost of the best solution assuming a k mile highway and assuming a monitoring device on mile k. Given C and d, if the values of v1 through vk-1 are known, show how to determine the value of vk. You can write this mathematically, or provide pseudocode in the style of the book. Note you need to take into account all possible values of k from k = 1 to k = n.

Sono sicuro che un problema simile a questo verrà visualizzato durante l'esame e mi piacerebbe almeno sapere da dove cominciare a risolvere questo problema, quindi qualsiasi assistenza è apprezzata.

    
posta WoernerBro 26.03.2016 - 04:30
fonte

1 risposta

1

Con qualsiasi problema di programmazione dinamica. Il trucco sta realizzando dove puoi condensare molte possibilità in un minor numero di possibilità.

Un approccio a forza bruta a questo problema sarebbe quello di provare ogni possibile posizione per i dispositivi di monitoraggio, eliminare quelle possibilità che sono illegali (la distanza è maggiore di d), e poi trovare quella con il costo minimo.

Per passare da una forza bruta alla programmazione dinamica, devi trovare dove molte possibilità sono equivalenti. Puoi farlo se ti rendi conto che non devi conoscere i dettagli di dove si trovano le stazioni di monitoraggio prima di una determinata località, tutto quello che devi sapere è il costo minimo per arrivarci. Sulla base di questo, puoi iniziare dal caso più semplice e lavorare da lì.

A partire da k = 1. Quanto costa? Questo è facile perché sappiamo che dobbiamo mettere un dispositivo nella posizione 1, e non ci sono posizioni precedenti, quindi v [1] = C [1].

Che dire di k = 2? Se d = 1, dovevamo avere un dispositivo nella posizione 1, quindi il costo è v [1] + C [2]. Se d = 2, abbiamo anche la possibilità di non aver bisogno di un dispositivo in una posizione precedente, quindi il costo è solo C [2]. Scegliamo la possibilità con il minimo costo che è valido e chiamiamo questo v [2].

Che dire di k = 3? Ora dobbiamo considerare v [2] + C [3], v [1] + C [3], o solo C [3]. Nuovamente, scegliamo quello con il minimo costo che è valido e lo chiamiamo v [3].

Possiamo procedere nello stesso modo fino a raggiungere la posizione n.

    
risposta data 26.03.2016 - 05:28
fonte

Leggi altre domande sui tag