GCP: algoritmi Backtracking e Gaschnig's Backjumping
Introduzione al GCP
Nell'elaborato viene trattato il problema di Graph Coloring nella versione decisionale.
L'obiettivo è di determinare se esiste una k-colorazione
dati in input un grafo non orientato G e k colori. Nel caso affermativo ritornerà comer risultato
l'assegnamento corretto, altrimenti nessuna soluzione.
E' stata inoltre prevista la possibilità di specificare domini diversi per ogni nodo, ovvero il
problema si pone con k colori ma la cardinalità del dominio di un node può essere inferiore o ugale a k.
Algoritmi di risoluzione
Sono state analizzate ed implementate due strategie di ricerca:
-
Backtracking:
può essere descritto come una depht-first su grafo implicito. Un grafo implicito è un grafo non
noto a priori, ogni mossa lungo il grafo corrisponde ad aggiungere un nuovo elemento alla soluzione.
Se procedendo, si arrica a terminare la soluzione ammissibile, la ricerca ha successo.
Se invece si arriva ad un nodo per cui non è possibile completare la soluzione, si torna indietro fino al
primo nodo che ha ancora dei vicini non visitati, dai quali la ricerca riprende.
-
Gasching's Backjumping:
trattasi di un miglioramento applicato al Backjumping applicando uno schema di tipo Lookback.
L'idea di base è che quando non si può più espandere il grafo implicito si effettua un salto indietro non
di un passo ma ad una variabile chiamata culprit, che corrisponde alla variabile più vicina fra
quelle in conflitto con l'attuale nodo, ovvere fra quelle "colpevoli" del fallimento.
Implementazione
L'elaborato è stato programmato in java e le principali classi sono:
- Data:
si occupa di filtrare i dati contenuti nell'input_file per catturare le informazioni
necessarie a generare l'istanza.
- Istance:
costituisce la vera e propria istanza di GCP, inoltre in essa vengono implementati
gli algoritmi risolutivi.
- Node:
rappresenta il nodo di un'istanza, indicando i colori disponibili nel dominio del nodo
e i conflitti con gli altri nodi.
- Domain:
rappresenta un possibile assegnamento per un determinato nodo, è a true se il colore è nel dominio.
- Statistics:
contiene le informazioni relative ai risultati e ai tempi di risposta di un'istanza.
Risultati
Tutti i risultati vengo riportati nel file Result.txt
Inoltre nella directory data sono presenti varie istanze che possono essere utilizzate per
testare il programma. Per sciegliere quali istanze eseguire basta semplicemente modificare
il file main.java.
C'è anche la possibilità di rappresentare tramite 2 grafi le statistiche generate. Nel fie
Statistic.txt sono riassunte le statistiche campionate per numero di nodi dell'istanza.
Viene inoltre generato automaticamente un m_file eseguibile con octave chiamato data.m che
permette la creazione dei grafici rispettivamente salvati in backtracking.png e gaschnig.png
Link