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 6 1.3.1 Tecniche di Consistenza e Algoritmi di Propagazione Le Tecniche di Consistenza e gli Algoritmi di Propagazione sono metodi che cercano, utilizzando i vincoli in maniera attiva, di prevenire a priori i fallimenti anzichØ recuperare quelli gi avvenuti. Pu , infatti, accadere che un assegnamento sbagliato nei primi livelli dell albero produca come effetto il fallimento della ricerca in quel ramo molto piø tardi, quindi molto in profondit nell albero decisionale. Un algoritmo in grado di riconoscere subito questo tipo di errori evita la generazione inutile di un elevato numero di sottoalberi. Entrambi i metodi si occupano di utilizzare i vincoli il prima possibile per evitare inutili ricerche e, quindi, inutile spreco di tempo e di risorse. Le Tecniche di Consistenza sono meccanismi per propagare i vincoli prima di cominciare la ricerca, e quindi derivare un problema piø semplice, ma equivalente a quello originale completo. Viceversa i secondi si basano sulla propagazione dei vincoli per eliminare, durante la ricerca, quei valori dai domini delle variabili, e quindi quelle porzioni dell albero decisionale, che porterebbero, associati ai valori gi assegnati, ad un sicuro fallimento. Tipicamente in un CSP vengono applicate prima le Tecniche di Consistenza e successivamente gli Algoritmi di Propagazione. Una volta che non sia piø possibile applicare tali metodi, o si Ł giunti ad una soluzione o Ł necessario scegliere un valore da assegnare ad una delle variabili ancora libere. La figura 1.2 esemplifica la differenza tra utilizzo dei vincoli a priori e a posteriori. Utilizzando i vincoli a priori viene evitata la fase di test, riducendo quindi drasticamente il numero di backtracking. Infatti, ogni assegnamento generato dal metodo Generate and Test, ha, perlomeno a priori, la stessa probabilit di essere una soluzione di tutti gli altri assegnamenti; viceversa, l eliminazione di valori incompatibili dai domini grazie alla propagazione dei vincoli, comporta anche un aumento

Anteprima della Tesi di Alessio Guerri

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

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.