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.

PROBLEMI DI SODDISFACIMENTO DI VINCOLI 5 assegnamenti, si capisce che utilizzare i vincoli solo a posteriori sia una strada impraticabile per i CSP normalmente analizzati. Infatti per un semplice problema con 5 variabili e domini di cardinalit 10, esistono 10 milioni di permutazioni dei valori, cioŁ 10 milioni di foglie nell albero decisionale. Oltretutto, essendo questo valore esponenziale nel numero delle variabili, gi un problema con il doppio di variabili porta ad avere 10 miliardi di possibili assegnamenti, con un incremento del tempo di computazione di un fattore 1000. ¨ per possibile utilizzare i vincoli in maniera piø intelligente riducendo a priori l albero di ricerca. Per esempio, nella successiva figura 1.1 Ł rappresentato l albero decisionale di un semplice problema di 3 variabili con domini (0,1) e vincoli X≠ Y,X≠ Z,Z≥ X. Fig. 1.1: Esempio di albero decisionale per un problema di tre variabili con domini di cardinalit 2 Il Generate and Test risale 4 volte l albero in backtracking prima di trovare la soluzione (0,1,1), mentre lo Standard Backtracking soltanto 2 volte. Utilizzando per i vincoli subito dopo l assegnamento del valore 0 ad X, si pu eliminare a priori il valore 0 sia da Y sia da Z, in quanto incompatibili rispettivamente con il primo e con il secondo vincolo, ed arrivare alla soluzione senza eseguire nessun backtracking.

Anteprima della Tesi di Alessio Guerri

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

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.