PD per il problema del subset sum¶

Parte 3 · Programmazione dinamica · Capitolo 20 · Dispensa, volume 3 (PDF) · Slide · Esercizi: Subset sum (SSP) · App: Tabelle della PD per i problemi di zaino

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 del subset sum e la sua soluzione come problema dello zaino 0/1 con $p_j=w_j$.
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 $r(j,k)\in\{\textit{true},\textit{false}\}$ delle somme raggiungibili, con i suoi casi base;
eseguire a mano l'algoritmo di PD e leggere la risposta dell'istanza dell'SSP in $r(n,c)$;
riempire la matrice $s$ e ricostruire un sottoinsieme di peso totale $c$ quando la risposta è sì;
mettere in relazione $r(j,k)$ con l'algoritmo di PD del KP con $p_j=w_j$, e contare i $\Theta(nc)$ passi.

Il problema di questo capitolo è il problema del subset sum (SSP): la sua definizione e le sue ipotesi sono nella sua pagina.

20.1 Un algoritmo di PD¶

Esempio 20.1: Istanza dell'SSP

Consideriamo un valore obiettivo $c=10$ e un insieme $\mathscr{I}=\{1,2,3,4\}$ di $4$ oggetti ($n=4$), con i seguenti pesi:

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

Chiamiamo questa istanza dell'SSP Esempio 20.1.

Un sottoinsieme $S\subseteq\mathscr{I}$ si descrive con il vettore binario $(x_1,x_2,\dots,x_n)$, dove $x_j=1$ se l'oggetto $j$ appartiene a $S$ e $x_j=0$ altrimenti.
La risposta all'istanza dell'SSP è sì se qualche vettore soddisfa $\sum_{j=1}^{n} w_j x_j = c$, e no altrimenti.
Passo 1: calcolo della risposta
Per ogni $j \in \{0,1,\dots,n\}$ e $k \in \{0,1,\dots,c\}$, sia $r(j,k)\in\{\textit{true},\textit{false}\}$ la risposta della sottoistanza dell'SSP data da:
1. un valore obiettivo $k$,
2. un insieme $\{1,2,\dots,j\}$ di oggetti disponibili,
3. per ogni oggetto $h \in \{1,2,\dots,j\}$, un peso $w_h$.
La formula ricorsiva per calcolare $r(j,k)$ è la seguente:

