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 : E' quindi stato possibile ipotizzare che la scelta dell'algoritmo piu' conveniente sara' :

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 :
  1. Basi teoriche
  2. Implementazione
  3. Considerazioni

Risorse

Relazione
Sorgenti