(HW4.2) Memorizzare esiti per aumentare efficienza

1
1803699 (800 points)
1 5 16
asked Dec 2, 2017 in Es2 by 1803699 (800 points)
Il mio programma perde una miriade di tempo nei test con le griglie vuote perché ricalcola più volte le stesse configurazioni a cui arrivo da antenati diversi (esempio: ['o','o','x']['','','']['','',''] può essere raggiunta in due modi diversi a seconda da quale 'o' viene messa alla prima mossa e quale alla terza). So di dover implementare un sistema di memorizzazione in qualche modo per evitare di fargli calcolare di nuovo esiti che ha già calcolato, ma non ho idea sul come implementare tale sistema di memorizzazione. Qualcuno può indirizzarmi alla risposta?

1 Answer

Best answer
m
mirko (1920 points)
3 12 19
answered Dec 3, 2017 by mirko (1,920 points)
selected Dec 4, 2017 by 1803699
Puoi usare un dizionario in cui la chiave è una configurazione (cioè, il 'nome' di un NodoTris) e il valore è il risultato per quel sottoalbero. In questo modo, prima di processare un nodo, puoi controllare nel dizionario se ne hai già calcolato la soluzione.

Edit: probabilmente non ti fa usare direttamente la lista di liste come chiave, quindi trasformatela in una stringa
andrea.sterbini (172780 points)
513 935 1789
commented Dec 3, 2017 by andrea.sterbini (172,780 points)
oppure una tupla
1
1803699 (800 points)
1 5 16
commented Dec 3, 2017 by 1803699 (800 points)
Sì sono riuscito eventualmente a risolvere con quel metodo usando tuple anche prima della tua risposta. Grazie comunque!