logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-11032005-114319


Tipo di tesi
Tesi di laurea specialistica
Autore
De Pascale, Giovanna
Indirizzo email
gdepasca@cli.di.unipi.it
URN
etd-11032005-114319
Titolo
Progetto e sperimentazione di algoritmi euristici per il problema dei cammini bilanciati
Dipartimento
SCIENZE MATEMATICHE, FISICHE E NATURALI
Corso di studi
INFORMATICA
Relatori
relatore Cappanera, Paola
relatore Prof.ssa Scutellà, Maria Grazia
Parole chiave
  • algoritmo pseudopolinomiale
  • cammini arc-disjoint
  • euristica
  • cammini node-disjoint
  • programmazione dinamica
  • bilanciamento
Data inizio appello
17/02/2006
Consultabilità
Completa
Riassunto
Nel primo capitolo viene fornita una formulazione del problema dei cammini bilanciati nel caso di grafi aciclici, si analizza la complessità computazionale in tempo di tale problema e si descrive con completezza un algoritmo di risoluzione. Nel capitolo si affrontano e si analizzano anche le versioni node-disjoint e arc-disjoint del problema, e si descrive come adattare l’algoritmo precedentemente descritto per poter risolvere le due varianti del problema per alcuni casi speciali.
Nel secondo capitolo si presenta la generalizzazione del problema al caso di grafi di input generici. Si mostra come l’algoritmo per reti acicliche, descritto nel primo capitolo, possa essere adattato al caso in cui il grafo di input contenga cicli e si mostra come tale approccio possa essere utilizzato per progettare una famiglia di algoritmi euristici che guidi efficientemente nella ricerca di soluzioni di buona qualità.
Nel terzo capitolo innanzitutto si descrive il software che implementa l’approccio euristico proposto e successivamente si riportano le principali scelte implementative effettuate nelle fasi di progettazione e realizzazione del software.
Nei capitoli successivi si descrive il dataset utilizzato per effettuare le sperimentazioni e si fa un’analisi dei risultati ottenuti.