PD per il problema dello zaino con setup¶

Parte 3 · Programmazione dinamica · Capitolo 23 · Dispensa, volume 3 (PDF) · Slide · Esercizi: Zaino con setup (KPS)

Prerequisiti

Da questo modulo, il capitolo «PD per il problema dello zaino 0/1»: la ricorrenza $v(j,k)$ del problema dello zaino 0/1 (KP) su oggetti e capacità, la matrice $s$ delle decisioni e la ricostruzione di una soluzione.
Da questo modulo, il capitolo «Problemi di zaino»: il problema dello zaino con setup, le sue classi, i costi di setup $f_h$ e i pesi di setup $s_h$.
Dal modulo Algoritmi: le convenzioni dello pseudocodice (Capitolo 2) e la dimensione dell'input (Capitolo 11).

Obiettivi

Al termine di questo capitolo saremo in grado di:

scrivere la ricorrenza del KPS: per ogni classe, il valore migliore senza aprirla e il valore migliore dopo averne pagato il setup;
eseguire a mano l'algoritmo di PD, classe per classe, con una ricorrenza del KP dentro ogni classe aperta;
ricostruire una soluzione ottima dalle tabelle delle scelte $s$ e $o$;
contare i $\Theta(nc)$ passi dell'algoritmo di PD.

Il problema di questo capitolo è il problema dello zaino con setup (KPS): la sua definizione e le sue ipotesi sono nella sua pagina.

23.1 Un algoritmo di PD¶

Numeriamo gli oggetti classe per classe, in modo che $\mathscr{J}_h=\{\ell_{h-1}+1,\dots,\ell_h\}$ per ogni classe $h$, con $\ell_0=0$ e $\ell_q=n$. La classe $h$ ha $t_h=|\mathscr{J}_h|=\ell_h-\ell_{h-1}$ oggetti, e il suo $i$-esimo oggetto è $j=\ell_{h-1}+i$.
Una soluzione si descrive con il vettore binario $(x_1,x_2,\dots,x_n)$. La classe $h$ è aperta se almeno uno dei suoi oggetti è selezionato: allora il suo peso di setup $s_h$ si aggiunge al peso totale, e il suo costo di setup $f_h$ si sottrae dal ricavo totale.

Esempio 23.1: Istanza del KPS

Consideriamo uno zaino di capacità $c=10$ e un insieme $\mathscr{I}=\{1,2,\dots,5\}$ di $5$ oggetti ($n=5$), partizionato in $q=2$ classi: $\mathscr{J}_1=\{1,2\}$, con costo di setup $f_1=2$ e peso di setup $s_1=2$, e $\mathscr{J}_2=\{3,4,5\}$, con costo di setup $f_2=3$ e peso di setup $s_2=1$. I ricavi e i pesi sono:

\[ \begin{array}{l|rr|rrr} \hline & {j=1} & {j=2} & {j=3} & {j=4} & {j=5} \\ \hline {p_j} & 6 & 5 & 4 & 7 & 3 \\ {w_j} & 3 & 2 & 2 & 4 & 1 \\ \hline \end{array} \]

Chiamiamo questa istanza del KPS Esempio 23.1.

Passo 1: calcolo del valore ottimo
- Le classi sono gli stadi dell'algoritmo di PD. Per ogni classe $h$ ci sono due opzioni: la classe $h$ resta chiusa, oppure la classe $h$ viene aperta, se ne paga il setup e si selezionano alcuni dei suoi oggetti.
- Dentro una classe aperta, la scelta degli oggetti è un KP: l'algoritmo di PD del KP scorre gli oggetti della classe, partendo dal valore rimasto dopo aver pagato il setup.
Per ogni $h \in \{0,1,\dots,q\}$ e $k \in \{0,1,\dots,c\}$, sia $v(h,k)$ il valore ottimo della sottoistanza del KPS con capacità $k$ e le classi $\mathscr{J}_1,\dots,\mathscr{J}_h$. Per ogni $h \in \{1,\dots,q\}$ e $i \in \{0,1,\dots,t_h\}$, sia $u(h,i,k)$ il valore ottimo della stessa sottoistanza quando la classe $h$ è aperta (il suo setup è pagato) e sono disponibili solo i suoi primi $i$ oggetti, con $u(h,i,k)=-\infty$ se il peso di setup non entra nello zaino.

