Come recuperare i criteri dopo la programmazione dinamica?

Question

Come recuperare i criteri dopo la programmazione dinamica?

#1 da (1 voti)
#2 da (-2 voti)

4

Sto lavorando su un semplice problema di allocazione delle risorse, che sto risolvendo usando il DP all'indietro. Il codice completo è disponibile all'indirizzo: link

Funziona bene, ma sono un po 'perplesso su come recuperare la politica ottimale una volta eseguita l'ottimizzazione. Uso un decoratore di memoization, ma non ho idea di come ottenerne la politica ottimale alla fine. (La politica sarebbe una serie di 1,0 come descrizione di quando allocare e quando no.)

def memoize(f):
    cache = {}

    def memoizedFunction(*args):
        if args not in cache:
            cache[args] = f(*args)
        return cache[args]

    memoizedFunction.cache = cache
    return memoizedFunction

In uno sforzo alternativo io uso:

def record(D,key,item):
    """Records the value of item in the dictionary d with k"""
    if key in D.keys():
        D[key].append(item)
    else:
        D[key] = [item]

    return D

E nel DP:

   if v == no_pump:
        pos = 0
    else:
        pos = 1

    record(X,i+1,pos)

La mia impressione è che se posso creare un nuovo dizionario (X) per ogni politica e registrare il valore ottimale fino alla sua esecuzione, potrebbe funzionare. Ma non so come farlo. Inoltre sembra abbastanza inefficiente.

Per chiarire: i metodi in avanti, o la conversione in un grafico non sono adatti in quanto l'intero problema sarà convertito in un problema di controllo stocastico in seguito.

python dynamic-programming

posta ic_fl2 23.03.2016 - 13:14

fonte

2 risposte

Leggi altre domande sui tag python dynamic-programming

Qual è il modo più sicuro per capire se la decrittografia ha avuto successo? Le migliori pratiche per caricare file di grandi dimensioni, visualizzare in anteprima e modificare prima di salvare nel database?

score 1 · Answer 1

In questo momento la funzione che memoize restituisce semplicemente il punteggio la soluzione migliore. Il cambiamento è tale da restituire una tupla del primo passo della soluzione migliore e il punteggio. Qualcosa come:

@memoize
def score(...)
    _, zero_score = score(...)
    _, one_score = score(...)
    if zero_score < one_score:
       return 0, zero_score
    else:
       return 1, one_score

Ora, per scoprire il passaggio successivo, devi semplicemente chiamare il punteggio e ti dirà il passo successivo e il punteggio.

score -2 · Answer 2

-2

Spostare il dizionario memoizedFunction.cache dalla funzione memoize della funzione in modo che sia a livello globale. Quindi sarai in grado di interrogarlo dopo l'esecuzione dell'ottimizzazione.

risposta data 25.03.2016 - 20:14

fonte