Il problema consisteva nel trovare il percorso che attraversasse più anelli possibili (rispettando le regole di attraversamento) in un tempo massimo fissato.
La soluzione proposta fa uso di diverse tecniche di programmazione: greedy, scelta casuale, backtrack con pruning e ricerca locale.
Nella repository è possibile trovare:
- il dataset usato per la correzione e valutazione del progetto
- il testo del progetto con tutte le specifiche
- la nostra soluzione al problema proposto
- una spiegazione della soluzione proposta.
Per compilare ed eseguire il codice consultare il file prog2.testo.pdf.
Per creare le immagini dei vari output generati dall'algoritmo è possibile usare uno script in Ruby presente nella cartella test.
Se si desidera utilizzarla è necessario avere installato ImageMagick, una versione di Ruby, il packet manager RubyGems e la gemma Bundler.
Successivamente effettuare i seguenti passi:
Clonare il progetto:
$ git clone https://github.com/emanuelebeozzo/progetto2algoritmi.gitInstallare le dipendenze:
$ bundle installRecarsi nella carella test:
$ cd testEd eseguire il seguente comando:
ruby generate_paths.rb ../path_to_input.txt ../path_to_output.txtDove gli argomenti dello script sono il file di input del problema e il relativo file di output.
In automatico genererà una cartella img con all'interno tutti i percorsi generati.
Il programma si è rivelato in grado di saper svolgere egregiamente grafi sparsi oppure densi ma di dimensione ridotta. L'idea di utilizzare la ricerca locale per poter migliorare le soluzioni ogni volta, di impedire all'algoritmo di cercare una soluzione migliore prima di aver trovato una di almeno ugual valore e l'implementazione di una sottospecie di backtrack in modo da poter tornare all'anello precedente hanno permesso nel complesso di ottenere un punteggio di 72.5/100.
Proponiamo di seguito un paio di gif che mostrano il funzionamento dell'algoritmo e basate sulle soluzioni ottenute da input del dataset
