DEFINIZIONE

E GESTIONE DI MATRICI IN JAVA Domenico Sacc

1. Tipo Matrice: array of array
Abbiamo visto come in Java sia possibile utilizzare gli array, che rappresentano vettori di elementi tutti dello stesso tipo. Ad esempio: int [ ] X; char [ ] Y; double [ ] Z; String [ ] W; definiscono X come array di interi, Y come array di caratteri, Z come array di double e W come array di stringhe. E possibile anche definire array di array, ad esempio int [ ] [ ] X; definisce che X un array di elementi, ciascuno a sua volta costituito da array di interi. Quindi X una matrice bidimensionale di interi. Per dimensionare un array necessario utilizzare il costrutto new, ad esempio: X = new int [10] [5] fissa a 10 il numero di righe di X, individuate con appositi indici che vanno da 0 a 9, e a 5 il numero di colonne per ogni riga X[i], gli indici di colonna vanno da 0 a 4 e gli elementi della riga vanno X[i][0] a X[i][4] . Si noti che X[i] di tipo array di interi mentre X[i][j] un intero. E possibile anche stabilire la dimensione dellarray nel momento della sua definizione: int [ ] [ ] X = new int [10] [5]; E anche possibile ridimensionare un array di array. Ad esempio int [ ] [ ] X = new int [10] [5]; for ( int i =0; i < 10; i++ ) for ( int j =0; j < 5; j++ ) X[i] [j]=i*j; // vengono inizializzati gli elementi di X X = new int [4] [4]; // ora X una matrice quadrata 4 x 4 // attenzione che i 50 elementi precedenti ora sono cancellati for ( int i = 0; i < 4; i++) X [i]= new int [i]; // ora X una matrice triangolare! int [ ] [ ] Y = new int [4] [ ] for ( int i = 0; i < 4; i++) Y [i]= new int [i]; // ora Y una matrice triangolare! E quindi anche possibile definire una matrice in cui ogni riga ha un numero differente di colonne. Si noti che nella definizione di Y, le colonne sono state dimensionate a zero per poi essere dimensionate in vario modo per ciascuna riga.

2. Operazioni su Matrice
Date due matrici A e B conformi (cio il numero n di righe di A uguale al numero di righe di B e il numero m di colonne di A uguale al numero di colonne di B), possiamo calcolare la matrice C come somma di A e B. Cio per 0 <= i < n, 0 <= j < m, C[i][j] = A[i][j]+B[i][j]. Presentiamo di seguito un metodo per il calcolo della somma che restituisce true se la somma stata effettuata e false diversamente (cio le matrici non sono conformi).
static boolean sommaMatrici( double[] [] A, double [][] B, double [][] C) { // somma di due matrici: C = A+B // Le 3 matrici devono essere conformi (stesse dimensioni) if ( A.length != B.length || A[0].length != B[0].length || A.length != C.length || A[0].length != C[0].length ) return false; // matrici non conformi

for ( int i = 0; i < A.length; i++) for ( int j =0; j < A[0].length; j++ ) C[i][j] = A[i][j]+B[i][j]; return true; }

