Introduzione agli algoritmi greedy e l’algoritmo del cassiere¶

Algoritmo del cassiere¶

L’algoritmo del cassiere può essere un buon esempio di algoritmo greedy: Il problema che ci viene posto è quello di un cassiere zelante che dovendo dare un resto ai clienti, vuole creare una regola di decisione per dare un resto esatto ai clienti, utilizzando il minimo numero di monete possibili.

Gli argomenti in input di questo algoritmo sono chiaramente:

• \(R\): il resto da fornire al cliente
• \(C\): L’insieme di monete a disposizione per dare il resto

L’algoritmo del cassiere, in versione Greedy segue un ragionamento di questo tipo:

• Seleziona la moneta di maggior valore in \(C\), che chiameremo \(X\)
• Confronta la moneta \(X\) con il resto da fornire \(R\)
• Se \(X<R\), aggiunge la moneta alla soluzione e la toglie dall’insieme \(C\)
• Se \(X>R\), non aggiunge la moneta alla soluzione

Questo ragionamento si ripete fino all’individuazione della soluzione, o alla dimostrazione che essa non è raggiungibile.

Di seguito è riportata una rappresentazione dell’algoritmo in Python.

def cassiere_alg (r, c):
print ('Devo fornire', r, 'euro di resto' )
print ('Ho a disposizione monete di taglio:', str(c))
c.sort()
s=[]
while r>=0:
        x=c[-1]
        del c[-1]
        if r>=x:
                r=r-x
                s.append(x)
        if r==0:
                print ("La soluzione e':" + str(s))
                return s
        if c==[]:
                print ("Non e' possibile trovare una soluzione")
                break

cassiere_alg(73, [100, 50, 20, 10, 5, 2, 1])

Vediamo adesso con un esempio il funzionamento in ogni loop dell’algortimo del cassiere, ipotizzando di dover fornire un resto di 73c, avendo a disposizione i tagli di monete degli euro.

• \(R= 73c\)
• \(C= (100c, 50c, 20c, 10c, 5c, 2c, 1c)\)

In questa situazione l’algoritmo, pesca ad ogni loop la moneta di maggior valore che ha a disposizione, controlla che non sia maggiore del resto da erogare e la aggiunge alla soluzione quindi

Loop 1:

• \(X=max(C)=100c\)
• \(100c \geq 73c\)
• \(S= (\emptyset)\)
• \(C=(50c, 20c, 10c, 5c, 2c, 1c)\)
• \(R= 73-0= 73c\)

Loop 2:

• \(X=max(C)=50c\)
• \(50c \leq 73c\)
• \(S= (50c)\)
• \(C=(20c, 10c, 5c, 2c, 1c)\)
• \(R= 73-50= 23c\)

Loop 3:

• \(X=max(C)=20c\)
• \(20c \leq 23c\)
• \(S= (50c, 20c)\)
• \(C=(10c, 5c, 2c, 1c)\)
• \(R= 23-20= 3c\)

Loop 4:

• \(X=max(C)=10c\)
• \(10c \geq 3c\)
• \(S= (50c, 20c)\)
• \(C=(5c, 2c, 1c)\)
• \(R= 3-0 = 3c\)

Loop 5:

• \(X=max(C)=5c\)
• \(5c \geq 3c\)
• \(S= (50c, 20c)\)
• \(C=(2c, 1c)\)
• \(R= 3-0 = 3c\)

Loop 6:

• \(X=max(C)=2c\)
• \(2c \leq 3c\)
• \(S= (50c, 20c, 2c)\)
• \(C=(1c)\)
• \(R= 3-2= 1c\)

Loop 7:

• \(X=max(C)=1c\)
• \(1c \leq 1c\)
• \(S= (50c, 20c, 2c, 1c)\)
• \(C=(\emptyset)\)
• \(R= 1-1= 0\)

Visto che \(R=0\) siamo arrivati alla soluzione dell’algoritmo, che risulta essere \(S=(50c, 20c, 2c , 1c)\).

In generale, l’algoritmo del cassiere e gli algoritmi greedy devono rispettare alcune caratteristiche, che riportiamo di seguito:

• Set di candidati: per trovare una soluzione al problema, è necessario che sia presente un insieme di candidati potenziali per la soluzione.
• Analisi: ogni elemento deve essere esaminato secondo la regola di decisione che ci siamo dati, e una volta esaminato, viene rimosso dall’insieme dei candidati, questo ci ricorda la peculiarità degli algoritmi greedy di non poter tornare indietro.
• Funzione di selezione: è la funzione che potremmo pensare come il cuore dell’algoritmo, infatti è il momento della scelta greedy. Fra i candidati prendiamo il più promettente seguendo il criterio di ottimo locale, non considerando cosa ciò possa comportare per la ricerca dell’ottimo totale. Nel nostro caso è la funzione che cerca il massimo nel set delle monete in \(C\).
• Funzione di ammissibilità: Si controlla che il candidato esaminato possa essere soluzione, nell’algoritmo del cassiere questo passo è il controllo che la moneta candidata sia inferiore del resto ancora da erogare.
• Funzione di Ottimo: è la funzione che controlla che il set di soluzione candidato sia anche l’ottimo specifico.
• Funzione Obiettivo: E’ la funzione che restituisce il risultato dell’algoritmo

Arriviamo ad una conclusione dell’algoritmo in due casi:

• Il resto \(R\) è uguale a zero, ed allora abbiamo trovato una soluzione, \(S\)
• Il resto \(R\) è maggiore di zero, e sono stati esaminati tutti gli elementi in \(C\), questo vuol dire che nessun elemento di \(C\) è ammissibile secondo le regole di decisione e in base alle scelte fatte precedentemente, il problema quindi non ha soluzione.