Le formule ricorsive per calcolare $u(h,i,k)$ e $v(h,k)$ sono le seguenti, dove $j=\ell_{h-1}+i$ è l'$i$-esimo oggetto della classe $h$:

\[\begin{equation*} \label{eq:kpsu} u(h,i,k)= \left\{ \begin{array}{ll} -\infty & \textrm{se $i=0$ e $k<s_h$,}\\[2ex] v(h-1,k-s_h)-f_h & \textrm{se $i=0$ e $k\ge s_h$,}\\[2ex] u(h,i-1,k) & \textrm{se $i\ge 1$ e $w_j>k$,}\\[2ex] \begin{array}[t]{@{}l@{}}\displaystyle \max \bigg\{ u(h,i-1,k),\\ \qquad p_j+u(h,i-1,k-w_j) \bigg\}\end{array} & \textrm{se $i\ge 1$ e $w_j\le k$,} \end{array} \right. \tag{23.1} \end{equation*}\]

\[\begin{equation*} \label{eq:kpsv} v(h,k)= \left\{ \begin{array}{ll} 0 & \textrm{se $h=0$,}\\[2ex] \max \big\{ v(h-1,k),\; u(h,t_h,k) \big\} & \textrm{se $h\ge 1$.} \end{array} \right. \tag{23.2} \end{equation*}\]
- La riga $u(h,0,\cdot)$ paga il setup della classe $h$: il peso di setup $s_h$ lascia la capacità $k-s_h$ alle classi $1,2,\dots,h-1$, e il costo di setup $f_h$ viene sottratto.
- Le righe $u(h,1,\cdot),\dots,u(h,t_h,\cdot)$ sono la ricorrenza del KP sugli oggetti della classe $h$, con $-\infty+p_j=-\infty$.
- La formula $\eqref{eq:kpsv}$ confronta le due opzioni per la classe $h$: chiusa, con valore $v(h-1,k)$, oppure aperta, con valore $u(h,t_h,k)$.
- La riga $u(h,0,\cdot)$ ammette una classe aperta senza oggetti selezionati, che non è una soluzione del KPS. Questo valore non viene mai scelto in $\eqref{eq:kpsv}$, perché $f_h\ge 1$ dà
  
  \[ v(h-1,k-s_h)-f_h\;<\;v(h-1,k). \]
  
  Quindi, quando il massimo in $\eqref{eq:kpsv}$ è raggiunto solo da $u(h,t_h,k)$, almeno un oggetto della classe $h$ è selezionato.
- Una soluzione ottima per $(h,k)$ si costruisce da una soluzione ottima di una sottoistanza più piccola: $(h-1,k)$ se la classe $h$ è chiusa e, dentro una classe aperta, $(h,i-1,\cdot)$ con o senza l'oggetto $j$.
  
  $\rightsquigarrow$ Sottostruttura ottima verificata!
- Decisioni diverse sulle classi $h+1,\dots,q$ possono lasciare la stessa capacità $k$, e quindi lo stesso valore $v(h,k)$ può servire più volte.
  
  $\rightsquigarrow$ Sottoproblemi sovrapposti verificati!
- L'approccio bottom-up calcola, per $h=1,2,\dots,q$, prima le righe $u(h,i,\cdot)$ per $i=0,1,\dots,t_h$, e poi la riga $v(h,\cdot)$, ciascuna per $k$ crescente. Il valore ottimo dell'istanza del KPS è $v(q,c)$.

Passo 2: calcolo di una soluzione ottima

Si memorizzano due tabelle delle scelte: $s[h][i][k]=1$ se l'$i$-esimo oggetto della classe $h$ è selezionato nel valore ottimo $u[h][i][k]$, e $o[h][k]=1$ se la classe $h$ è aperta nel valore ottimo $v[h][k]$.
Il peso di setup $s_h$ ha un indice; la scelta $s[h][i][k]$ ne ha tre.

Questo è lo pseudocodice dell'algoritmo di PD con l'approccio bottom-up, che memorizza le tabelle delle scelte insieme ai valori:

Algoritmo: KPS_DP

Input: Un'istanza del KPS data da $q$, dalle classi $\mathscr{J}_1,\dots,\mathscr{J}_q$ numerate come sopra, dai costi di setup $f_h$ e dai pesi di setup $s_h$, dai vettori $p[1..n]$, $w[1..n]$ e dalla capacità $c$

Output: Il valore ottimo dell'istanza del KPS e le tabelle delle scelte $s$ e $o$

1Function KPS_DP($q,\mathscr{J},p,w,c$)

2$v,o := \textnormal{new arrays}[0..q][0..c]$; $u,s := \textnormal{new arrays}[1..q][0..t_h][0..c]$

3for $k := 0$ to $c$ do

4$v[0][k] \leftarrow 0$; $o[0][k] \leftarrow 0$

5end

6for $h := 1$ to $q$ do

7for $k := 0$ to $c$ do

8$u[h][0][k] \leftarrow -\infty$

9if $k\ge s_h$ then

10$u[h][0][k] \leftarrow v[h-1][k-s_h]-f_h$

11end

12end

13for $i := 1$ to $t_h$ do

14$j := \ell_{h-1}+i$

15for $k := 0$ to $c$ do

16$u[h][i][k] \leftarrow u[h][i-1][k]$; $s[h][i][k] \leftarrow 0$

17if $w[j]\le k$ e $p[j]+u[h][i-1][k-w[j]] > u[h][i][k]$ then

18$u[h][i][k] \leftarrow p[j]+u[h][i-1][k-w[j]]$; $s[h][i][k] \leftarrow 1$

19end

20end

21end

22for $k := 0$ to $c$ do

23$v[h][k] \leftarrow v[h-1][k]$; $o[h][k] \leftarrow 0$

24if $u[h][t_h][k] > v[h][k]$ then

25$v[h][k] \leftarrow u[h][t_h][k]$; $o[h][k] \leftarrow 1$

26end

27end

28end

29return $v[q][c], s, o$

Per ogni classe, il primo ciclo su $k$ paga il setup dove entra nello zaino, i cicli su $i$ e $k$ eseguono l'algoritmo di PD del KP sugli oggetti della classe, e l'ultimo ciclo su $k$ confronta la classe chiusa con quella aperta.
In caso di pareggio l'oggetto non viene selezionato e la classe resta chiusa, perché i valori vengono aggiornati solo quando sono strettamente maggiori.

Esempio 23.2: Esecuzione dell'algoritmo di PD

Consideriamo l'istanza del KPS dell'Esempio 23.1. Le righe si calcolano nell'ordine della tabella qui sotto, ciascuna per $k=0,1,\dots,10$; questi sono alcuni dei calcoli:

$u[1][0][1]=-\infty$, perché $k=1<s_1=2$
$v[1][7]=\max\{v[0][7],\,u[1][2][7]\}=\max\{0,\,9\}=9$
$v[2][10]=\max\{v[1][10],\,u[2][3][10]\}=\max\{9,\,11\}=11$
$u[2][3][10]=\max\{u[2][2][10],\,p_5+u[2][2][9]\}=\max\{10,\,3+8\}=11$
$u[2][2][9]=\max\{u[2][1][9],\,p_4+u[2][1][5]\}=\max\{6,\,7+1\}=8$
$u[2][1][5]=\max\{u[2][0][5],\,p_3+u[2][0][3]\}=\max\{0,\,4-3\}=1$
$u[2][0][3]=v[1][2]-f_2=0-3=-3$
$v[1][2]=\max\{v[0][2],\,u[1][2][2]\}=\max\{0,\,-2\}=0$

Questa è la tabella dei valori dopo l'esecuzione dell'algoritmo di PD, riga per riga nell'ordine di calcolo:

Riga	$k=0$	$k=1$	$k=2$	$k=3$	$k=4$	$k=5$	$k=6$	$k=7$	$k=8$	$k=9$	$k=10$
$v[0][k]$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$
$u[1][0][k]$ (setup)	$-\infty$	$-\infty$	$-2$	$-2$	$-2$	$-2$	$-2$	$-2$	$-2$	$-2$	$-2$
$u[1][1][k]$ ($j=1$)	$-\infty$	$-\infty$	$-2$	$-2$	$-2$	$4$	$4$	$4$	$4$	$4$	$4$
$u[1][2][k]$ ($j=2$)	$-\infty$	$-\infty$	$-2$	$-2$	$3$	$4$	$4$	$9$	$9$	$9$	$9$
$v[1][k]$	$0$	$0$	$0$	$0$	$3$	$4$	$4$	$9$	$9$	$9$	$9$
$u[2][0][k]$ (setup)	$-\infty$	$-3$	$-3$	$-3$	$-3$	$0$	$1$	$1$	$6$	$6$	$6$
$u[2][1][k]$ ($j=3$)	$-\infty$	$-3$	$-3$	$1$	$1$	$1$	$1$	$4$	$6$	$6$	$10$
$u[2][2][k]$ ($j=4$)	$-\infty$	$-3$	$-3$	$1$	$1$	$4$	$4$	$8$	$8$	$8$	$10$
$u[2][3][k]$ ($j=5$)	$-\infty$	$-3$	$0$	$1$	$4$	$4$	$7$	$8$	$11$	$11$	$11$
$v[2][k]$	$0$	$0$	$0$	$1$	$4$	$4$	$7$	$9$	$11$	$11$	$11$

Il valore ottimo dell'istanza è $v[2][10]=11$. I valori $-2$ e $-3$ nelle righe di setup sono i costi di setup pagati prima di selezionare qualsiasi oggetto.

Esempio 23.3: Le tabelle delle scelte

Per l'istanza dell'Esempio 23.1, queste sono le tabelle delle scelte calcolate dall'algoritmo di PD: le righe $s[h][i][\cdot]$ degli oggetti e le righe $o[h][\cdot]$ delle classi.

Riga	$k=0$	$k=1$	$k=2$	$k=3$	$k=4$	$k=5$	$k=6$	$k=7$	$k=8$	$k=9$	$k=10$
$s[1][1][k]$ ($j=1$)	$0$	$0$	$0$	$0$	$0$	$1$	$1$	$1$	$1$	$1$	$1$
$s[1][2][k]$ ($j=2$)	$0$	$0$	$0$	$0$	$1$	$0$	$0$	$1$	$1$	$1$	$1$
$o[1][k]$	$0$	$0$	$0$	$0$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
$s[2][1][k]$ ($j=3$)	$0$	$0$	$0$	$1$	$1$	$1$	$0$	$1$	$0$	$0$	$1$
$s[2][2][k]$ ($j=4$)	$0$	$0$	$0$	$0$	$0$	$1$	$1$	$1$	$1$	$1$	$0$
$s[2][3][k]$ ($j=5$)	$0$	$0$	$1$	$0$	$1$	$0$	$1$	$0$	$1$	$1$	$1$
$o[2][k]$	$0$	$0$	$0$	$1$	$1$	$0$	$1$	$0$	$1$	$1$	$1$

Una soluzione ottima si ricostruisce scorrendo le classi da $h=q$ fino a $h=1$, partendo da $k=c$ e da $x_j=0$ per ogni oggetto $j$.
Se $o[h][k]=0$, la classe $h$ è chiusa e $k$ non cambia. Se $o[h][k]=1$, gli oggetti della classe $h$ si scorrono da $i=t_h$ fino a $i=1$ come nel KP, e alla fine il peso di setup $s_h$ si sottrae da $k$.

Algoritmo: KPS_Reconstruct

Input: Il numero $q$ di classi, i pesi di setup $s_h$, il vettore $w[1..n]$, la capacità $c$ e le tabelle delle scelte $s$ e $o$

Output: Una soluzione ottima dell'istanza del KPS

1Function KPS_Reconstruct($q,w,c,s,o$)

2$x := \textnormal{new array}[1..n]$, con $x[j]=0$ per ogni $j$

3$k := c$

4for $h := q$ downto $1$ do

5if $o[h][k]=1$ then

6for $i := t_h$ downto $1$ do

7$j := \ell_{h-1}+i$; $x[j] \leftarrow s[h][i][k]$

8$k \leftarrow k-x[j]\,w[j]$

9end

10$k \leftarrow k-s_h$

11end

12end

13return $x$

Esempio 23.4: Calcolo di una soluzione ottima

Dopo l'esecuzione dell'algoritmo di PD sull'istanza dell'Esempio 23.1, partiamo da $h=2$ e $k=10$:

Iterazione	Stadio	$k$	Scelta	$x[3]$	$x[4]$	$x[5]$	Azione
$-$	$-$	$-$	$-$	0	0	0	$k=10$
$1$	$h=2$	$10$	$o[2][10]=1$	0	0	0	classe $2$ aperta
$2$	$j=5$	$10$	$s[2][3][10]=1$	0	0	1	$k\leftarrow 10-1=9$
$3$	$j=4$	$9$	$s[2][2][9]=1$	0	1	1	$k\leftarrow 9-4=5$
$4$	$j=3$	$5$	$s[2][1][5]=1$	1	1	1	$k\leftarrow 5-2=3$
$-$	$-$	$3$	$-$	1	1	1	setup: $k\leftarrow 3-s_2=2$
$5$	$h=1$	$2$	$o[1][2]=0$	1	1	1	classe $1$ chiusa

Il vettore $x=(0,0,1,1,1)$ è una soluzione ottima dell'istanza del KPS dell'Esempio 23.1: solo la classe $2$ è aperta, e sono selezionati gli oggetti $\{3,4,5\}$. Il suo peso totale è $2+4+1+s_2=8\le c$ e il suo valore ottimo è $v(2,10)=4+7+3-f_2=11$.

Gli oggetti della classe $1$ hanno il rapporto maggiore fra ricavo totale e peso totale ($11/5$ contro $14/7$), ma la classe $1$ resta chiusa. Con la sola classe $1$ il valore migliore è $v[1][10]=9$, mentre la classe $2$ aperta dà $u[2][3][10]=11$; dopo i suoi oggetti e il suo peso di setup resta solo $k=2$ per la classe $1$, e $o[1][2]=0$.

23.1.1 Numero di passi¶

Indichiamo con $S(n,q,c)$ il numero di passi eseguiti da KPS_DP nel caso peggiore. I cicli su $i$ scorrono gli oggetti di ogni classe, quindi su tutte le classi vengono eseguiti $t_1+t_2+\dots+t_q=n$ volte. Supponendo che le condizioni alle righe 9, 17 e 24 siano sempre vere:
- Le righe 2 e 29 vengono eseguite $1$ volta ciascuna.
- Le righe 3 e 4 vengono eseguite $c+1$ volte ciascuna.
- La riga 6 viene eseguita $q$ volte.
- Le righe 7, 8, 9, 10, 22, 23, 24 e 25 vengono eseguite $q(c+1)$ volte ciascuna.
- Le righe 13 e 14 vengono eseguite $n$ volte ciascuna.
- Le righe 15, 16, 17 e 18 vengono eseguite $n(c+1)$ volte ciascuna.
Quindi il numero totale di passi nel caso peggiore è

\[ S(n,q,c)=4n(c+1)+8q(c+1)+2n+q+2c+4. \]

Poiché ogni classe contiene almeno un oggetto, $1\le q\le n$, e

\[ 4n(c+1)\;\le\; S(n,q,c)\;\le\; 12n(c+1)+3n+2c+4. \]

Entrambi i bound sono $\Theta(nc)$, quindi $S(n,q,c)=\Theta(nc)$.

L'algoritmo di PD per il KPS esegue $S(n,q,c)=\Theta(nc)$ passi nel caso peggiore: i setup aggiungono $2q$ righe alle $n$ righe della ricorrenza del KP.
La ricostruzione esegue $\Theta(n)$ passi.

23.2 Errori tipici¶

Attenzione

Pagare il setup per ogni oggetto. Il setup della classe $h$ si paga una volta sola, nella riga $u(h,0,\cdot)$; le righe degli oggetti aggiungono solo $p_j$ e $w_j$.
Far partire gli oggetti di una classe da $v(h-1,k)$. Le righe di una classe aperta partono da $v(h-1,k-s_h)-f_h$: partire da $v(h-1,k)$ selezionerebbe oggetti senza pagare il setup.
Dimenticare il peso di setup nella ricostruzione. Dopo gli oggetti di una classe aperta, la capacità diminuisce anche di $s_h$.
Confondere $s_h$ con $s[h][i][k]$. Il peso di setup della classe $h$ ha un indice; la scelta dell'$i$-esimo oggetto della classe $h$ ne ha tre.

23.3 In sintesi¶

In sintesi

Per ogni classe $h$ l'algoritmo di PD confronta la classe chiusa, $v(h-1,k)$, con la classe aperta, $u(h,t_h,k)$.
La classe aperta parte da $u(h,0,k)=v(h-1,k-s_h)-f_h$, che paga il setup una volta sola, e prosegue con la ricorrenza del KP sui suoi oggetti.
Le tabelle delle scelte $s$ (oggetti) e $o$ (classi) danno una soluzione ottima, letta all'indietro a partire da $(q,c)$.
L'algoritmo di PD esegue $\Theta(nc)$ passi, come l'algoritmo di PD del KP.

Quadro riassuntivo dell'esempio del KPS. Esempio 23.1 ($c=10$, due classi):

Metodo	Lower bound	Upper bound	Origine
Algoritmo di PD	$11$	$11$	valore ottimo, soluzione $x=(0,0,1,1,1)$

Esercizi su questo capitolo: Zaino con setup (KPS)

Riga	\(k=0\)	\(k=1\)	\(k=2\)	\(k=3\)	\(k=4\)	\(k=5\)	\(k=6\)	\(k=7\)	\(k=8\)	\(k=9\)	\(k=10\)
\(v[0][k]\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)
\(u[1][0][k]\) (setup)	\(-\infty\)	\(-\infty\)	\(-2\)	\(-2\)	\(-2\)	\(-2\)	\(-2\)	\(-2\)	\(-2\)	\(-2\)	\(-2\)
\(u[1][1][k]\) (\(j=1\))	\(-\infty\)	\(-\infty\)	\(-2\)	\(-2\)	\(-2\)	\(4\)	\(4\)	\(4\)	\(4\)	\(4\)	\(4\)
\(u[1][2][k]\) (\(j=2\))	\(-\infty\)	\(-\infty\)	\(-2\)	\(-2\)	\(3\)	\(4\)	\(4\)	\(9\)	\(9\)	\(9\)	\(9\)
\(v[1][k]\)	\(0\)	\(0\)	\(0\)	\(0\)	\(3\)	\(4\)	\(4\)	\(9\)	\(9\)	\(9\)	\(9\)
\(u[2][0][k]\) (setup)	\(-\infty\)	\(-3\)	\(-3\)	\(-3\)	\(-3\)	\(0\)	\(1\)	\(1\)	\(6\)	\(6\)	\(6\)
\(u[2][1][k]\) (\(j=3\))	\(-\infty\)	\(-3\)	\(-3\)	\(1\)	\(1\)	\(1\)	\(1\)	\(4\)	\(6\)	\(6\)	\(10\)
\(u[2][2][k]\) (\(j=4\))	\(-\infty\)	\(-3\)	\(-3\)	\(1\)	\(1\)	\(4\)	\(4\)	\(8\)	\(8\)	\(8\)	\(10\)
\(u[2][3][k]\) (\(j=5\))	\(-\infty\)	\(-3\)	\(0\)	\(1\)	\(4\)	\(4\)	\(7\)	\(8\)	\(11\)	\(11\)	\(11\)
\(v[2][k]\)	\(0\)	\(0\)	\(0\)	\(1\)	\(4\)	\(4\)	\(7\)	\(9\)	\(11\)	\(11\)	\(11\)

Riga	\(k=0\)	\(k=1\)	\(k=2\)	\(k=3\)	\(k=4\)	\(k=5\)	\(k=6\)	\(k=7\)	\(k=8\)	\(k=9\)	\(k=10\)
\(s[1][1][k]\) (\(j=1\))	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(1\)	\(1\)	\(1\)	\(1\)	\(1\)	\(1\)
\(s[1][2][k]\) (\(j=2\))	\(0\)	\(0\)	\(0\)	\(0\)	\(1\)	\(0\)	\(0\)	\(1\)	\(1\)	\(1\)	\(1\)
\(o[1][k]\)	\(0\)	\(0\)	\(0\)	\(0\)	\(1\)	\(1\)	\(1\)	\(1\)	\(1\)	\(1\)	\(1\)
\(s[2][1][k]\) (\(j=3\))	\(0\)	\(0\)	\(0\)	\(1\)	\(1\)	\(1\)	\(0\)	\(1\)	\(0\)	\(0\)	\(1\)
\(s[2][2][k]\) (\(j=4\))	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(1\)	\(1\)	\(1\)	\(1\)	\(1\)	\(0\)
\(s[2][3][k]\) (\(j=5\))	\(0\)	\(0\)	\(1\)	\(0\)	\(1\)	\(0\)	\(1\)	\(0\)	\(1\)	\(1\)	\(1\)
\(o[2][k]\)	\(0\)	\(0\)	\(0\)	\(1\)	\(1\)	\(0\)	\(1\)	\(0\)	\(1\)	\(1\)	\(1\)

Iterazione	Stadio	\(k\)	Scelta	\(x[3]\)	\(x[4]\)	\(x[5]\)	Azione
\(-\)	\(-\)	\(-\)	\(-\)	0	0	0	\(k=10\)
\(1\)	\(h=2\)	\(10\)	\(o[2][10]=1\)	0	0	0	classe \(2\) aperta
\(2\)	\(j=5\)	\(10\)	\(s[2][3][10]=1\)	0	0	1	\(k\leftarrow 10-1=9\)
\(3\)	\(j=4\)	\(9\)	\(s[2][2][9]=1\)	0	1	1	\(k\leftarrow 9-4=5\)
\(4\)	\(j=3\)	\(5\)	\(s[2][1][5]=1\)	1	1	1	\(k\leftarrow 5-2=3\)
\(-\)	\(-\)	\(3\)	\(-\)	1	1	1	setup: \(k\leftarrow 3-s_2=2\)
\(5\)	\(h=1\)	\(2\)	\(o[1][2]=0\)	1	1	1	classe \(1\) chiusa