La complessit delloperazione di somma (nm) ovvio che si tratta di un algoritmo ottimale (non possibile fare di meglio in quanto vanno trascritti tutti i valori su C e questi sono in numero di n m). In modo simile pu essere definita loperazione di sottrazione. Unaltra classica operazione sulle matrice il calcolo della trasposta. Data una matrice A di dimensioni n x m, la sua trasposta una matrice AT di dimensioni m n tale che per ogni 0 <= i < n, 0 <= j < m, AT[j][i] = A[i][j]. Presentiamo di seguito un metodo per restituisce la trasposta di una matrice.
static double [] [] trasposta ( double [][] A) { // AT la trasposta della matrice M double [][] AT = new double [A[0].length][A.length]; for ( int i = 0; i < A.length; i++ ) for ( int j = 0; j < A[0].length; j++ ) AT[j][i] = A[i][j]; return AT; }

La complessit delloperazione ancora (n m) anche in questo caso che si tratta di un algoritmo ottimale (non possibile fare di meglio in quanto vanno trascritti tutti i valori su C e questi sono in numero di n m). Vediamo ora come calcolare il prodotto scalare di due matrici A e B conformi (cio il numero di colonne di A uguale al numero di righe di B). Il risultato una matrice C che ha lo stesso numero di righe di A e lo stesso numero di colonne di B. Siano n il numero di righe di A, p il numero di colonne di A (pari al numero di righe di B) e m il numero di colonne di B. Per ogni 0 <= i < n, 0 <= j < m, C[j][i] = 0 <= k < p A[i][k] x B[k][j]. Presentiamo di seguito un metodo per il calcolo del prodotto scalare che restituisce true se il prodotto stato effettuato e false diversamente (cio le matrici non sono conformi).
static boolean moltiplicaMatrici( double[][] A, double []] B, double [][] C) { if ( A[0].length != B.length || A.length != C.length || B[0].length != C[0].length ) return false; // matrici non conformi for ( int i = 0; i < C.length; i++) for ( int j =0; j < C[i].length; j++ ) { C[i][j] = 0; for ( int k = 0; k < A[0].length; k++ ) C[i][j] += A[i][k]*B[k][j]; } return true; }

La complessit delloperazione ancora (n p m) che diventa (n3) nel caso di matrici quadrate. In questo caso non si tratta di un algoritmo ottimale in quanto il lower bound del problema (n2). In effetti esistono algoritmi che effettuano il prodotto in tempo (nq) con q intorno a 2.5.

3. Matrici Triangolari
Una matrice quadrata A di dimensioni n x n triangolare inferiore se tutti gli elementi sopra la diagonale principale sono uguali a 0, cio per 0 <= i < n, i < j < m, C[i][j] = 0. Presentiamo di seguito un metodo per la verifica se una matrice quadrata sia triangolare inferiore.
static boolean eTriangolareInferiore( double [] [] A ) { boolean verificato = true; for ( int i = 0; i < A.length-1 && verificato; i++ ) for ( int j = i+1; j < A[0].length && verificato; j++) verificato = A[i][j] == 0; return verificato; }

Calcoliamo il numero N di confronti effettuati dal metodo. Per i = 0, vengono effettuati n-1 confronti, per i = 1, n-2 confronti, , per i = n-2, 1 confronto e per i = n-1, 0 confronti. Quindi N = (n-1) + (n-2) + + 1 = n (n-1) / 2. Quindi la complessit (n2). Una matrice quadrata A di dimensioni n x n triangolare superiore se tutti gli elementi sotto la diagonale principale sono uguali a 0, cio per 0 <= i < n, 0 <= j < i, C[i][j] = 0. Presentiamo di seguito un metodo per la verifica se una matrice quadrata sia triangolare superiore.
static boolean eTriangolareSuperiore( double [] [] A ) { boolean verificato = true; for ( int i = 1; i < A.length && verificato; i++ ) for ( int j = 0; j < i && verificato; j++) verificato = A[i][j] == 0; return verificato; }

Anche in questo caso il numero N pari a n (n-1) / 2 e la complessit (n2). Un caso degenere di matrice triangolare una matrice diagonale in cui tutti gli elementi sopra e sotto la diagonale principale sono uguali a 0, cio per 0 <= i < n, 0 <= j < n, i j, C[i][j] = 0. Presentiamo di seguito un metodo per la verifica se una matrice quadrata sia diagonale.
static boolean eDiagonale( double [] [] A ) { boolean verificato = true; for ( int i = 0; i < A.length && verificato; i++ ) for ( int j = i+1; j < A[0].length && verificato; j++) verificato = A[i][j] == 0 && A[j][i] == 0; return verificato; }

La complessit del metodo (n2).

4. Risoluzione di un Sistema di Equazioni Lineari

Sia dato il seguente sistema S di n equazioni lineari in n incognite:

 a0,0 x 0 a1,0 x 0 S ai,0 x 0 an 1,0 x 0

+ a0,1 x1 + a1,1 x1 + ai,1 x1 + an 1,1 x1

+ + a0, j x j + + a1, j x j + + ai, j x j + + an 1, j x n 1

+ + a0,n 1 x n 1 + + a1,n 1 x n 1 + + ai,n 1 x n 1

= b0 = b1 = bi

+ + an 1,n 1 x n 1 = bn 1

In forma matriciale S pu essere scritto come A XT = BT, dove A la matrice nn dei coefficienti ai,j, XT il trasposto del vettore X delle incognite xi e BT il trasposto del vettore dei termini noti bi (cio XT e BT hanno dimensioni n1).

a0,0 a1,0 a j ,0 an 1,0

a0,1 a1,1 ai,1 an 1,1

a0, j a1, j ai, j an 1, j A

a0,n 1 x 0 b0 a1,n 1 x1 b1 ai,n 1 x i = bi an 1,n 1 x n 1 bn 1 XT BT

La risoluzione del sistema consiste nel determinare il vettore X delle incognite. Affrontiamo questo problema considerando per prima il caso semplice in cui la matrice A sia triangolare superiore (o singolare, cio tutti gli elementi sulla diagonale principale aj,j sono diversi da 0. Il inferiore) e non sistema ha quindi questo formato:

a0,0 x 0 S

+ a0,1 x1 + + a0, j x j + a1,1 x1 + + a1, j x j a j, j x j

+ + a0,n 1 x n 1 + + a1,n 1 x n 1

= b0 = b1

+ + a j ,n 1 x n 1 = b j an 1,n 1 x n 1 = bn 1

In questo caso la risoluzione immediata in quanto sufficiente calcolare xn-1 = bn-1/an-1,n-1 dallultima equazione e quindi sostituire questo valore per xn-1 nella penultima equazione: an 2,n 2 x n 2 + an 2,n 1 x n 1 = bn 2 per calcolare xn-2 = (bn-2 an-2,n-1 bn-1/an-1,n-1)/an -2,n -2 e cos via. Il sistema S triangolare superiore pu essere quindi risolto dal seguente metodo si noti che per valutare una eventuale singolarit della matrice, va verificato se sulla diagonale non ci sia qualche elemento uguale a zero:
static boolean risSistemaTriangSup( double [] [] A, double [] B, double [] X ) { if ( diagonaleConZero(A) ) return false; for ( int i = X.length-1; i >= 0 ; i-- ) { X[i] = B[i]; for ( int j=i+1; j < A[0].length; j++) X[i] -= X[j]*A[i][j]; X[i] = X[i]/A[i][i];

} return true; }

Poich ci sono due cicli di 'for' innestati, la funzione ha complessit (n2); quindi essa ha una complessit ottima in quanto per calcolare le incognite non possibile evitare di scandire gli elementi nel triangolo non-zero della matrice che sono in numero di n(n+1)/2 = (n2). Si noti che abbiamo assunto che le matrici A e B e il vettore X abbiano dimensioni conformi per cui non effettuato alcun controllo responsabilit del metodo chiamante verificare tale conformit prima della chiamata. Il metodo diagonaleConZero :
static boolean diagonaleConZero( double [] [] A ) { boolean esisteZero = false; for ( int i = 0; i < A.length && !esisteZero; i++ ) esisteZero = A[i][i] == 0; return esisteZero; }

La complessit ovviamente (n). Prima di procedere alla risoluzione del caso generale di un sistema di equazioni lineari, mostriamo la risoluzione anche per il caso di matrice triangolare inferiore.
static boolean risSistemaTriangInf( double [] [] A, double [] B, double [] X ) { if ( diagonaleConZero(A) ) return false; for ( int i = 0; i < X.length ; i++ ) { X[i] = B[i]; for ( int j=0; j < i; j++) X[i] -= X[j]*A[i][j]; X[i] = X[i]/A[i][i]; } return true; }

Per risolvere un sistema generale di equazioni lineari sufficiente far precedere la funzione 'risSistemaTriangSup' da un passo di triangolarizzazione della matrice, ad esempio applicando la ben nota eliminazione gaussiana nel seguente modo. Per rendere la matrice A triangolare superiore, procediamo nel seguente modo. Cominciamo con azzerare tutti i coefficienti della colonna 0 sotto la diagonale, cio aj,1, 1 j n-1, in modo che la matrice diventi:

a0,0 x 0 + a0,1 x1 a1,1 x1 S ai,1 x1 an 1,1 x1

+ + a0, j x j + + a1, j x j + + ai, j x j

+ + a0,n 1 x n 1 + + a1,n 1 x n 1 + + ai,n 1 x n 1

= b0 = b1 = bi

+ + an 1, j x n 1 + + an 1,n 1 x n 1 = bn 1

A tale scopo lequazione 1 viene modificata sottraendo ad essa la riga 0 moltiplicata per a1,0/a0,0 in modo che il coefficiente di x1 nella riga 1 (cio a1,0) diventi zero. Quindi per ogni j, 0 j n-1, ogni coefficiente a1,j viene modificato in a1,j a0,j a1,0/a0,0 e il termine noto b1 viene modificato in b1 b0

 a1,0/a0,0. Allo stesso modo si annulla il coefficiente ai,0 di x0 nelle altre righe i sottostanti, sottraendo a ciascuna di esse la riga 0 moltiplicata per ai,0/a0,0. Passiamo ora ad annullare i coefficienti sotto la diagonale della colonna 1; pertanto, per ogni riga i, 2 i n-1, annulliamo il coefficiente ai,1 di x1 sottraendo ad essa la riga 1 moltiplicata per ai,1/a1,1. Si noti che il coefficiente ai,0, che era stato modificato a 0 nel passo precedente, rimane tale in quanto per esso la sottrazione comporta la modifica in ai,0 a1,0 ai,1/a1,1 , che vale 0 essendo anche a1,0 = 0.

a0,0 x 0 + a0,1 x1 + a0,2 x 2 + a1,1 x1 + a1,2 x 2 + S ai,2 x 2 + an 1,2 x 2 +

+ a0, j x j + a1, j x j + ai, j x j + an 1, j x n 1

+ + a0,n 1 x n 1 + + a1,n 1 x n 1 + + ai,n 1 x n 1

= b0 = b1 = bi

+ + an 1,n 1 x n 1 = bn 1

Iteriamo il procedimento per tutte le altre colonne j. Per annullare i coefficienti sotto la diagonale della colonna j, per ogni riga i, j+1 i n-1, annulliamo il coefficiente di xj sottraendo alla riga i la riga j moltiplicata per ai,j/aj,j. Al passo j-mo il sistema diventa:

a0,0 x 0 + a0,1 x1 + a0,2 x 2 + a1,1 x1 + a1,2 x 2 + S

+ a0, j x j + a1, j x j a j, j x j

+ + a0,n 1 x n 1 + + a1,n 1 x n 1 + + ai,n 1 x n 1

= b0 = b1 = bj

an 1, j x n 1 + + an 1,n 1 x n 1 = bn 1

Alla fine delle iterazioni il sistema diventa triangolare superiore a meno che la matrice A non sia singolare e non ammetta, quindi, soluzioni. Per la verifica di singolarit, sufficiente verificare che, ad passo j della triangolarizzazione, non sia effettuata una divisione per aj,j sia diverso da 0 ogni altrimenti verrebbe effettuata una divisione per zero. Ma il fatto che un qualche aj,j sia zero non comporta necessariamente che la matrice sia singolare; infatti l'anomalia potrebbe essere eliminata con un opportuno scambio di righe. Ad esempio, la matrice

0 1 1 1
pu essere triangolarizzata semplicemente scambiando le due righe. Introduciamo quindi nell'algoritmo di triangolarizzazione la possibilit di scambiare una riga i con una riga successiva se il coefficiente aj,j sulla diagonale nullo. Otteniamo cos un metodo per risolvere un sistema generale di equazioni lineari che realizza il metodo di eliminazione di Gauss:
static boolean risSistemaEquazioni ( double [][] A, double [] B, double [] X) { boolean singolare = false; for ( int i = 0; i < A.length-1 && !singolare; i++ ) { if ( A[i][i] == 0 ) singolare = !scambiaRiga(A,B,i); for ( int j = i+1; j < A.length && !singolare; j++ ) { double d = A[j][i]/A[i][i]; for ( int k = i+1; k < A.length; k++ ) A[j][k] -= d*A[i][k]; /***

B[j] -= d*B[i]; } } if ( !singolare ) risSistemaTriangSup(A,B,X); return !singolare; } static boolean scambiaRiga( double [] [] A, double [] B, int i ) { boolean trovatoNonZero = false; for ( int j = i+1; j < A.length && !trovatoNonZero; j++ ) if ( A[i][j] != 0 ) { trovatoNonZero=true; double temp = B[i]; B[i]=B[j]; B[j]=temp; for (int k = i; k < A.length; k++) { temp = A[i][k]; A[i][k]=A[j][k]; A[j][k]=temp; } } return trovatoNonZero; }

Il metodo scambiaRiga ha una complessit (n) in quanto il for pi interno eseguito al pi una volta. Pertanto, poich la complessit del metodo risSistemaTriangSup (n2) come abbiamo gi mostrato precedentemente, la complessit del metodo risSistemaEquazioni determinata dalla istruzione asteriscata dentro i tre cicli di 'for' per cui essa (n3). L'algoritmo di risoluzione non ottimale poich esistono algoritmi che risolvono un sistema di equazioni in tempo (nk) con 2 < k < 3. Si noti che la complessit del problema (n2) in quanto la semplice scansione di tutti i coefficienti del sistema richiede un tempo quadratico. Tale limite pu essere abbattuto nel caso di matrici sparse (cio con un numero limitato di valori diversi da zero) tramite algoritmi ad hoc.

5. Compressione di una Matrice

Sia data una superficie piana di dimensioni X e Y. Supponiamo che la dimensione Y sia suddivisa in n parti uguali e quella X in m parti uguali - la superficie quindi rappresentabile da una griglia di n m celle rettangolari. Supponiamo ora di aver memorizzato un valore per ciascuna cella ad esempio, se la superficie unarea territoriale, il valore potrebbe essere la piovosit annuale. I valori possono essere rappresentati con una matrice A di dimensioni n m. Supponiamo di voler ora comprimere la rappresentazione della superficie attraverso una riduzione del numero di celle ad esempio delle celle iniziali. Possiamo quindi costruire una matrice compressa della superficie attraverso una matrice B di dimensioni ridotte, le cui celle hanno come valori le medie delle celle originarie compresse Ad esempio, data la matrice A di dimensioni 12 8:

la matrice con fattore di compressione 4 la matrice B di dimensione 3 2 : in quanto le sei celle di B rappresentano la compressione dei valori dei 6 gruppi di celle di A, come indicati di seguito: Utilizzando un fattore di compressione 3, la matrice B ha dimensione 4 3 e rappresenta i seguenti valori: rappresentano la compressione dei valori dei 12 gruppi di celle di A, come indicati di seguito::

Si noti che i 4 gruppi sul bordo destro hanno dimensione 3 2 in quanto lapplicazione del fattore di riduzione 3 al numero di colonne 8 d il valore 2,667 (arrotondato a 3). In alcuni casi pu essere richiesto che nella aggregazione di celle sia effettuata la somma dei valori piuttosto che la loro media ad esempio nel caso che i valori rappresentino la popolazione in una cella territoriale. Di seguito presentiamo un metodo che effettua la compressione a partire dalla matrice A, del fattore di compressione fC, che deve essere un intero maggiore di 1, e dallindicazione tramite il parametro S_M se si tratta di effettuare la somma (S_M = S) o la media altrimenti:

static double [][] compressione ( double [][] A, int fC, char S_M ) { int n = A.length; int m = A[0].length; int nc = (int) Math.ceil(n / (double) fC); //approssimazione per eccesso int mc = (int) Math.ceil(m / (double) fC); //approssimazione per eccesso double [][] B = new double[nc][mc]; for ( int i = 0; i < nc; i++ ) for ( int j = 0; j < mc; j++ ) B[i][j]=aggregazione(A,i*fC,j*fC, fC, S_M); return B; } static double aggregazione ( double[][] A, int i, int j, int fC, char S_M) { double somma =0; int nElem = 0; for ( int ic=i; ic<A.length && ic < i+fC; ic++) for ( int jc=j; jc<A[0].length && jc < j+fC; jc++) { somma += A[ic][jc]; nElem++; } if ( S_M == S ) return somma; else return somma/nElem; }

Il metodo aggregazione ha una complessit C = (fC2) a causa dei due for innestati, ciascuno ripetuto al pi fC volte. La complessit del metodo compressione ha complessit (nc mc C2); poich nc = n/fC, mc = m/fC, abbiamo (n m C2/ fC2). Quindi essendo C = (fC2), la complessit della compressione (n m) e quindi si tratta di un metodo ottimale in quanto per comprimere i valori di A necessario scorrerli tutti.

6. Punto di Sella di una Matrice

Sia data una matrice M bidimensionale n m. Un punto di sella un elemento M[i][j] di M tale che esso contemporaneamente il minimo elemento della riga i e il massimo elemento della colonna j. I generale una matrice pu avere 0, 1 o pi punti di sella. Il calcolo di un eventuale punto di sella di molto interesse nella Teoria dei Giochi che una disciplina che studia situazioni di competizione e di cooperazione tra due o pi soggetti (giocatori, decisori, operatori economici, produttori e consumatori di beni) razionali ed intelligenti. Come esempio di gioco con due soggetti (A e B) non cooperativo (cio A e B sono avversari) a somma zero (cio il guadagno di A e pari alla perdita di B e viceversa), supponiamo che lUniversit della Calabria abbia deciso di aprire due punti di vendita di snack sul ponte assegnandoli ai due soggetti, con il solo vincolo che ciascuno dei due punti di vendita sia allocato o a uno dei due estremi, o al centro, o a 1/4 del ponte o a 3/4 del ponte. I due soggetti presentano in busta chiusa la localizzazione prescelta. Il calcolo del punto di sella ci permette di prevedere quale saranno le scelte effettuate dai due soggetti. Il guadagno di A rappresentato dalla frazione di potenziale domanda che riuscir ad attrarre il suo punto di vendita. Si supponga che la domanda sia uniformemente distribuita sul ponte e che la scelta da parte dei clienti di un punto di vendita dipende dalla sua distanza. Ovviamente A cercher di massimizzare la frazione di domanda da lui servita. Al contrario B cercher di minimizzare tale frazione di domanda (e quindi massimizzare la sua frazione). Il problema pu essere formalizzato dalla matrice M di dimensioni 5 5, riportata di seguito, in cui sulle righe sono riportate tutte le possibili decisioni di A e sulle colonne quelle di B e i valori M[i][j] memorizzano la frazione di domanda catturata da A, se egli colloca il suo punto di vendita nella posizione i e contemporaneamente B colloca il suo punto di vendita nella posizione j. Ad esempio i valori della riga 0 riportano le frazioni di domanda per A nel caso di allocazione del suo punto di vendita allinizio del ponte per le varie scelte possibili per B: 1/2 se anche B posizione il suo punto vendita allinizio del ponte in tal caso si dividono la

domanda 1/8 se B posiziona il suo punto di vendita a 1/4 in tal caso tutti i clienti da 1/4 in poi vanno da B e quelli compresi tra 0 e 1/4 si dividono tra A e B 1/4 se B posiziona il suo punto di vendita a 1/2 in tal caso tutti i clienti da 1/2 in poi vanno da B e quelli compresi tra 0 e 1/2 si dividono tra A e B 3/8 se B posiziona il suo punto di vendita a 3/4 in tal caso tutti i clienti da 3/4 in poi vanno da B e quelli compresi tra 0 e 3/4 si dividono tra A e B 1/2 se B posiziona il suo punto di vendita alla fine del ponte in tal caso tutti i clienti si divideranno equamente tra i due punti di vendita. Allo stesso modo si calcolano i valori delle altre righe. Pertanto la matrice M : Avendo a disposizione M, il soggetto A calcoler per ogni riga i il valore minimo, che rappresenta la sua minima quota di mercato se dovesse decidere di allocare il punto vendita in i. La sua scelta allora ricadr sulla riga i che ha il valore minimo pi grande nella fattispecie la posizione i=2 a met del ponte. Anche B riesce a costruire la matrice M ma i suoi calcoli li far per colonna. Per ogni colonna j, egli calcola il valore massimo, che rappresenta la massima quota di mercato di A se B dovesse decidere di allocare il punto vendita in j. Poich egli vuole minimizzare la quota di mercato di A, la scelta di B ricadr sulla colonna j che ha il valore massimo pi piccolo nella fattispecie la posizione j=2 a met del ponte. Lelemento M[2][2] un punto di sella ( il minimo della riga 2 e il massimo della colonna 2) e costituisce la situazione di equilibrio, cio due soggetti A e B razionali e avversari alla fine opteranno per tale scelta.: entrambi posizioneranno il proprio punto di vendita a met del ponte. Per verificare che non ci sono altri punti di sella, riportiamo di seguito i valori minimi di riga e i valori massimi di colonna: Pur non essendoci altri punti di equilibrio, tuttavia esistono altre 8 scelte che permettono ai due avversari di suddividersi equamente le quote di mercato (cio valori della matrice pari a 1/2: a. entrambi collocano il punto di vendita alla stessa estremit del ponte (2 possibilit)

10

b. entrambi collocano il punto di vendita a 1/4 o a 3/4 del ponte (altre 2 possibilit) c. A colloca il suo punto di vendita ad una estremit e B allaltra (ulteriori 2 possibilit) d. A colloca il suo punto di vendita a 1/4 e B a 3/4 o viceversa (ultime 2 possibilit) E interessante notare che delle 8 altre possibilit, le ultime due (punto d) sono vantaggiose per la clientela in quanto riducono il totale degli spostamenti in effetti ogni cliente al massimo si dovr spostare di 1/4 di ponte per arrivare al punto di vendita mentre nella soluzione del punto di sella i clienti agli estremi dovranno percorrere met del ponte. Ma nonostante questo vantaggio, tale soluzione non sar scelta dai due soggetti spontaneamente il soggetto A non proporr la collocazione a 1/4 per timore che B scelga la collocazione a met. Lunico modo per pervenire alle soluzioni di cui al punto d che ci sia una regolamentazione da parte di un soggetto terzo, nel nostro caso lUniversit. Possiamo ora mostrare il metodo calcoloPuntiSella, che restituisce tutti gli eventuali punti di sella di una matrice. Il metodo riceve come parametro la matrice M, gli indici di riga (iPuntiSella) e gli indici di colonna (jPuntiSella) degli eventuali punti di sella e restituisce il numero di punti di sella. I due array iPuntiSella e jPuntiSella sono stati dimensionati dal metodo chiamante con n m elementi per il caso estremo che tutti gli elementi di M siano punti di sella. Il metodo calcoloPuntiSella restituisce il numero effettivo di punti di sella nel caso dellesempio dei due punti di vendita sul ponte dellUniversit, viene restituito 1 e i due array iPuntiSella e jPuntiSella contengono ciascuno un solo valore, in particolare iPuntiSella[0] = 2 e jPuntiSella[0] = 2, che stabiliscono che lunico punto di sella M[2][2].
static int calcoloPuntiSella ( double [][] M, int [] iPuntiSella, int [] jPuntiSella ) { int n = M.length; int m = M[0].length; double [] minRiga = new double[n]; for ( int i=0; i < n; i++) minRiga[i]=minimoRiga(M,i); double [] maxColonna = new double [m]; for ( int j=0; j < m; j++) maxColonna[j]=massimoColonna(M,j); int nPuntiSella = 0; for ( int i = 0; i < n; i++) for (int j =0; j < m; j++) if ( M[i][j] == minRiga[i] && M[i][j] == maxColonna[j]) { iPuntiSella[nPuntiSella]=i;jPuntiSella[nPuntiSella]=j; nPuntiSella++; } return nPuntiSella; } static double minimoRiga ( double[][] M, int i ) { double minimo =M[i][0]; for ( int j=1; j<M[0].length; j++) if ( M[i][j]<minimo) minimo = M[i][j]; return minimo; } static double massimoColonna ( double[][] M, int j ) { double massimo =M[0][j]; for ( int i=1; i<M.length; i++) if ( M[i][j]>massimo) massimo = M[i][j]; return massimo; }

E facile verificare che la complessit dellalgoritmo (n m), cio lalgoritmo ottimale non essendo in generale possibile calcolare i punti di sella senza consultare tutti i valori di M.

11