Capitolo 2 Una famiglia di algoritmi euristici per reti generiche

Capitolo 2

Una famiglia di algoritmi euristici per reti generiche

Nel primo capitolo il problema dei cammini bilanciati è stato affrontato analizzando il caso di reti acicliche. Se ne studia ora la sua generalizzazione al caso di grafi di input generici. Si mostrerà innanzitutto come l’algoritmo per reti acicliche descritto in 1.4.3.1 possa essere adattato al caso in cui il grafo di input contenga cicli. Si mostrerà quindi come tale approccio possa essere utilizzato per progettare una famiglia di algoritmi euri-stici che guidi efficientemente nella ricerca di soluzioni di buona qualità.

2.1 Grafi di input generici

L’algoritmo descritto per risolvere il problema dei cammini bilanciati node-disjoint, formulato su reti acicliche con un numero costante di livelli e in cui k è , risul-ta essere un algoritmo esatto anche nel caso in cui il problema sia formulato su grafi ge-nerici, cioè su grafi in cui siano presenti dei cicli e in cui non necessariamente k sia

. Nel caso di grafi di input generici, però, l’algoritmo non è più pseudopoli-nomiale. Da qui la necessità di definire un algoritmo euristico per il problema, la cui struttura, come vedremo, è stata suggerita proprio dall’approccio descritto nel capitolo 1.

(

log n Ο

)

)

(

log n Ο

Analizziamo ora con più precisione il caso di grafi di input generici e le eventuali modi-fiche da apportare all’algoritmo.

Sia G = (V, E) una rete orientata con #V = n e #E = m, ai cui archi sono associati costi interi e positivi. Assumiamo che G contenga cicli e supponiamo che su G sia stato for-mulato il problema dei cammini bilanciati node-disjoint. In caso di reti di input qualsia-si, usualmente, a livello applicativo, si richiedono cammini bilanciati node-disjoint che siano semplici, cioè in nessun cammino un nodo può essere visitato più di una volta. Siano dunque

{

s s1, ,...,2 sk

}

i nodi sorgente e

{

t t1, ,...,2 tk

}

i nodi destinazione del

pro-blema, sia C=

{

c_ij | ,

( )

i j ∈E e c_ij∈ ¥+

}

l’insieme dei costi degli archi del grafo G e sia-no s e t la superorigine e la superdestinazione. Valgosia-no le seguenti osservazioni. Innan-zitutto cammini non semplici in G vengono mappati su cammini semplici in a causa della positività dei costi degli archi di G. Sia infatti

U

G

1 2

( , , , ,..., )_i

P= s s j j j_l un cammino

in G contenente un ciclo e tale che ( )c P ≤ . E’ facile mostrare che il corrispondente U

cammino in è semplice: poiché contiene un ciclo, esi-stono due indici

1 ( ) 1 ( , , cs j_i ,..., c P ) U i l P = s s j j G_U P

{

}

, 1,...,

a b∈ l tali che a < b ej_a = ; ciò comporta che nel corrispon-j_b

dente cammino P_U in G_U, ci siano due copie dello stesso nodo j , _a ca

a j e cb a j , con e c c 1 1 1 1 i p p a a s j j j p c c c ₊ − = = +

∑

1 1 p p b b a j j p a c ₊ − = = +

∑

> ca; essendo ca ≠ si ha cb a c a b c a j ≠ j e quindi il

cammino non contiene cicli. La seconda osservazione è che se si effettuasse una colorazione dei vertici di G e si estendesse tale colorazione a , come effettuato per il caso di reti acicliche, il cammino sarebbe sicuramente non colorful in quanto i due nodi

(..., ca,..., cb...) U a a P = j j U G U P e a c a a b c

j j avrebbero lo stesso colore. La colorazione dei vertici di G

e la ricerca di un insieme colorful di k cammini che si effettuano nell’algoritmo, dun-que, oltre a garantire che i k cammini della soluzione siano node-disjoint, garantiscono anche che i cammini siano semplici anche nel caso in cui il problema sia stato formulato su grafi contenenti cicli. L’algoritmo descritto nel paragrafo 1.4.3.1 può quindi essere utilizzato per risolvere il problema dei cammini bilanciati node-disjoint su grafi conte-nenti cicli senza che sia necessario apportare alcuna modifica.

Come descritto nel capitolo precedente, nel primo passo dell’algoritmo, per poter co-struire la rete espansa GU =

(

VU,EU

)

, è necessario calcolare U, il costo del cammino

semplice più costoso in G. Nel caso in cui G contenga dei cicli è pertanto necessario ap-prossimare il valore di U. Tenendo presente che i cammini cercati devono essere

node-disjoint, una buona approssimazione per U è in questo caso

(

n−2k+1

)

c_max, dove

{

}

max max ij| ij

utiliz-mino semplice più costoso da s a t è proprio

(

n−2k+1

)

c_max. Istanze in cui ciò avviene sono ad esempio quelle in cui, nel grafo di input, esistono un nodo origine e un nodo de-stinazione, senza perdere di generalità siano essi e rispettivamente, per i quali gli unici cammini semplici che li connettono includono tutti i nodi in

1 s t₁

{

2 2

}

\ ,..., , ,...,_k V s s t t_k ⎤⎦

e contengono solo archi di costo . Il costo di ognuno di questi cammini è . Un’istanza di questo tipo è mostrata in Figura 5.

max c

(

n−2k+1

)

cmax Figura 5 1 s 2 s 3 s 4 s t₄ 3 t 2 t 1 t 1 2 3 m in

c

m ax

c

m ax

c

m ax

c

m ax

c

3 2 s t

c

2 3 s t

c

21 s

c

3 1

c

n = 11 m = 9 k = 4 U = 4c_max

Nell’algoritmo il valore di U viene utilizzato anche per stabilire l’estremo superiore dell’intervallo in cui effettuare la ricerca binaria descritta in 1.3.1. Tale estremo deve rappresentare il valore della funzione obiettivo nel caso pessimo, cioè quando la diffe-renza in costo tra il cammino più costoso e quello meno costoso in ogni insieme di k cammini ammissibili è la massima possibile. Più efficientemente, se indichiamo con

il costo del cammino di costo minimo dalla superorigine s alla superdestinazione t in G, individuabile in tempo polinomiale mediante un algoritmo di cammino minimo da

s a t [7], la ricerca binaria può essere effettuata nell’intervallo anziché

nell’intervallo min c min 0,U c ⎡ − ⎣

valore ottimo della funzione obiettivo è proprio min , con e U−c cmin =c_min

{

}

min min ij| ij c = c c ∈C k

)

