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 8 le tecniche di consistenza riducono il problema originale eliminando dai domini delle variabili i valori che non possono comparire in alcuna soluzione. Tutte le tecniche di consistenza sono basate su una rappresentazione del problema come un grafo di vincoli. Gli archi possono essere orientati o no: per esempio il vincolo > Ł rappresentato da un arco orientato, mentre il vincolo ≠ da uno semplice (non orientato o doppiamente orientato). Per ogni CSP, esiste un grafo in cui i nodi rappresentano le variabili, e gli archi i vincoli tra le variabili costituenti i nodi che l arco unisce. I vincoli unari sono rappresentati da archi che iniziano e terminano sullo stesso nodo X i , mentre i vincoli binari collegano 2 nodi X i e X j . Fig. 1.3: Rappresentazione di vincoli unari e binari in un grafo di un CSP Esistono vari algoritmi che realizzano gradi diversi di consistenza. ¾ Node-Consistency: consistenza di grado 1. Un nodo di un grafo Ł consistente se, per ogni valore nel dominio, i vincoli unari associati al nodo sono soddisfatti. Tutti i valori che non soddisfano i vincoli possono sicuramente essere eliminati dal dominio. Un grafo viene definito node-consistent se tutti i suoi nodi sono consistenti. Se, per esempio, in un CSP avessimo una variabile X con dominio iniziale [0..10], e il vincolo X>2, per rendere il grafo node-consistent Ł necessario eliminare i valori [0..2] dal dominio di X. ¾ Arc-Consistency: consistenza di grado 2. La consistenza di grado 2 si ottiene partendo da un grafo node-consistent verificando la consistenza di tutti gli archi. Un arco Ł consistente se per ogni valore nel dominio di una variabile esiste almeno un valore nel dominio dell altra variabile che soddisfi i vincoli associati all arco.

Anteprima della Tesi di Alessio Guerri

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

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.