Questo sito utilizza cookie di terze parti per inviarti pubblicità in linea con le tue preferenze. Se vuoi saperne di più clicca QUI 
Chiudendo questo banner, scorrendo questa pagina, cliccando su un link o proseguendo la navigazione in altra maniera, acconsenti all'uso dei cookie. OK

Determinazione del vincitore nelle aste combinatorie: un approccio a vincoli

L'anteprima di questa tesi è scaricabile in PDF gratuitamente.
Per scaricare il file PDF è necessario essere iscritto a Tesionline.
L'iscrizione non comporta alcun costo. Mostra/Nascondi contenuto.

CAPITOLO 1 4 La maggior parte di questi problemi sono NP-difficili, sono cioŁ problemi per i quali non Ł ancora stata trovata, e probabilmente non esiste, un algoritmo in grado di trovare la soluzione in un tempo polinomiale nella dimensione del problema. 1.3 Albero decisionale e strategie di esplorazione Qualunque tecnica di risoluzione di problemi NP-difficili fa uso, almeno concettualmente, di un albero decisionale. Per un CSP, l albero decisionale si pu ottenere facendo corrispondere ad ogni livello l assegnamento di una variabile, secondo un ordine prestabilito, e ad ogni nodo la scelta del valore da assegnare alla variabile corrispondente al livello in cui in nodo stesso si trova. ¨ quindi evidente che ogni foglia dell albero rappresenta una diversa combinazione di valori assegnati alle variabili. Le foglie associate ad assegnamenti compatibili con tutti i vincoli del problema sono soluzioni del problema stesso. La ricerca di una soluzione Ł quindi equivalente all esplorazione dell albero decisionale associato al problema, al fine di trovare una foglia con un assegnamento compatibile con i vincoli imposti. Una metodologia di esplorazione dell albero pu essere quella di generare un assegnamento e verificare a posteriori se sia compatibile con i vincoli dati. In caso negativo viene continuata la ricerca in backtracking, risalendo l albero in maniera cronologica fino ad arrivare al primo nodo che contenga strade ancora inesplorate, e ripetendo l algoritmo su tali strade. Tale algoritmo Ł chiamato Generate and Test. Un altro algoritmo, leggermente migliore di questo, Ł lo Standard Backtracking, in cui ad ogni assegnamento di una variabile viene controllata la compatibilit di tutte le variabili correntemente assegnate con i vincoli, evitando in caso di incompatibilit di percorrere ulteriormente una strada che porter sicuramente ad un fallimento. Notando per che, in un problema con v variabili, ognuna delle quali abbia un dominio di cardinalit d, esistono d v foglie, cioŁ d v possibili

Anteprima della Tesi di Alessio Guerri

Anteprima della tesi: Determinazione del vincitore nelle aste combinatorie: un approccio a vincoli, Pagina 5

Tesi di Laurea

Facoltà: Ingegneria

Autore: Alessio Guerri Contatta »

Composta da 106 pagine.

 

Questa tesi ha raggiunto 1595 click dal 20/03/2004.

 

Consultata integralmente una volta.

Disponibile in PDF, la consultazione è esclusivamente in formato digitale.