Algoritmi di Path Consistency
Confronto tra PC-1 e PC-2
Autore : Cordioli Federico VR084495
Docente: dott. Farinelli Alessandro
Anno Accademico: 2009/2010
Obiettivi del progetto
Il progetto aveva come scopo realizzare il confronto tra due algoritmi per forzare la consistenza su una rete di vincoli. Tale rete di vincoli
e' stata rappresentata mediante un grafo non diretto e si sono considerati gli algoritmi PC-1 e PC-2.
Il confronto e' stato quindi eseguito su reti di vincoli binari generate in modo pseudo-casuale su cui inoltre era possibile specificare
il numero di variabili e la dimensione del dominio a loro associato.
Si sono quindi riassunti i risultati ottenuti in tabelle in base al numero di nodi e alle dimensioni del dominio caratteristiche delle
reti generate.
I risultati hanno permesso di osservare che :
- il numero di revise3 utilizzate da PC-2 e' sempre minore o uguale al numero di PC-1;
- se la non path-consistenza (o la path-consistenza) viene rilevata durante il primo ciclo PC-2 e PC-1 necessitano del medesimo numero di revise3;
- se la non path-consistenza viene rilevata dopo il primo controllo degli archi PC-2 necessita un numero di revise3 minori o uguali a PC-1;
- superato un determinato valore di k tutti i grafi generati casualmente risultano consistenti;
- il valore del k necessario a ottenere grafi tutti consistenti aumenta all'aumentare del rapporto tra nodi e dominio;
- l'andamento della curva risultante evidenzia una fase crescente (in cui generalmente i grafi non sono path-consistenti) seguita da una decrescente (in cui invece sono generalmente path-consistenti). Quindi il numero di Revise3 all'aumentare di k cresce fino ad arrivare a un valore per cui e' necessario effettuare un notevole numero di Revise3, superato tale picco tale numero decresce;
- le differenze maggiori tra le esecuzioni di PC-1 e PC-2 si hanno in prossimita' di tale picco;
- PC-1 ha in generale un variabilita' maggiore nel numero di esecuzioni necessarie rispetto a PC-2;
- mantenendo fisse le dimensioni del dominio si nota una crescita del valore di k, corrispondente al picco, all'aumentare del numero di nodi;
- mantenendo fisso il rapporto tra il numero di nodi e le dimensioni del dominio si nota una forte similitudine tra le curve risultanti, sebbene il picco si trovi per un valore di k minore nel caso si abbia un numero di nodi minore.
E' quindi stato possibile ipotizzare che la scelta dell'algoritmo piu' conveniente sara' :
- PC-1 nei casi in cui si debbano testare grafi principalmente non consistenti se il coefficiente k e' basso;
- PC-1 nei casi in cui vi siano da testare grafi principalmente consistenti se il coefficiente k e' alto ;
- PC-2 in tutti gli altri casi.
Input : Grafo
Output : Path-Consistenza del Grafo e numero di Revise3 necessarie a PC-1 e PC-2
Implementazione
Linguaggio : Java
Compilatore : JDK 1.6.0 (Windows 32 bit)
Relazione
Contenuto relazione :
- Basi teoriche
- Definizioni preliminari
- Path Consistency
- Revise3
- PC-1 e PC-2
- Implementazione
- Classi principali
- Oggetti e classi accessorie
- Considerazioni
- Risultati
- Analisi risultati
Risorse