\[\begin{equation*} \label{eq:ssp} r(j,k)= \left\{ \begin{array}{ll} \textit{true} & \textrm{se $k=0$,}\\[2ex] \textit{false} & \textrm{se $j=0$ e $k\ge 1$,}\\[2ex] r(j-1,k) & \textrm{se $j,k\ge 1$ e $w_j>k$,}\\[2ex] r(j-1,k) \,\lor\, r(j-1,k-w_j) & \textrm{se $j,k\ge 1$ e $w_j\le k$.} \end{array} \right. \tag{20.1} \end{equation*}\]
- Il simbolo $\lor$ è l'or logico: $r(j,k)$ è true se almeno uno dei due valori è true.
- I casi base sono $r(j,0)=\textit{true}$, perché il sottoinsieme vuoto ha peso totale $0$, e $r(0,k)=\textit{false}$ per $k\ge 1$, perché nessun oggetto è disponibile.
- Un sottoinsieme di $\{1,2,\dots,j\}$ con peso totale $k$ o non contiene l'oggetto $j$, e allora è un sottoinsieme di $\{1,2,\dots,j-1\}$ con peso totale $k$, oppure contiene l'oggetto $j$, e allora gli altri oggetti formano un sottoinsieme di $\{1,2,\dots,j-1\}$ con peso totale $k-w_j$.
- Quindi la formula $\eqref{eq:ssp}$ genera al più $2$ sottoproblemi indipendenti, e un sottoinsieme per $(j,k)$ si costruisce da un sottoinsieme di uno di essi aggiungendo o no l'oggetto $j$.
  
  $\rightsquigarrow$ Sottostruttura ottima verificata!
- Decisioni diverse sugli oggetti possono portare alla stessa coppia $(j,k)$, e quindi lo stesso valore $r(j,k)$ può servire più volte durante la valutazione ricorsiva della formula $\eqref{eq:ssp}$.
  
  $\rightsquigarrow$ Sottoproblemi sovrapposti verificati!
- Il valore $r(j,k)$ dipende solo dai valori $r(j-1,k')$ con $k'\le k$. Quindi l'approccio bottom-up calcola le righe $j=0,1,\dots,n$ in quest'ordine, ciascuna per $k$ crescente, e memorizza ogni valore in una tabella di lookup.
- L'SSP si può risolvere anche con l'algoritmo di PD del KP, con $p_j=w_j$ per ogni oggetto $j$. Il suo valore $v(j,k)$ è il massimo peso totale, non superiore a $k$, di un sottoinsieme di $\{1,2,\dots,j\}$, e
  
  \[ r(j,k)=\textit{true} \iff v(j,k)=k. \]
- La ricorrenza $\eqref{eq:ssp}$ memorizza un solo bit per cella, e le sue operazioni logiche sostituiscono le somme e i confronti della ricorrenza del KP.

Passo 2: calcolo di un sottoinsieme

Quando la risposta è sì, un sottoinsieme di peso totale $c$ si ricostruisce dalla matrice $s$: $s[j][k]=1$ se l'oggetto $j$ è usato per raggiungere il valore true di $r[j][k]$, e $s[j][k]=0$ altrimenti.
L'algoritmo di PD preferisce non usare l'oggetto $j$: $s[j][k]=1$ solo se $r[j-1][k]$ è false e $r[j-1][k-w_j]$ è true.

Questo è lo pseudocodice dell'algoritmo di PD con l'approccio bottom-up, che memorizza la matrice $s$ insieme alla matrice $r$:

Algoritmo: SSP_DP

Input: Un'istanza dell'SSP data da $n$, dal vettore $w[1..n]$ e dal valore obiettivo $c$

Output: La risposta $r[n][c]$ dell'istanza dell'SSP e la matrice $s[0..n][0..c]$

1Function SSP_DP($n,w,c$)

2$r := \textnormal{new array}[0..n][0..c]$; $s := \textnormal{new array}[0..n][0..c]$

3$r[0][0] \leftarrow \textit{true}$; $s[0][0] \leftarrow 0$

4for $k := 1$ to $c$ do

5$r[0][k] \leftarrow \textit{false}$; $s[0][k] \leftarrow 0$

6end

7for $j := 1$ to $n$ do

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

9$r[j][k] \leftarrow r[j-1][k]$; $s[j][k] \leftarrow 0$

10if $r[j][k]=\textit{false}$ e $w[j]\le k$ e $r[j-1][k-w[j]]=\textit{true}$ then

11$r[j][k] \leftarrow \textit{true}$; $s[j][k] \leftarrow 1$

12end

13end

14end

15return $r[n][c], s$

La matrice $r[0..n][0..c]$ è la tabella di lookup delle risposte, e la matrice $s[0..n][0..c]$ memorizza le decisioni.
Le righe 3–5 riempiono la riga $j=0$: senza oggetti è raggiungibile solo il valore obiettivo $0$.
Per ogni coppia $(j,k)$, l'algoritmo di PD copia prima la risposta senza l'oggetto $j$, e poi usa l'oggetto $j$ solo se questa risposta è false e l'oggetto $j$ rende raggiungibile il valore $k$.
Infine, la risposta dell'istanza dell'SSP viene restituita come $r[n][c]$, insieme alla matrice $s$.

Esempio 20.2: Esecuzione dell'algoritmo di PD

Consideriamo l'istanza dell'SSP dell'Esempio 20.1, con valore obiettivo $c=10$ e pesi $w=(3,5,4,7)$.

Per ogni passo dell'algoritmo di PD con $j\ge 1$, la tabella riporta i valori di $j$ e $k$, le celle $r[j][k]$ e $s[j][k]$ e l'operazione eseguita; $\mathrm{T}$ sta per true e $\mathrm{F}$ per false. La riga $j=0$ è $r[0][0]=\mathrm{T}$ e $r[0][k]=\mathrm{F}$ per $k\ge 1$, con $s[0][k]=0$.

$j$	$k$	$r[j][k]$	$s[j][k]$	Azione
$1$	$0$	$\mathrm{T}$	$0$	$w_1=3>0$: $r[0][0]=\mathrm{T}$
$1$	$1$	$\mathrm{F}$	$0$	$w_1=3>1$: $r[0][1]=\mathrm{F}$
$1$	$2$	$\mathrm{F}$	$0$	$w_1=3>2$: $r[0][2]=\mathrm{F}$
$1$	$3$	$\mathrm{T}$	$1$	$r[0][3]\lor r[0][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$1$	$4$	$\mathrm{F}$	$0$	$r[0][4]\lor r[0][1]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$5$	$\mathrm{F}$	$0$	$r[0][5]\lor r[0][2]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$6$	$\mathrm{F}$	$0$	$r[0][6]\lor r[0][3]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$7$	$\mathrm{F}$	$0$	$r[0][7]\lor r[0][4]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$8$	$\mathrm{F}$	$0$	$r[0][8]\lor r[0][5]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$9$	$\mathrm{F}$	$0$	$r[0][9]\lor r[0][6]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$1$	$10$	$\mathrm{F}$	$0$	$r[0][10]\lor r[0][7]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$2$	$0$	$\mathrm{T}$	$0$	$w_2=5>0$: $r[1][0]=\mathrm{T}$
$2$	$1$	$\mathrm{F}$	$0$	$w_2=5>1$: $r[1][1]=\mathrm{F}$
$2$	$2$	$\mathrm{F}$	$0$	$w_2=5>2$: $r[1][2]=\mathrm{F}$
$2$	$3$	$\mathrm{T}$	$0$	$w_2=5>3$: $r[1][3]=\mathrm{T}$
$2$	$4$	$\mathrm{F}$	$0$	$w_2=5>4$: $r[1][4]=\mathrm{F}$
$2$	$5$	$\mathrm{T}$	$1$	$r[1][5]\lor r[1][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$2$	$6$	$\mathrm{F}$	$0$	$r[1][6]\lor r[1][1]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$2$	$7$	$\mathrm{F}$	$0$	$r[1][7]\lor r[1][2]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$2$	$8$	$\mathrm{T}$	$1$	$r[1][8]\lor r[1][3]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$2$	$9$	$\mathrm{F}$	$0$	$r[1][9]\lor r[1][4]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$2$	$10$	$\mathrm{F}$	$0$	$r[1][10]\lor r[1][5]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$

$j$	$k$	$r[j][k]$	$s[j][k]$	Azione
$3$	$0$	$\mathrm{T}$	$0$	$w_3=4>0$: $r[2][0]=\mathrm{T}$
$3$	$1$	$\mathrm{F}$	$0$	$w_3=4>1$: $r[2][1]=\mathrm{F}$
$3$	$2$	$\mathrm{F}$	$0$	$w_3=4>2$: $r[2][2]=\mathrm{F}$
$3$	$3$	$\mathrm{T}$	$0$	$w_3=4>3$: $r[2][3]=\mathrm{T}$
$3$	$4$	$\mathrm{T}$	$1$	$r[2][4]\lor r[2][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$3$	$5$	$\mathrm{T}$	$0$	$r[2][5]\lor r[2][1]=\mathrm{T}\lor \mathrm{F}=\mathrm{T}$
$3$	$6$	$\mathrm{F}$	$0$	$r[2][6]\lor r[2][2]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$3$	$7$	$\mathrm{T}$	$1$	$r[2][7]\lor r[2][3]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$3$	$8$	$\mathrm{T}$	$0$	$r[2][8]\lor r[2][4]=\mathrm{T}\lor \mathrm{F}=\mathrm{T}$
$3$	$9$	$\mathrm{T}$	$1$	$r[2][9]\lor r[2][5]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$
$3$	$10$	$\mathrm{F}$	$0$	$r[2][10]\lor r[2][6]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}$
$4$	$0$	$\mathrm{T}$	$0$	$w_4=7>0$: $r[3][0]=\mathrm{T}$
$4$	$1$	$\mathrm{F}$	$0$	$w_4=7>1$: $r[3][1]=\mathrm{F}$
$4$	$2$	$\mathrm{F}$	$0$	$w_4=7>2$: $r[3][2]=\mathrm{F}$
$4$	$3$	$\mathrm{T}$	$0$	$w_4=7>3$: $r[3][3]=\mathrm{T}$
$4$	$4$	$\mathrm{T}$	$0$	$w_4=7>4$: $r[3][4]=\mathrm{T}$
$4$	$5$	$\mathrm{T}$	$0$	$w_4=7>5$: $r[3][5]=\mathrm{T}$
$4$	$6$	$\mathrm{F}$	$0$	$w_4=7>6$: $r[3][6]=\mathrm{F}$
$4$	$7$	$\mathrm{T}$	$0$	$r[3][7]\lor r[3][0]=\mathrm{T}\lor \mathrm{T}=\mathrm{T}$
$4$	$8$	$\mathrm{T}$	$0$	$r[3][8]\lor r[3][1]=\mathrm{T}\lor \mathrm{F}=\mathrm{T}$
$4$	$9$	$\mathrm{T}$	$0$	$r[3][9]\lor r[3][2]=\mathrm{T}\lor \mathrm{F}=\mathrm{T}$
$4$	$10$	$\mathrm{T}$	$1$	$r[3][10]\lor r[3][3]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}$

Questa è la matrice $r$ dopo l'esecuzione dell'algoritmo di PD:

\[ \begin{array}{l|rrrrrrrrrrr} \hline {r[j][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} & {k=8} & {k=9} & {k=10} \\ \hline {j=0} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} \\ {j=1} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} \\ {j=2} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} \\ {j=3} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{F}} \\ {j=4} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{T}} \\ \hline \end{array} \]