n .

2.2 Una famiglia di algoritmi euristici

2.2.1 Approccio euristico

Quando si è valutata la complessità computazionale in tempo del procedimento descritto per il caso node-disjoint del problema, è stato messo in evidenza come sia possibile ot-tenere un algoritmo deterministico. Ciò che permette di avere un procedimento deter-ministico è la possibilità di generare una lista di colorazioni dei vertici del grafo di input con la seguente proprietà: per ogni sottoinsieme di V con # , la lista contiene una colorazione che assegna colori distinti ad ogni vertice in . Tale proprietà garanti-sce che la lista contenga almeno una colorazione corrispondente ad una soluzione ottima del problema. Per ottenere una soluzione ottima del problema, quindi, basta applicare il procedimento descritto per ognuna delle colorazioni nella lista, e restituire la soluzione migliore tra quelle individuate. Tuttavia, se si pensa all’implementazione di tale algo-ritmo deterministico e alla sua efficienza in pratica, si possono evidenziare due aspetti critici, soprattutto su istanze del problema di grandi dimensioni. Il primo aspetto riguar-da la lista delle colorazioni riguar-da analizzare: come descritto in [1], la cardinalità della lista è ; inoltre, l’individuazione delle colorazioni da inserire in tale lista è stata studiata da un punto di vista esclusivamente teorico, e risulta essere di non immediata attuazione in pratica. Il secondo aspetto riguarda sempre la lista delle colorazioni da a-nalizzare, e più precisamente il parametro h presente nella valutazione della cardinalità della lista. Nel caso di reti acicliche il parametro h indica il numero di livelli della rete in esame. Nel caso di grafi di input generici invece h, in quanto stima della massima lunghezza dei cammini dai nodi origine ai nodi destinazione, può essere .

' V V'≤h ' V

