HW 8 approcci consentiti

Question

Ciao a tutti, sto facendo questo post poichè cercando nel forum non ho capito molto sugli "approcci" con cui si può risolvere l'homework 8 senza cadere nel "non consentito".

Più specificatamente nella mia soluzione salvo il risultato ottenuto dai nodi intermedi per poi riutilizzarlo se mosse diverse mi riconducono allo stesso stato della tabella, evitando così numerose ricorsioni e riuscendo ad ottenere un'efficienza più bassa. Ovviamente nessuna variabile globale viene utilizzata ed il dizionario con gli stati viene perso appena ottenuto il risultato finale di una tabella, in quanto viene trasmesso da ricorsione a ricorsione tra i parametri della funzione ricorsiva. Quest'approccio è ritenuto consentito?

Grazie in anticipo per l'aiuto :D

Answer 1

Certamente si.

Sono proibiti i meccanismi di caching che ricordano i risultati di un test nella esecuzione dei test seguenti o nella ripetizione di 15 volte di tutta la batteria che viene usata per calcolare il tempo medio di esecuzione.

Comments

Grazie mille per la risposta velocissima prof!

Answer 2

Ciao, ti consiglio per ottimizzare l’HW che a me ha funzionato, di ricordati le posizioni libere ogni volta che viene generato un nodo per evitare che ogni volta devi calcolarle, non credo che in questo modo cadi nel non consentito.

Comments

Al momento, il mio algoritmo come detto prima, si basa sul ricordare il risultato dei nodi, in modo che ogni volta che ricapito in una situazione identica posso evitare ricorsioni e passare direttamente al nodo successivo. Oltre a questo, come detto tu, ricordo le posizioni vuote e le aggiungo/elimino dalla lista all'occorrenza in modo da non doverle rielaborare sapendo che sono le uniche posizioni vuote su cui posso agire. Infine, invece di trattare la "board" come una lista di liste, con un po' di ingegno mi sono accorto che la si può tranquillamente salvare in un altro modo nettamente più efficiente.

In particolare con quest'ultima modifica sono sceso da 130 di efficienza che era il mio approccio "base" a circa 82.