Vai al contenuto

30.10 Look-ahead e regret

Parte 4 · Algoritmi euristici · Capitolo 30 · Capitolo 30: Euristiche costruttive · Dispensa, volume 4 (PDF) · Slide (1/2) · Slide (2/2) · Esercizi: Euristiche costruttive · App: Euristiche per il bin packing · App: List scheduling e LPT · App: Colorazione: greedy e DSATUR · App: TSP: nearest neighbour e 2-opt

  • Un criterio greedy chiede: quale scelta è la migliore adesso? La sua miopia si può ridurre ponendo due domande diverse:

    • regret: che cosa perdo se rimando questa scelta? Un elemento che ha una sola buona opzione va servito prima che la perda; un elemento con molte opzioni equivalenti può aspettare;

    • look-ahead: dove porta questa scelta? Ogni candidato si valuta completando la soluzione parziale con un'euristica veloce, e si sceglie il candidato con la migliore soluzione completata.

    Entrambe le idee costano più tempo per passo del semplice criterio greedy, ed entrambe mantengono la caratteristica essenziale di un'euristica costruttiva: la scelta fatta è definitiva.

30.10.1 Inserimento con regret

  • Per un'euristica di inserimento, siano \(\Delta^{1}_q\le\Delta^{2}_q\) i due costi di inserimento minimi della città \(q\) sugli archi del sottogiro corrente (con \(\Delta^2_q=\Delta^1_q\) se il sottogiro ha un solo arco). Il regret di \(q\) è
\[ reg_q \;=\; \Delta^{2}_q - \Delta^{1}_q \;\ge\; 0 : \]

il costo aggiuntivo pagato per \(q\) se il suo arco migliore viene usato da un'altra città prima che \(q\) sia inserita.

L'algoritmo di inserimento regret-2 (indicato con \(REG_2\)) è un'euristica costruttiva per il TSP. Partendo dal sottogiro \((s)\), a ogni passo inserisce la città con il regret massimo, in caso di pareggio quella con \(\Delta^1_q\) minimo e poi con l'indice minimo, nel suo arco di costo di inserimento minimo.

Algoritmo: Inserimento regret-2

Input: istanza del TSP con \(n\) città, distanze \(d[1..n][1..n]\); città di partenza \(s\)
Output: giro \(\sigma[1..n]\)
1Function Regret2Insertion(\(n, d, s\))
2\(\sigma := (s)\)
3for \(len := 1\) to \(n-1\) do
4for each città \(q\notin\sigma\) do
5\(\Delta^1_q, \Delta^2_q :=\) i due valori minimi di \(\Delta(\sigma[a],q,\sigma[a+1])\), \(a=1,\dots,len\)
6\(reg_q := \Delta^2_q-\Delta^1_q\) ▹ regret di \(q\)
7end
8\(k :=\) la città con \(reg_q\) massimo (pareggi: \(\Delta^1_q\) minimo, poi indice minimo)
9inserire \(k\) nel suo arco di costo di inserimento minimo
10end
11return \(\sigma\)

Esegui in Colab:PythonC++

  • Le euristiche regret-\(k\) generalizzano l'idea, sommando le differenze fra l'opzione migliore e le \(k-1\) successive; sono molto usate per i problemi di vehicle routing, dove un cliente può avere una sola route ammissibile rimasta (J.-Y. Potvin, J.-M. Rousseau, A parallel route building algorithm for the vehicle routing and scheduling problem with time windows, European Journal of Operational Research 66 (1993) 331–340). La stessa idea si applica a qualunque costruzione di tipo assegnamento, come oggetti a contenitori.

  • Finché tutti i regret sono \(0\), la regola di risoluzione dei pareggi fa comportare \(REG_2\) come \(CI\).

Esempio 30.16: \(REG_2\) contro \(CI\) sull'istanza con \(6\) città

Sull'istanza dell'Esempio 30.11, dalla città \(1\). Nei primi due passi tutti i regret sono \(0\) (i sottogiri \((1)\) e \((1,6)\) hanno un arco, o due copie dello stesso arco), e sia \(REG_2\) sia \(CI\) inseriscono la città \(6\) (costo \(4\)) e poi la città \(3\) (costo \(5\)), ottenendo \((1,3,6)\) di lunghezza \(9\). Al terzo passo i costi di inserimento sugli archi \((1,3)\), \((3,6)\), \((6,1)\) sono

città \(q\) costi \(\Delta^1_q\) \(\Delta^2_q\) \(reg_q\)
\(2\) \((2,2,7)\) \(2\) \(2\) \(0\)
\(4\) \((4,7,8)\) \(4\) \(7\) \(3\)
\(5\) \((6,5,6)\) \(5\) \(6\) \(1\)

\(CI\) inserisce la città \(2\), la più economica, sull'arco \((1,3)\). \(REG_2\) inserisce la città \(4\), quella con il regret massimo, sull'arco \((1,3)\): questo arco è l'unica buona posizione per la città \(4\), mentre la città \(2\) ha due posizioni ugualmente buone e può aspettare. Le due costruzioni proseguono poi così:

