Aiuto dimostrazione su algoritmo greedy

[Net_Raider]

salve, ho risolto questo esercizio sulla progettazione di un algoritmo greedy:

Si supponga di dover effettuare un viaggio dalla localià $A$ alla località $B$ con un auto che ha un’ autonomia di $k$ chilometri. Lungo il percorso, a partire da $A$ sono presenti $n$ distributori di benzina, ciascuno distante dal precedente meno di $k$ chilometri e l’ ultimo dista meno di $k$ chilometri da $B$. Sia $d_i$ la distanza che separa il distributore $i$ dal distributore $i + 1$, per $i = 1, 2, . . . , n - 1$ e sia $d_n$ la distanza da $B$ dell’ ultimo distributore. Descrivere un algoritmo greedy che seleziona un numero minimo di distributori in cui far tappa durante il viaggio. Giustificare le affermazioni fatte.

eccolo:

//restituisce una stringa binaria di dimensione n dove s[i] = 1 sse si utilizza l'i-esimo distributore
Alg(d, n, k)
inizializza il vettore s[1...n] a 0
autonomia = k
i = 1
while(i <= n)
{
     if(autonomia < d[i])
     {
          autonomia = k
          s[i] = 1
     }
     autonomia = autonomia - d[i]
     i = i + 1
}
return s

ora l'unico passo da fare è dimostrare che l'algoritmo restituisca la soluzione ottima. ma è qui il punto: non so come dovrei fare. l'unica cosa che mi viene in mente è che banalmente, per costruzione, l'algoritmo utilizza un distributore solo se ce n'è la necessità, perciò utilizza il minor numero di distributori, ma non mi sembra che abbia molto senso come dimostrazione...

ciao e grazie

[Umby2]

"Net_Raider":
.... l'algoritmo utilizza un distributore solo se ce n'è la necessità, perciò utilizza il minor numero di distributori, ma non mi sembra che abbia molto senso come dimostrazione...

mi sembra cosi' tanto logico, che non necessita manco di una dimostrazione (considerando che al distributore si faccia sempre il pieno...)

L'unica osservazione che farei è quella che ci manca un dato: la distanza dal punto A al primo distributore..... mi sbaglio?

[apatriarca]

Devi secondo me in qualche modo dimostrare che scegliendo un distributore diverso il numero di distributori non diminuisce. Supponiamo che fino ad un distributore $d_i$ la scelta sia stata uguale a quella effettuata con il tuo algoritmo. It distributore successivo per il tuo algoritmo sarà $d_j$. Siccome non è possibile arrivare al distributore $d_{j+1}$ con l'autonomia scelta allora sarà necessario scegliere un distributore $d_s$ con $i < s < j$. $d_k$ che sarà la scelta ancora successiva per il tuo algoritmo è sempre massimale e quindi partendo da $d_s$ sarà possibile arrivare al massimo a $d_k$. Siccome ad ogni passaggio il percorso alternativo sceglie un distributore che è precedente o al massimo uguale a quello scelto dal tuo algoritmo allora dovrà avere un numero di rifornimenti che è al massimo uguale al tuo, ma di certo non inferiore.

[Net_Raider]

@umby: il primo distributore è in A

@apatriarca: non capisco perchè non posso arrivare a $d_j+1$ se l'algoritmo sceglie $d_j$

grazie mille per l'interessamento

[apatriarca]

Non puoi arrivare a $d_{j+1}$ perché nel tuo algoritmo scegli un distributore solo se non è possibile arrivare al successivo. Se quindi si parte dallo stesso distributore precedente le uniche scelte possibili sono quelle fino a $d_j$ compreso. Ma allora seguendo lo stesso ragionamento si potrà arrivare al massimo a $d_k$ (perché è il massimo distributore raggiungibile da $d_j$ che è quello più avanti nel percorso). E così via fino alla fine.

[Net_Raider]

grazie mille, sei stato perfetto ho capito tutto.
magari per te sono cazzatelle, ma io non sono tanto pratico di dimostrazioni (fortunatamente me la cavo con gli algoritmi, almeno questo XD)

[tvd_40]

Innanzitutto grazie..perché mi trovo a dover eseguire lo stesso esercizio e mi siete stati di grande aiuto

..tuttavia mi resta ancora un dubbio:
nella fase di inizializzazione, quando si assegna autonomia= k è come se in A si effettuasse il 1˚ rifornimento o sbaglio?
Però se è così poi questo rifornimento non viene conteggiato?

Vi sarei molto grata se potreste risolvermi quest'ultimo dubbio