(HW4.2) Memorizzare esiti per aumentare efficienza

Question

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?

Answer 1

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

Comments

oppure una tupla

---

Sì sono riuscito eventualmente a risolvere con quel metodo usando tuple anche prima della tua risposta. Grazie comunque!