Questa è la matrice $s$ dopo l'esecuzione dell'algoritmo di PD:

\[ \begin{array}{l|rrrrrrrrrrr} \hline {s[j][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} & {k=8} & {k=9} & {k=10} \\ \hline {j=0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} \\ {j=1} & {0} & {0} & {0} & {1} & {0} & {0} & {0} & {0} & {0} & {0} & {0} \\ {j=2} & {0} & {0} & {0} & {0} & {0} & {1} & {0} & {0} & {1} & {0} & {0} \\ {j=3} & {0} & {0} & {0} & {0} & {1} & {0} & {0} & {1} & {0} & {1} & {0} \\ {j=4} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {1} \\ \hline \end{array} \]

Poiché $r[4][10]=\mathrm{T}$, la risposta all'istanza dell'SSP è sì. Per esempio, $s[4][10]=1$ perché $r[3][10]=\mathrm{F}$ e $r[3][3]=\mathrm{T}$: l'oggetto $4$ serve per raggiungere il valore obiettivo $10$.

Calcolata la matrice $s$, se $r[n][c]$ è true si ricostruisce un sottoinsieme di peso totale $c$ scorrendo gli oggetti da $j=n$ fino a $j=1$, partendo da $k=c$ e da $x_j=0$ per ogni oggetto $j$:

\[ x_j \leftarrow s[j][k], \qquad k \leftarrow k - s[j][k]\,w_j. \]
La ricostruzione termina con $k=0$, perché ogni passo mantiene $r[j-1][k]$ uguale a true.

Algoritmo: SSP_Reconstruct

Input: Il numero $n$ di oggetti, il valore obiettivo $c$, il vettore $w[1..n]$ e la matrice $s[0..n][0..c]$, con $r[n][c]=\textit{true}$

Output: Un sottoinsieme di peso totale $c$, come vettore binario

1Function SSP_Reconstruct($n,c,w,s$)

2$x := \textnormal{new array}[1..n]$

3$k := c$

4for $j := n$ downto $1$ do

5$x[j] \leftarrow s[j][k]$

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

7end

8return $x$

Esempio 20.3: Calcolo di un sottoinsieme

Dopo l'esecuzione dell'algoritmo di PD sull'istanza dell'Esempio 20.1, partiamo da $j=4$ e $k=10$:

Iterazione	$j$	$k$	$s[j][k]$	$x[1]$	$x[4]$	Azione
$-$	$-$	$-$	$-$	0	0	$k=10$
$1$	$4$	$10$	$1$	0	1	$x[4]\leftarrow 1$, $k\leftarrow 10-7=3$
$2$	$3$	$3$	$0$	0	1	$x[3]\leftarrow 0$, $k=3$
$3$	$2$	$3$	$0$	0	1	$x[2]\leftarrow 0$, $k=3$
$4$	$1$	$3$	$1$	1	1	$x[1]\leftarrow 1$, $k\leftarrow 3-3=0$

La risposta all'istanza dell'SSP dell'Esempio 20.1 è sì: il vettore $(1,0,0,1)$ seleziona il sottoinsieme $\{1,4\}$, il cui peso totale è $3+7=c$.

20.1.1 Numero di passi¶

Indichiamo con $S(n,c)$ il numero di passi eseguiti da SSP_DP nel caso peggiore. Contiamo quante volte viene eseguita ogni riga dello pseudocodice, supponendo che la condizione alla riga 10 sia sempre vera:
- Le righe 2 e 3 vengono eseguite $1$ volta ciascuna.
- La riga 4 viene eseguita $c$ volte, e la riga 5 $c$ volte.
- La riga 7 viene eseguita $n$ volte.
- Le righe 8, 9, 10 e 11 vengono eseguite $n(c+1)$ volte ciascuna.
- La riga 15 viene eseguita $1$ volta.
Quindi il numero totale di passi nel caso peggiore è

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

Di conseguenza,

\[ S(n,c)=\Theta(nc), \]

poiché

\[ \lim_{n,c\to\infty}\frac{4n(c+1)+n+2c+3}{nc} =\lim_{n,c\to\infty}\left(4+\frac{4}{c}+\frac{1}{c}+\frac{2}{n}+\frac{3}{nc}\right)=4\in\mathbb{R}_{>0}. \]

L'algoritmo di PD per l'SSP esegue $S(n,c)=\Theta(nc)$ passi nel caso peggiore, lo stesso numero dell'algoritmo di PD del KP.
La ricostruzione esegue $\Theta(n)$ passi, uno per ogni oggetto.
Il numero di passi contiene il valore obiettivo $c$, un numero dell'input, e non solo la dimensione dell'input: è pseudo-polinomiale.

20.2 Errori tipici¶

Attenzione

Porre $r(j,0)=\textit{false}$. Il valore obiettivo $0$ è sempre raggiungibile con il sottoinsieme vuoto; con $r(j,0)=\textit{false}$ nessun valore diventerebbe mai true.
Porre $r(0,k)=\textit{true}$ per $k\ge 1$. Senza oggetti è raggiungibile solo il valore obiettivo $0$.
Leggere la risposta nella cella sbagliata. La risposta è $r(n,c)$; un valore true in un'altra cella dell'ultima riga dice che è raggiungibile un valore obiettivo diverso.
Ricostruire quando la risposta è no. Se $r(n,c)$ è false, nessun sottoinsieme ha peso totale $c$, e la matrice $s$ non dà nulla da ricostruire.

20.3 In sintesi¶

In sintesi

La ricorrenza $r(j,k)=r(j-1,k)\lor r(j-1,k-w_j)$ dice se il valore obiettivo $k$ è raggiungibile con gli oggetti $1,2,\dots,j$.
I casi base sono $r(j,0)=\textit{true}$ e $r(0,k)=\textit{false}$ per $k\ge 1$; la risposta è $r(n,c)$.
La matrice $s$ memorizza se l'oggetto $j$ è usato, e un sottoinsieme di peso totale $c$ si legge all'indietro a partire da $(n,c)$.
L'algoritmo di PD esegue $\Theta(nc)$ passi, come l'algoritmo di PD del KP con $p_j=w_j$.

Quadro riassuntivo dell'esempio dell'SSP. Esempio 20.1 ($c=10$, quattro oggetti):

Metodo	Risposta	Origine
Algoritmo di PD	sì	$r(4,10)=\textit{true}$, sottoinsieme $\{1,4\}$

Esercizi su questo capitolo: Subset sum (SSP)

Nel laboratorio interattivo: Tabelle della PD per i problemi di zaino.

\(j\)	\(k\)	\(r[j][k]\)	\(s[j][k]\)	Azione
\(1\)	\(0\)	\(\mathrm{T}\)	\(0\)	\(w_1=3>0\): \(r[0][0]=\mathrm{T}\)
\(1\)	\(1\)	\(\mathrm{F}\)	\(0\)	\(w_1=3>1\): \(r[0][1]=\mathrm{F}\)
\(1\)	\(2\)	\(\mathrm{F}\)	\(0\)	\(w_1=3>2\): \(r[0][2]=\mathrm{F}\)
\(1\)	\(3\)	\(\mathrm{T}\)	\(1\)	\(r[0][3]\lor r[0][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}\)
\(1\)	\(4\)	\(\mathrm{F}\)	\(0\)	\(r[0][4]\lor r[0][1]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(1\)	\(5\)	\(\mathrm{F}\)	\(0\)	\(r[0][5]\lor r[0][2]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(1\)	\(6\)	\(\mathrm{F}\)	\(0\)	\(r[0][6]\lor r[0][3]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(1\)	\(7\)	\(\mathrm{F}\)	\(0\)	\(r[0][7]\lor r[0][4]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(1\)	\(8\)	\(\mathrm{F}\)	\(0\)	\(r[0][8]\lor r[0][5]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(1\)	\(9\)	\(\mathrm{F}\)	\(0\)	\(r[0][9]\lor r[0][6]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(1\)	\(10\)	\(\mathrm{F}\)	\(0\)	\(r[0][10]\lor r[0][7]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(2\)	\(0\)	\(\mathrm{T}\)	\(0\)	\(w_2=5>0\): \(r[1][0]=\mathrm{T}\)
\(2\)	\(1\)	\(\mathrm{F}\)	\(0\)	\(w_2=5>1\): \(r[1][1]=\mathrm{F}\)
\(2\)	\(2\)	\(\mathrm{F}\)	\(0\)	\(w_2=5>2\): \(r[1][2]=\mathrm{F}\)
\(2\)	\(3\)	\(\mathrm{T}\)	\(0\)	\(w_2=5>3\): \(r[1][3]=\mathrm{T}\)
\(2\)	\(4\)	\(\mathrm{F}\)	\(0\)	\(w_2=5>4\): \(r[1][4]=\mathrm{F}\)
\(2\)	\(5\)	\(\mathrm{T}\)	\(1\)	\(r[1][5]\lor r[1][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}\)
\(2\)	\(6\)	\(\mathrm{F}\)	\(0\)	\(r[1][6]\lor r[1][1]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(2\)	\(7\)	\(\mathrm{F}\)	\(0\)	\(r[1][7]\lor r[1][2]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(2\)	\(8\)	\(\mathrm{T}\)	\(1\)	\(r[1][8]\lor r[1][3]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}\)
\(2\)	\(9\)	\(\mathrm{F}\)	\(0\)	\(r[1][9]\lor r[1][4]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(2\)	\(10\)	\(\mathrm{F}\)	\(0\)	\(r[1][10]\lor r[1][5]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)

\(j\)	\(k\)	\(r[j][k]\)	\(s[j][k]\)	Azione
\(3\)	\(0\)	\(\mathrm{T}\)	\(0\)	\(w_3=4>0\): \(r[2][0]=\mathrm{T}\)
\(3\)	\(1\)	\(\mathrm{F}\)	\(0\)	\(w_3=4>1\): \(r[2][1]=\mathrm{F}\)
\(3\)	\(2\)	\(\mathrm{F}\)	\(0\)	\(w_3=4>2\): \(r[2][2]=\mathrm{F}\)
\(3\)	\(3\)	\(\mathrm{T}\)	\(0\)	\(w_3=4>3\): \(r[2][3]=\mathrm{T}\)
\(3\)	\(4\)	\(\mathrm{T}\)	\(1\)	\(r[2][4]\lor r[2][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}\)
\(3\)	\(5\)	\(\mathrm{T}\)	\(0\)	\(r[2][5]\lor r[2][1]=\mathrm{T}\lor \mathrm{F}=\mathrm{T}\)
\(3\)	\(6\)	\(\mathrm{F}\)	\(0\)	\(r[2][6]\lor r[2][2]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(3\)	\(7\)	\(\mathrm{T}\)	\(1\)	\(r[2][7]\lor r[2][3]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}\)
\(3\)	\(8\)	\(\mathrm{T}\)	\(0\)	\(r[2][8]\lor r[2][4]=\mathrm{T}\lor \mathrm{F}=\mathrm{T}\)
\(3\)	\(9\)	\(\mathrm{T}\)	\(1\)	\(r[2][9]\lor r[2][5]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}\)
\(3\)	\(10\)	\(\mathrm{F}\)	\(0\)	\(r[2][10]\lor r[2][6]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
\(4\)	\(0\)	\(\mathrm{T}\)	\(0\)	\(w_4=7>0\): \(r[3][0]=\mathrm{T}\)
\(4\)	\(1\)	\(\mathrm{F}\)	\(0\)	\(w_4=7>1\): \(r[3][1]=\mathrm{F}\)
\(4\)	\(2\)	\(\mathrm{F}\)	\(0\)	\(w_4=7>2\): \(r[3][2]=\mathrm{F}\)
\(4\)	\(3\)	\(\mathrm{T}\)	\(0\)	\(w_4=7>3\): \(r[3][3]=\mathrm{T}\)
\(4\)	\(4\)	\(\mathrm{T}\)	\(0\)	\(w_4=7>4\): \(r[3][4]=\mathrm{T}\)
\(4\)	\(5\)	\(\mathrm{T}\)	\(0\)	\(w_4=7>5\): \(r[3][5]=\mathrm{T}\)
\(4\)	\(6\)	\(\mathrm{F}\)	\(0\)	\(w_4=7>6\): \(r[3][6]=\mathrm{F}\)
\(4\)	\(7\)	\(\mathrm{T}\)	\(0\)	\(r[3][7]\lor r[3][0]=\mathrm{T}\lor \mathrm{T}=\mathrm{T}\)
\(4\)	\(8\)	\(\mathrm{T}\)	\(0\)	\(r[3][8]\lor r[3][1]=\mathrm{T}\lor \mathrm{F}=\mathrm{T}\)
\(4\)	\(9\)	\(\mathrm{T}\)	\(0\)	\(r[3][9]\lor r[3][2]=\mathrm{T}\lor \mathrm{F}=\mathrm{T}\)
\(4\)	\(10\)	\(\mathrm{T}\)	\(1\)	\(r[3][10]\lor r[3][3]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}\)

Iterazione	\(j\)	\(k\)	\(s[j][k]\)	\(x[1]\)	\(x[4]\)	Azione
\(-\)	\(-\)	\(-\)	\(-\)	0	0	\(k=10\)
\(1\)	\(4\)	\(10\)	\(1\)	0	1	\(x[4]\leftarrow 1\), \(k\leftarrow 10-7=3\)
\(2\)	\(3\)	\(3\)	\(0\)	0	1	\(x[3]\leftarrow 0\), \(k=3\)
\(3\)	\(2\)	\(3\)	\(0\)	0	1	\(x[2]\leftarrow 0\), \(k=3\)
\(4\)	\(1\)	\(3\)	\(1\)	1	1	\(x[1]\leftarrow 1\), \(k\leftarrow 3-3=0\)