\(CI\) \(REG_2\)
passo 3 \(2\) su \((1,3)\), costo \(2\): \((1,2,3,6)\) \(4\) su \((1,3)\), costo \(4\): \((1,4,3,6)\)
passo 4 \(4\) su \((1,2)\), costo \(4\): \((1,4,2,3,6)\) \(5\) su \((3,6)\), costo \(5\): \((1,4,3,5,6)\)
passo 5 \(5\) su \((3,6)\), costo \(5\): \((1,4,2,3,5,6)\) \(2\) su \((3,5)\), costo \(1\): \((1,4,3,2,5,6)\)
lunghezza \(4+5+2+4+5=20\) \(4+5+4+5+1=19\)

Al passo \(4\) di \(REG_2\) i costi della città \(2\) sugli archi di \((1,4,3,6)\) sono \((6,2,2,7)\), regret \(0\), e quelli della città \(5\) sono \((10,10,5,6)\), regret \(1\): la città \(5\) passa prima. La città \(2\), rimandata due volte, si inserisce infine per \(1\) invece che per \(2\), fra le città \(3\) e \(5\). \(REG_2(I)=19=z(I)\), mentre \(CI(I)=20\).

30.10.2 Look-ahead: il metodo pilota

Il metodo pilota trasforma un'euristica costruttiva \(\mathscr{H}\), il pilota, in un'euristica più forte. A ogni passo prova ogni candidato: la soluzione parziale estesa con il candidato viene completata da \(\mathscr{H}\), e il candidato la cui soluzione completata è la migliore si aggiunge in modo definitivo. Con \(NN\) come pilota (indicato con \(PILOT\)-\(NN\)), i candidati sono le città successive del giro.

Algoritmo: Metodo pilota con nearest neighbour

Input: istanza del TSP con \(n\) città, distanze \(d[1..n][1..n]\); città di partenza \(s\)
Output: giro \(\sigma[1..n]\)
1Function PilotNN(\(n, d, s\))
2\(\sigma := (s)\)
3for \(len := 2\) to \(n\) do
4for each città \(q\notin\sigma\) do
5\(\tau_q :=\) il cammino \(\sigma\) esteso con \(q\) e completato da \(NN\) ▹ guardare avanti
6end
7\(k :=\) la città \(q\) con \(L(\tau_q)\) minimo (indice minimo)
8accodare \(k\) a \(\sigma\) ▹ la scelta è definitiva
9end
10return \(\sigma\)

Esegui in Colab:PythonC++

  • Il metodo pilota è dovuto a C. Duin e S. Voß (The pilot method: a strategy for heuristic repetition with application to the Steiner problem in graphs, Networks 34 (1999) 181–191). Ogni passo esegue il pilota una volta per candidato: con \(NN\) come pilota il tempo di esecuzione è \(O(n^4)\) invece di \(O(n^2)\).

  • Il metodo pilota non è mai peggiore del suo pilota. Al primo passo, il candidato scelto da \(NN\) è fra quelli provati, e il suo completamento è il giro di \(NN\) da \(s\), quindi il miglior completamento trovato ha lunghezza al più \(NN(I)\). A ogni passo successivo, il completamento del candidato scelto è di nuovo fra i completamenti provati al passo seguente (il candidato che \(NN\) accoderebbe), quindi la lunghezza del miglior completamento non aumenta mai. Il giro finale è l'ultimo completamento, quindi \(PILOT\)-\(NN(I)\le NN(I)\) dalla stessa città di partenza.

Esempio 30.17: \(PILOT\)-\(NN\) sull'istanza di riferimento del TSP

Dalla città \(1\), i candidati e i loro completamenti con \(NN\) sono:

cammino parziale candidati: giro completato e lunghezza scelta
\((1)\) \(2\): \((1,2,4,3,5)\) \(28\); \(3\): \((1,3,2,4,5)\) \(25\); \(4\): \((1,4,2,3,5)\) \(25\); \(5\): \((1,5,2,4,3)\) \(22\) \(5\)
\((1,5)\) \(2\): \((1,5,2,4,3)\) \(22\); \(3\): \((1,5,3,2,4)\) \(25\); \(4\): \((1,5,4,2,3)\) \(25\) \(2\)
\((1,5,2)\) \(3\): \((1,5,2,3,4)\) \(23\); \(4\): \((1,5,2,4,3)\) \(22\) \(4\)
\((1,5,2,4)\) \(3\): \((1,5,2,4,3)\) \(22\) \(3\)

\(PILOT\)-\(NN\) va prima nella città \(5\), la più lontana dalla città \(1\), cosa che \(NN\) non farebbe mai, e restituisce \((1,5,2,4,3)\) con \(L=9+4+3+4+2=22\), contro \(NN(I)=25\) dalla stessa città. L'ottimo \(18\) non si raggiunge: il look-ahead è buono solo quanto il pilota che lo esegue. Sull'istanza con \(6\) città dell'Esempio 30.11, \(PILOT\)-\(NN\) dalla città \(1\) dà \(20\), contro \(25\) per \(NN\).

Avanti: 30.11 Che cosa danno le euristiche costruttive, e che cosa non danno