30.7 Il problema del commesso viaggiatore: accodare o inserire?

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

• Per il TSP ogni permutazione delle città è un giro ammissibile, quindi il test di ammissibilità è banale, e tutto il progetto sta nel criterio di selezione. Due famiglie di euristiche costruttive sono naturali, e differiscono per dove si colloca la nuova città:

  • accodare: la soluzione parziale è un cammino, e la nuova città si aggiunge alla sua fine;

  • inserire: la soluzione parziale è un sottogiro chiuso, e la nuova città si inserisce fra due città consecutive, dove costa meno.

30.7.1 Nearest neighbour

Il Nearest Neighbour Algorithm (indicato con \(NN\)) è un'euristica costruttiva per il TSP. Partendo da una città data \(s\), si sposta ripetutamente dall'ultima città visitata alla città più vicina non ancora visitata (in caso di pareggio, quella con l'indice minimo); quando tutte le città sono state visitate, torna in \(s\).

Algoritmo: 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 NearestNeighbour(\(n, d, s\))

2\(\sigma[1] \leftarrow s\) \(visited := \{s\}\) ▹ il cammino parte da \(s\)

3for \(len := 2\) to \(n\) do

4\(last := \sigma[len-1]\) \(k :=\) la città \(j\notin visited\) con \(d[last][j]\) minimo (indice minimo) ▹ ultima città del cammino

5\(\sigma[len] \leftarrow k\) \(visited \leftarrow visited \cup \{k\}\) ▹ accodare \(k\) alla fine

6end

7return \(\sigma\) ▹ il giro si chiude con l'arco \((\sigma[n],s)\)

Esegui in Colab:PythonC++

• Il criterio è dinamico: le distanze che contano sono quelle dall'ultima città, che cambia a ogni passo. \(NN\) richiede tempo \(O(n^2)\).

• La debolezza di \(NN\) si vede nei suoi ultimi passi: le città rimaste sono quelle che non sono mai state le più vicine a niente, spesso lontane fra loro e da \(s\), e l'arco di chiusura verso \(s\) non viene scelto affatto, è forzato.

Esempio 30.7: \(NN\) sull'istanza di riferimento del TSP

Partendo dalla città \(1\):

1. dalla città \(1\) le distanze verso \(2,3,4,5\) sono \(5,2,2,9\): le città \(3\) e \(4\) sono le più vicine, e il pareggio si risolve a favore della città \(3\);

2. dalla città \(3\) le distanze verso \(2,4,5\) sono \(4,4,7\): città \(2\) (pareggio con \(4\));

3. dalla città \(2\) le distanze verso \(4,5\) sono \(3,4\): città \(4\);

4. dalla città \(4\) resta solo la città \(5\), a distanza \(7\);

5. il giro si chiude con l'arco \((5,1)\), di lunghezza \(9\).

Quindi \(\sigma=(1,3,2,4,5)\) e

\[ NN(I)=d_{13}+d_{32}+d_{24}+d_{45}+d_{51}=2+4+3+7+9=25 , \]

il \(39\%\) in più di \(z(I)=18\); è il giro usato nel capitolo «Algoritmi euristici: definizioni» per illustrare il gap. I quattro archi scelti dal criterio hanno lunghezza \(2+4+3+7=16\), e il solo arco di chiusura forzato costa \(9\), la distanza più grande dell'istanza.

30.7.2 Nearest neighbour multi-start

• Il risultato di \(NN\) dipende dalla città di partenza, che è una scelta arbitraria: il giro è un ciclo e non ha una prima città naturale. Poiché \(NN\) è veloce, lo si può semplicemente eseguire da ogni città.

L'algoritmo nearest neighbour multi-start esegue \(NN\) una volta da ogni città \(s\in\mathscr{V}\) e restituisce il più corto degli \(n\) giri ottenuti (in caso di pareggio, il primo trovato).

Algoritmo: Nearest Neighbour multi-start

Input: istanza del TSP con \(n\) città, distanze \(d[1..n][1..n]\)

Output: giro \(\sigma^{best}[1..n]\)

1Function MultiStartNN(\(n, d\))

2\(L^{best} := +\infty\)

3for \(s := 1\) to \(n\) do

4\(\sigma :=\) NearestNeighbour(\(n, d, s\))

5if \(L(\sigma) < L^{best}\) then

6\(\sigma^{best} \leftarrow \sigma\), \(L^{best} \leftarrow L(\sigma)\) ▹ nuovo giro migliore

7end

8end

9return \(\sigma^{best}\)

Esegui in Colab:PythonC++

• Il tempo di esecuzione è \(n\) volte quello di \(NN\), cioè \(O(n^3)\). Il multi-start è il modo più semplice di trasformare una scelta arbitraria in una ricerca: ogni partenza dà una soluzione diversa, e si tiene la migliore.

Esempio 30.8: \(NN\) multi-start sull'istanza di riferimento del TSP

Le cinque esecuzioni di \(NN\) danno

partenza \(s\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)
giro	\((1,3,2,4,5)\)	\((2,4,1,3,5)\)	\((3,1,4,2,5)\)	\((4,1,3,2,5)\)	\((5,2,4,1,3)\)
\(L\)	\(25\)	\(18\)	\(18\)	\(19\)	\(18\)

I giri dalle città \(2\), \(3\) e \(5\) sono il giro ottimo \((1,3,5,2,4)\), percorso da città diverse e in versi diversi; il multi-start restituisce il giro dalla città \(2\), di lunghezza \(18=z(I)\).

30.7.3 Euristiche di inserimento

• \(NN\) può solo aggiungere una città alla fine di un cammino. Un'euristica di inserimento mantiene un sottogiro chiuso \(T\) attraverso alcune delle città, e inserisce la nuova città dove costa meno. Inserire la città \(k\) fra due città consecutive \(i\) e \(j\) di \(T\) sostituisce l'arco \((i,j)\) con gli archi \((i,k)\) e \((k,j)\), e aumenta la lunghezza del costo di inserimento

\[ \Delta(i,k,j) \;=\; d_{ik} + d_{kj} - d_{ij} \qquad \text{per ogni arco } (i,j) \text{ del sottogiro } T . \]

Sulle istanze metriche \(\Delta(i,k,j)\ge 0\), per la disuguaglianza triangolare.

• Ogni passo prende due decisioni: quale città si inserisce (la regola di selezione) e dove (sempre l'arco di costo di inserimento minimo). Le tre euristiche classiche differiscono solo per la regola di selezione. Sia \(d(q,T)=\min_{i\in T} d_{qi}\) la distanza della città \(q\) dal sottogiro.

Le euristiche di inserimento per il TSP partono dal sottogiro \(T=(s)\) e, finché tutte le città non sono in \(T\), selezionano una città \(k\notin T\) e la inseriscono nell'arco di \(T\) di costo di inserimento minimo:

nearest insertion (\(NI\)):	\(k\) minimizza \(d(q,T)\), la distanza dal sottogiro
farthest insertion (\(FI\)):	\(k\) massimizza \(d(q,T)\)
cheapest insertion (\(CI\)):	\(k\) minimizza \(\min\limits_{(i,j)\in T}\Delta(i,q,j)\), il costo del suo inserimento

I pareggi si risolvono a favore dell'indice minimo, per la città e per l'arco.

Algoritmo: Inserimento (NI, FI, CI)

Input: istanza del TSP con \(n\) città, distanze \(d[1..n][1..n]\); città di partenza \(s\); \(rule\in\{NI,FI,CI\}\)

Output: giro \(\sigma[1..n]\)

1Function Insertion(\(n, d, s, rule\))

2\(\sigma := (s)\) ▹ sottogiro con una città

3for \(len := 1\) to \(n-1\) do

4\(k :=\) la città \(q\notin\sigma\) selezionata da \(rule\) \(a :=\) la posizione \(a\in\{1,\dots,len\}\) che minimizza \(\Delta(\sigma[a],k,\sigma[a+1])\), con \(\sigma[len+1]=\sigma[1]\) inserire \(k\) fra \(\sigma[a]\) e \(\sigma[a+1]\) ▹ quale città dove

5end

6return \(\sigma\)

Esegui in Colab:PythonC++

• Il sottogiro con una città. Il sottogiro \((s)\) è un giro chiuso con un solo “arco” \((s,s)\) di lunghezza \(0\), quindi inserire \(k\) costa \(d_{sk}+d_{ks}-0=2d_{sk}\), e il sottogiro \((s,k)\) va da \(s\) a \(k\) e ritorno. Non serve alcun caso particolare.

• Accodare o inserire. Ogni giro costruito da \(NN\) potrebbe essere costruito anche da un'euristica di inserimento, ma non viceversa: inserire in qualunque posizione mantiene il sottogiro chiuso a ogni passo, quindi la lunghezza dell'arco di chiusura si paga, e si controlla, fin dall'inizio.

• L'intuizione dietro FI. Prendere la città più lontana sembra assurdo per un algoritmo greedy, ma così si costruisce prima il contorno del giro, attraverso le città lontane fra loro, e poi si inseriscono le città rimanenti, che sono “di strada” e costano poco.

• Con le distanze \(d(q,T)\) e i costi di inserimento minimi aggiornati in modo incrementale dopo ogni inserimento, \(NI\) e \(FI\) richiedono tempo \(O(n^2)\); un'implementazione semplice di \(CI\) richiede tempo \(O(n^3)\).

Esempio 30.9: \(NI\) e \(CI\) sull'istanza di riferimento del TSP

Partiamo da \(T=(1)\). A ogni passo elenchiamo, per ogni città \(q\notin T\), la sua distanza \(d(q,T)\) e i suoi costi di inserimento sugli archi di \(T\), nell'ordine di \(T\).

sottogiro \(T\)	\(d(q,T)\)	costi di inserimento	inserita
\((1)\)	\(2{:}\,5,\ 3{:}\,2,\ 4{:}\,2,\ 5{:}\,9\)	\(2{:}\,10,\ 3{:}\,4,\ 4{:}\,4,\ 5{:}\,18\)	\(3\) su \((1,1)\), costo \(4\)
\((1,3)\)	\(2{:}\,4,\ 4{:}\,2,\ 5{:}\,7\)	\(2{:}\,(7,7),\ 4{:}\,(4,4),\ 5{:}\,(14,14)\)	\(4\) su \((1,3)\), costo \(4\)
\((1,4,3)\)	\(2{:}\,3,\ 5{:}\,7\)	\(2{:}\,(6,3,7),\ 5{:}\,(14,10,14)\)	\(2\) su \((4,3)\), costo \(3\)
\((1,4,2,3)\)	\(5{:}\,4\)	\(5{:}\,(14,8,7,14)\)	\(5\) su \((2,3)\), costo \(7\)

\(NI\) seleziona la città con la \(d(q,T)\) minima, \(CI\) la città con il costo di inserimento minimo: su questa istanza le due regole selezionano le stesse città a ogni passo (la città \(3\) al primo passo per il pareggio con la città \(4\)). Entrambe restituiscono \(\sigma=(1,4,2,5,3)\), e

\[ NI(I)=CI(I)=4+4+3+7=18=z(I), \]

il giro ottimo \((1,3,5,2,4)\) percorso nel verso opposto. I sottogiri crescono come segue (nuovi archi in rosso):

Esempio 30.10: \(FI\) sull'istanza di riferimento del TSP

Partiamo da \(T=(1)\):

sottogiro \(T\)	\(d(q,T)\)	costi di inserimento della città selezionata	inserita
\((1)\)	\(2{:}\,5,\ 3{:}\,2,\ 4{:}\,2,\ 5{:}\,9\)	\(5{:}\,18\)	\(5\) su \((1,1)\), costo \(18\)
\((1,5)\)	\(2{:}\,4,\ 3{:}\,2,\ 4{:}\,2\)	\(2{:}\,(0,0)\)	\(2\) su \((1,5)\), costo \(0\)
\((1,2,5)\)	\(3{:}\,2,\ 4{:}\,2\)	\(3{:}\,(1,7,0)\)	\(3\) su \((5,1)\), costo \(0\)
\((1,2,5,3)\)	\(4{:}\,2\)	\(4{:}\,(0,6,4,4)\)	\(4\) su \((1,2)\), costo \(0\)

Al primo passo \(FI\) prende la città \(5\), la più lontana dalla città \(1\), e il sottogiro \((1,5)\) ha già lunghezza \(2d_{15}=18\). Le città \(2\), \(3\) e \(4\) sono “di strada” e si inseriscono a costo zero, perché \(d_{12}+d_{25}=d_{15}\), \(d_{53}+d_{31}=d_{51}\) e \(d_{14}+d_{42}=d_{12}\). Quindi \(\sigma=(1,4,2,5,3)\) e \(FI(I)=18=z(I)\): lo stesso giro di \(NI\) e \(CI\), costruito in un ordine completamente diverso.

• Che cosa si sa nel caso peggiore. Sulle istanze metriche, \(NI\) e \(CI\) non restituiscono mai un giro più lungo del doppio di quello ottimo, mentre il rapporto di \(NN\) può crescere come \(\log n\) e per \(FI\) è noto solo un bound logaritmico (D.J. Rosenkrantz, R.E. Stearns, P.M. Lewis, An analysis of several heuristics for the traveling salesman problem, SIAM Journal on Computing 6 (1977) 563–581). In pratica, sulle istanze euclidee, \(FI\) è di solito la migliore delle euristiche di inserimento, e i giri di \(NN\) sono tipicamente circa il \(25\%\) più lunghi dell'ottimo.

30.7.4 Un confronto su un'istanza più grande

• Sull'istanza di riferimento le tre euristiche di inserimento, da ogni città di partenza, trovano tutte il giro ottimo, e le differenze fra le regole non si vedono. Per confrontarle usiamo una seconda istanza del TSP, con \(6\) città nel piano e distanze uguali alle distanze euclidee arrotondate all'intero più vicino. L'istanza è metrica (verificato su tutte le terne di città).

Esempio 30.11: Un'istanza del TSP con \(6\) città

Le città hanno coordinate

\[ 1{:}\,(2,1),\quad 2{:}\,(5,5),\quad 3{:}\,(4,4),\quad 4{:}\,(0,5),\quad 5{:}\,(7,0),\quad 6{:}\,(4,1), \]

e distanze

\[ \begin{array}{c|cccccc} \hline {d_{ij}} & {1} & {2} & {3} & {4} & {5} & {6} \\ \hline {1} & --- & {5} & {4} & {4} & {5} & {2} \\ {2} & {5} & --- & {1} & {5} & {5} & {4} \\ {3} & {4} & {1} & --- & {4} & {5} & {3} \\ {4} & {4} & {5} & {4} & --- & {9} & {6} \\ {5} & {5} & {5} & {5} & {9} & --- & {3} \\ {6} & {2} & {4} & {3} & {6} & {3} & --- \\ \hline \end{array} \]

L'istanza ha \(\frac{5!}{2}=60\) giri distinti; enumerandoli, l'unico giro ottimo è \((1,4,3,2,5,6)\), con \(z(I)=19\), e solo \(7\) giri hanno lunghezza minore di \(24\). Le euristiche di questa sezione danno:

	città di partenza
	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)
\(NN\)	\(25\)	\(24\)	\(25\)	\(24\)	\(24\)	\(24\)

dalla città \(1\)	\(L\)
\(NI\)	\(23\)
\(FI\)	\(19\)
\(CI\)	\(20\)

Il giro migliore del \(NN\) multi-start ha lunghezza \(24\), il \(26\%\) sopra l'ottimo, mentre \(FI\) trova il giro ottimo \((1,6,5,2,3,4)\) (il giro ottimo nel verso opposto):

Tutti e sei i giri di \(NN\) contengono l'arco \((4,5)\), di lunghezza \(9\), il più lungo dell'istanza: le città \(4\) e \(5\) sono agli estremi opposti dell'istanza, e \(NN\), da qualunque città parta, lascia almeno una delle due agli ultimi passi, quando l'unica strada rimasta è quella lunga.

---

Avanti: 30.8 Colorazione dei vertici: greedy e DSATUR