(

2 logkh O

( )

O n

Sulla base di queste osservazioni, si è pensato di progetttare il seguente approccio euri-stico:

• applicare l’algoritmo descritto per un numero di volte pari al numero di colora-zioni stabilito, effettuando ad ogni iterazione una colorazione dei vertici in mo-do ranmo-dom.

Chiaramente, il numero di colorazioni e il numero di colori da utilizzare devono essere stabiliti sulla base delle dimensioni del grafo di input, ma è difficile dare una valutazio-ne a priori di tali parametri. Per stabilire i valori ottimali dei parametri ci si è quindi fatti guidare da una fase di sperimentazione, i cui risultati sono riportati nei capitoli succes-sivi. Sono state comunque effettuate alcune valutazioni teoriche, le quali sono risultate essere d’aiuto per condurre la sperimentazione e per valutare l’errore relativo compiuto dall’approccio proposto. Tali valutazioni riguardano il numero di colorazioni utilizzabi-li, l’analisi di quante colorazioni siano equivalenti e lo studio della probabilità che, ef-fettuando le colorazioni in modo random, se ne ottengano due equivalenti.

2.2.2 Varianti dell’approccio euristico implementate

Nel software prodotto l’approccio euristico appena descritto è stato implementato in tre diverse versioni.

Nella prima versione dell’approccio euristico si impone un limite di un’ora alla ricerca dei cammini bilanciati e quindi, trascorsa un’ora dall’inizio della ricerca binaria, si arre-sta il processo di ricerca e si restituisce la miglior soluzione fino ad allora trovata (ver-sione con “time limit di un’ora”).

Nella seconda versione si procede nel seguente modo. Si supponga che siano trascorsi cinque minuti dal tempo in cui è stata individuata l’ultima soluzione ammissibile, e che l’euristica non abbia effettuato alcun miglioramento in questo lasso di tempo. Come conseguenza di tale comportamento, in questa seconda versione dell’approccio euristi-co, si assume che nell’intervallo corrente della ricerca binaria non esista alcuna soluzio-ne ammissibile e si interrompe la ricerca in tale intervallo. Si passa quindi ad effettuare la ricerca binaria nell’intervallo destro che la ricerca stessa indicherebbe come successi-vo qualora la non esistenza di una soluzione nell’intervallo corrente fosse stata accerta-ta. Nel nuovo intervallo la ricerca binaria procede in maniera regolare; tuttavia, se

tra-scorrono ulteriori cinque minuti senza trovare alcuna soluzione, l’euristica si arresta e restituisce la miglior soluzione trovata (versione “con blocchi di cinque minuti”).

La terza versione dell’approccio euristico implementata, versione “con scaling dei co-sti”, è la seguente. Fissato un parametro ε>0, si sostituisce il costo dell’arco cij

( )

,i j

con max ij c V c ε ⎡ # ⎤ × ⎢ ⎥

⎢ ⎥, ∀

( )

,i j arco del grafo, come descritto in [6], e si effettua la ricerca

dei cammini bilanciati utilizzando tali costi modificati. Una volta terminata la ricerca, si considerano i cammini generati e se ne calcola il costo rispetto ai costi originali, valu-tando la differenza in costo tra il cammino più costoso e quello meno costoso. In fase di sperimentazione, la versione è stata testata per valori di 1, ,1 3

2 2

ε_{∈ ⎨}⎧ ⎫_⎬

⎩ ⎭. Tale variante è stata ideata per tentare di ridurre le dimensioni del grafo espanso, riducendo quindi i tempi richiesti per effettuare la ricerca binaria.

2.3 Analisi delle colorazioni

2.3.1 Equivalenza tra colorazioni

Nell’algoritmo descritto, l’uso della tecnica della colorazione dei vertici di G=

(

V E,

)

,

e l’estensione della colorazione al grafo GU =

(

VU,EU

)

, serve per garantire che i

mini individuati siano node-disjoint, e ciò si ottiene imponendo che l’insieme dei cam-mini restituito sia colorful.

Sia l’insieme dei colori utilizzati e siano due colorazioni dei vertici di G.

Col r r V1, :2 →Col

Definizione: e sono equivalenti, se per ogni cammino in G, è colorful

ri-spetto ad se e solo se è colorful riri-spetto ad .

1

r r₂ P P

1

Sia G=

(

V E,

)

, con #V = n, il grafo di input e sia #Col= γ (con γ < ). Come intro-dotto precedentemente, una colorazione dei vertici di G può essere identificata mediante una funzione

n

:

r V →Col.

Le possibili colorazioni dei nodi di G, dunque, sono tante quante sono le funzioni da un insieme di n elementi ad un insieme di γ elementi, cioè γn

.

In base alla definizione di equivalenza appena introdotta, due colorazioni

1:

r V →Col ed r V₂: →Col

sono equivalenti se e solo se esiste un’applicazione biettiva λ tra r V₁

( )

e r V₂

( )

( )

( )

1 2

: r V r V

λ →

tale che r2 = o . Possiamo anche dire che ed sono equivalenti se e solo se utiliz-λ r1

zano uno stesso numero di colori

1

r r₂

ν e i colori

{

c₁,...,cv

}

utilizzati da e r1

{

d1,...,dv

}

da

possono essere ordinati in maniera tale che

2

r ∀ ∈j

{

1,...,ν

}

r11( )cj r21( )dj .

− ₌ −

Per capire meglio il concetto d’equivalenza tra due colorazioni mettiamo in evidenza due casi estremi:

• due qualsiasi colorazioni che utilizzano un solo colore sono equivalenti;

• due qualsiasi colorazioni che utilizzano un numero di colori pari al numero dei nodi sono tra loro equivalenti.

I colori sono di fatto utilizzati per generare una partizione dell’insieme dei nodi, e due colorazioni sono equivalenti se generano la stessa partizione.

2.3.2 Alcune stime probabilistiche

Data una colorazione r V1: →Col che utilizza ν γ≤ colori, il numero di colorazioni ad essa equivalenti è: ! ( 1)...( 1) γ ν γ γ γ ν ν ⎛ ⎞ = − − + ⎜ ⎟ ⎝ ⎠ .

Infatti, per costruire una colorazione equivalente ad , bisogna scegliere r2 r1 ν colori in , e ci sono Col γ ν ⎛ ⎞ ⎜ ⎟

⎝ ⎠ possibilità, e stabilire una biezione λ tra i ν colori usati da e i r1 ν colori usati da , e questo si può fare in r2 ν modi. Un’interessante formula combina-!

toria che consegue dai ragionamenti sopra riportati è la seguente:

1 ! n n γ ν ν γ ν γ ν = ⎛ ⎞ Π = ⎜ ⎟ ⎝ ⎠

∑

dove con n ν

Π denotiamo il numero di partizioni di un insieme di n elementi in ν sot-toinsiemi. Indicata con la cardinalità dell’i-esimo sottoinsieme della partizione, tale formula si può anche scrivere, esplicitando

i

b

n

ν

Π , nel seguente modo:

1 2 1 2 1 1 1 1 ... 1 2 0< ... ( ... ) ! ... n b b b n b b b n b b n n b b b b ν ν γ ν ν ν γ ν γ ν • − = + + + = ≤ ≤ ≤ − + + − ⎛ ⎞ ⎛ ⎞⎛ ⎞ ⎛ ⎞ = ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ⎝ ⎠⎝ ⎠ ⎝ ⎠

∑

∑

dove il • sulla sommatoria indica la seguente regola di calcolo: quando in una

decom-posizione di n alcuni degli addendi (necessariamente consecutivi) sono uguali l’addendo associato deve essere diviso per

1

< ... <

j j j p j p

b b₊ = =b₊ b_{+ +1} p . !

Si noti che il numero di colorazioni equivalenti ad una data non dipende dal numero di nodi n, ma solo da γ e dal numero di colori utilizzati ν .

Una volta stabilito il numero di colorazioni possibili ed il numero di colorazioni equiva-lenti ad una data, è facile vedere che, poiché nell’approccio euristico proposto le colora-zioni dei vertici vengono effettuate in modo random, data una colorazione

che usa

:

r V →Col ν colori, utilizzata durante l’esecuzione dell’algoritmo, ad ogni iterazione suc-cessiva la probabilità che l’algoritmo usi una colorazione equivalente ad r è

( 1)...( 1)

n

γ γ γ ν

γ

− − +

. Ora, invece, si supponga che nel corso delle prime p iterazioni dell’algoritmo siano state utilizzate p colorazioni , tra loro non equivalenti, e che tali colorazioni utilizzino, rispettivamente, un numero di colori pari a

1,..., p

r r

1,..., p

pro-babilità che alla -esima iterazione venga generata una colorazione r equivalente ad una delle precedenti è

(

p+1

)

1 ( 1)...( 1) ( 1)...( 1) ... p n n γ γ γ ν γ γ γ ν γ γ − − + − − + _{+ +} .

Durante la fase di sperimentazione, è estremamente importante valutare il tempo medio richiesto dall’algoritmo per una singola colorazione e valutare il tempo necessario per verificare se due colorazioni sono equivalenti. Fatto questo si può poi stabilire il numero di colorazioni che si vogliono utilizzare e si può valutare se l’algoritmo euristico sia più efficiente nel caso in cui usi solo colorazioni non equivalenti, o nel caso in cui non ef-fettui controlli sull’equivalenza delle colorazioni generate. Chiaramente, in questo se-condo caso, può accadere che l’algoritmo effettui alcune iterazioni “inutilmente”, per-ché eseguite con colorazioni equivalenti ad altre già utilizzate e che quindi non aggiun-gono nessuna nuova informazione. Può essere preferibile effettuare la scelta di non con-trollare l’equivalenza delle colorazioni, qualora questa operazione richieda più tempo che eseguire l’algoritmo per una singola colorazione, o qualora richieda un’eccessiva occupazione di memoria.

Considerazioni sperimentali relative al controllo sull’equivalenza delle colorazioni ge-nerate verranno riportate nel quarto capitolo.