[Vari] Context 2: Ricerca

[gugoXX]

Sia data una matrice rettangolare mXn, preordinata per righe e per colonne.
Cio' significa che sia in ogni riga che in ogni colonna mi trovero' solo valori ascendenti.
Guardate l'esempio

http://img.photobucket.com/albums/v314/gugogugo/matrix.png

Quale e' la soluzione piu' efficiente per cercare se esiste almeno una volta un dato valore nella matrice? E se siamo in grado anche quale e' la complessita' della soluzione?

Es: Esiste 13 nella matrice?

________________________________

Matrice di prova
http://www.usaupload.net/d/y6jn9l2x9ap

Formato:
Comma spearated.
Prima riga: DimX, DimY
Righe Successive 15,17,19,22,27,....,1139,1150
etc.

Da provarsi con i seguenti valori:
[Non Presenti]
0
100
32538
20984
32767
[Presenti]
32539
26
11672
9790
14089

[shinya]

Umh... magari dico una cazzata... ma una ricerca binaria su righe prima e colonne poi potrebbe andare?

Del tipo (prendendo l'esempio):
parto dalla terza riga, terza colonna (9)
9 è minore di 13, quindi cerco (sempre ricerca binaria) nel sub-array verso destra.
lo trovo? no...
ricerca binaria sulla terza colonna, arrivo nella quarta riga, terza colonna (12)
è ancora minore di 13, cerco come sopra verso destra (se fosse stato maggiore lo avrei cercato a sinistra)

se esaurisco le righe non ho nessun risultato....

[gugoXX]

mmmh. Forse non ho capito bene.
Ma se il 13 fosse stato nella 2a riga, 7a colonna? L'avresti trovato?

[morskott]

forse dico una cavolata, se pensiamo la matrice come albero degenere ordinato la soluzione diventerebbe O(log(n)). nel senso che la root è il valore nel punto (0,0) che ha figli (1,0) e (0,1), (0,1) ha figli (0,2) e (1,1) mentre (1,0) ha figli (2,0) e (1,1). Così avremo che un nodo puo avere 2 padri (per questo l'albero è degenere) ma è crescente piu si scende, il che mi ricorda un Max-Heap il cui costo di ricerca è logaritmico sul numero dei nodi (si controlla la testa, se non è quella cercata si cancella e si crea una nuova testa come minimo dei figli e così via).
Al massimo per non fare l'albero degenere si sceglie un nodo a quale padre metterlo (casualmente).
Almeno è quello che ho pensato in 30 secondi netti. Domani a mente fresca magari mi viene in mente qualcosa di meglio

[beppegrillo]

Partendo dall'elemento M,N e iterando sulla colonna n, e riga m, escludendo tutti i valori minori di x. Dopo di che riduco il mio intervallo di ricerca alla sottomatrice individuata, escludendo da questa le colonne nelle quali x non è incluso.

[^TiGeRShArK^]

io dopo una quantità d'alcool che stenderebbe un elefante direi che bisogna innanzitutto partire dall'upper-left corner.
Poichè le righe e le colonne della mtrice sono crescenti in senso stretto, direi di proseguire lungo la diagonale principale della matrice fino a localizzare il numero precedente a quello cercato e il successivo (ovvero i due numeri che sulla diagonale siano rispettivamente minori e maggiori del numero cercato).
al terzo passo arriviamo a 9 e quindi subito dopo c'è il 15.
9 è minore di 13 e 15 è maggiore.
Perfetto.
Abbiamo trovato la riga o la colonna che potenzialmente contengono il nostro numero x.
A questo punto proseguirei, partendo dal numero 9 trovato lungo la diagonale, a destra seguendo la stessa riga dove si trova questo numero e in basso lungo la colonna che contiene il nostro numero 9.
poichè incontriamo i numeri 12 in entrambi le direzioni seguiti da un numero maggiore del numero x possiamo escludere che il numero trovato sia in questa direzione.
A questo punto, partendo dalla riga e dalla colonna i-esima - 1 e j-esima - 1 rispetto al numero 9 scandiamo le righe e le colonne a ritroso se e solo se il valore finale (i,N) (j,M) che esse presentano è minore di x.
Ovviamente si prosegue fino a scandire a ritroso tutte le righe e le colonne che alla posizione (i,N) (j,M) presentano un valore > x.
Non so se mi sono spiegato, ma così ad occhio dovrebbe andare... :stordita:
ma non chiedetemi di calcolare la complessità computazionale che al massimo ve la calcolo domani prima di andare al mare :Prrr:

P.S. i e j rappresentano la riga e la colonna del numero minore di x appena trovato lungo la diagonale, ovvero 9. :p

[^TiGeRShArK^]

Partendo dall'elemento M,N e iterando sulla colonna n, e riga m, escludendo tutti i valori minori di x. Dopo di che riduco il mio intervallo di ricerca alla sottomatrice individuata, escludendo da questa le colonne nelle quali x non è incluso.

Non ho capito il disegno... :stordita:
P.S. su 4 visite che ha ricevuto il tuo allegato a quest'ora 3 le ho fatte io tentando di capirci qualcosa...mi sa che è un problema di tutti gli informatici essere scarsini coi disegni :Prrr:

[^TiGeRShArK^]

Ora che ci penso, leggendo il post di shinya si aumenterebbe l'efficienza utilizzando una ricerca binaria tra l'indice finale della riga/colonna e andando a ritroso fino alla casella della diagonale che già sappiamo essere minore di x :p

[gugoXX]

Partendo dall'elemento M,N e iterando sulla colonna n, e riga m, escludendo tutti i valori minori di x. Dopo di che riduco il mio intervallo di ricerca alla sottomatrice individuata, escludendo da questa le colonne nelle quali x non è incluso.

Questo non funziona.
Se la matrice avesse avuto una colonna in piu', e se ci fosse stato il 13 nella seconda riga, non l'avresti trovato.

[shinya]

mmmh. Forse non ho capito bene.
Ma se il 13 fosse stato nella 2a riga, 7a colonna? L'avresti trovato?

No, non l'avrei trovato. Ok non funziona.

Però il metodo proposto da tigershark non l'ho mica capito... :fagiano:

edit: leggendo il post di morskott mi viene in mente che la matrice cosi definita può essere vista come un heap (max-heap se la root è l'elemento [M,N]).
Quindi 22 ha come figli 19 e 20. 19 ha come figli 18 e 17 e cosi via.
Magari aiuta pensarla in questi termini...
Cioè, si costruisce l'heap e si comincia a eliminare il nodo di valore massimo fino a che la root è maggiore di 13...umh...o forse no...

edit2:
ho buttato giù uno stralcio un pò tirato via in java basato su una priority queue (quella della libreria standard, che usa un heap al suo interno)... l'ho testato poco, ma sembra funzionicchiare...


import java.util.*;

public class Context2 {
public static void main(String[] args) {
List<Integer> m = Arrays.asList(1, 4, 7, 8, 9, 15, 2, 5, 8, 10, 11, 12, 5,
6, 9, 12, 14, 15, 7, 8, 12, 15, 17, 20, 8, 9, 17, 18, 19, 22);

PriorityQueue<Integer> p = new PriorityQueue<Integer>(11,
new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return -1 * o1.compareTo(o2);
}
});

for (int i : m)
p.add(i);

int guess = 13;
int elem;
do {
elem = p.poll();
if (elem == guess) {
System.out.println("Found!");
System.exit(0);
}
} while (elem > guess);

System.out.println("Not Found!");
}
}


si, non è il massimo dell'eleganza, me ne rendo conto...

[^TiGeRShArK^]

No, non l'avrei trovato. Ok non funziona.

Però il metodo proposto da tigershark non l'ho mica capito... :fagiano:

edit: leggendo il post di morskott mi viene in mente che la matrice cosi definita può essere vista come un heap (max-heap se la root è l'elemento [M,N]).
Quindi 22 ha come figli 19 e 20. 19 ha come figli 18 e 17 e cosi via.
Magari aiuta pensarla in questi termini...
Cioè, si costruisce l'heap e si comincia a eliminare il nodo di valore massimo fino a che la root è maggiore di 13...umh...o forse no...

provo a rispiegarlo... :stordita:
si applica una ricerca binaria sulla diagonale e si ricavano le posizioni del numero rispettivamente + piccolo e + grande di x (se x non è presente nella diagonale).
Si memorizzano in due variabili, i e j, la riga e la colonna che contengono il numero immediatamente inferiore ad x sulla diagonale.
a questo punto, poichè nei "bordi" inferiore e destro della matrice si trovano i numeri massimi di tutta la riga e di tutta la colonna si esamina il bordo inferiore della riga i-esima e il bordo destro della riga j-esima.
Se il numero presente nelle due caselle appena analizzate è maggiore di x si inizia a scandire a ritroso la riga e la colonna, dal bordo verso il centro, sempre tramite ricerca binaria prendendo come estremi la riga m e la riga i e la casella n e la colonna j.
e si continua così fino a che sui bordi non si incontra un numero minore di x.
Mi sa che però faccio prima a scrivere uno pseudo-codice (con una ricerca semplice perchè non mi voglio complicare la vita a scrivere quella binaria) che si dovrebbe capire meglio il funzionamento.. :stordita:

x = numero incognito
matrix[m, n] = matrice

int i = 0;
int j = 0;

while (matrix[i, j] <= x && i < m && j < n) {
i++;
j++;
}

if (matrix[i, j] == x) {
found();
}


a = i;
b = j;

while (matrix[m, j] > x && matrix[i, n] > x) {
for (int u = m; u > a; u--) {
if (matrix[u, j] == x)
found();
}

for (int v = n; v > b; v--) {
if (matrix[i, v] == x)
found();
}

i--;
j--;
}


notFound();


La complessità della prima ricerca applicando l'algoritmo senza ricerca binaria dovrebbe essere O(sqrt(n^2 + m^2)) che per una matrice quadrata vale O(n * sqrt(2)) e che quindi nel nostro caso di matrice generica vale O(h), con h il lato minore tra m ed n. Applicando la ricerca binaria dovrebbe avere complessità O(log(h)) se non ricordo male la complessità di tale ricerca. :p
Per l'altra parte dell'algoritmo ora come ora mi sfugge la complessità... :stordita:
Ad occhio si può calcolare, ma ancora ho il neurone troppo spento mi sa :fagiano:

P.S. spero che così si capisca.. :stordita:

[marco.r]

L'idea della ricerca binaria e' buona, pero' secondo me va portato "all'estremo".
Quando trovi la posizione del numero sulla diagonale ("n"), a quel punto puoi dividere la matrice in quattro sottomatrici. quella con righe e colonne strettamente inferiori ad 'n'. Quella con solo le righe strettamente inferiori, quella con solo le colonne strettamente inferiori, e la rimanente.
Le due matrici che stanno sulla diagonale le possiamo escludere, in quanto siamo sicuri al 100% che contengono una tutti valori inferiori a quello cercato, l'altra tutti superiori.
A questo punto ci rimangono due sottomatrici a cui possiamo applicare l'algoritmo ricorsivamente.

Se mi dai qualche minuto posto anche del codice di esempio

[^TiGeRShArK^]

L'idea della ricerca binaria e' buona, pero' secondo me va portato "all'estremo".
Quando trovi la posizione del numero sulla diagonale ("n"), a quel punto puoi dividere la matrice in quattro sottomatrici. quella con righe e colonne strettamente inferiori ad 'n'. Quella con solo le righe strettamente inferiori, quella con solo le colonne strettamente inferiori, e la rimanente.
Le due matrici che stanno sulla diagonale le possiamo escludere, in quanto siamo sicuri al 100% che contengono una tutti valori inferiori a quello cercato, l'altra tutti superiori.
A questo punto ci rimangono due sottomatrici a cui possiamo applicare l'algoritmo ricorsivamente.

Se mi dai qualche minuto posto anche del codice di esempio
che è + o - quello che ho proposto io spiegato molto meglio se non ho capito male.. :stordita:

[marco.r]

def positionOfGreatestLowerOrEqualThan( matrix, value, rowmin, colmin, rowmax,colmax ):
i = rowmin
j = colmin
while i < rowmax and j < colmax and matrix[i][j] <= value:
i+=1
j+=1
return [i,j]


def findNumber( matrix, value, rowmin, colmin, rowmax, colmax ):
if rowmin == rowmax or colmin == colmax:
return False
[i,j] = positionOfGreatestLowerOrEqualThan( matrix, value, rowmin, colmin, rowmax, colmax )

if matrix[i-1][j-1] == value:
return [i-1,j-1]

return findNumber( matrix, value, rowmin, j, i, colmax ) or findNumber( matrix, value, i, colmin, rowmax, j )

Per pigrizia la ricerca sulla diagonale l'ho fatta lineare, ma basta modificare la prima funzione :p.

[marco.r]

Per inciso, per l'autore del thread: forse nel titolo intendevi dire "contest" ? :confused:

[marco.r]

che è + o - quello che ho proposto io spiegato molto meglio se non ho capito male.. :stordita:

Sorry non avevo capito... e' sabato anche per me (stavo per dire "sabato mattina... :asd:)

[gugoXX]

Non ho ancora letto le soluzioni, e mi paiono promettenti.
Forse c'e' ancora qualcosina da aggiustare.
Provate ad applicare gli algoritmi anche a questo esempio

http://img.photobucket.com/albums/v314/gugogugo/Ex2.gif

In cui ci sia da trovare il 10, il 12 oppure il 24

[morskott]

Una soluzione che almeno nel caso di test funziona èimport java.util.*;

public class CercaNumero{
private static int h(int curr,int numero){
return numero-curr;
}

public static boolean isInConAStar(int[][] matrice,int numero){
class Coppia implements Comparable<Coppia>{
int i,j;
int goodness;

Coppia(int i,int j,int goodness){
this.i=i;
this.j=j;
this.goodness=goodness;
}

public int compareTo(Coppia c){
return this.goodness-c.goodness;
}

public boolean equals(Object o){
if (o!=null && this.getClass().equals(o.getClass())){
Coppia c=(Coppia)o;
return this.i==c.i && this.j==c.j;
}else
return false;
}

public int hashCode(){
return this.i+31*this.j;
}
}
SortedSet<Coppia> frontiera=new TreeSet<Coppia>();
frontiera.add(new Coppia(0,0,h(matrice[0][0],numero)));
while(!frontiera.isEmpty()){
Coppia current=frontiera.first();
if (matrice[current.i][current.j]==numero) return true;
System.out.println("Visistato il numero:"+String.valueOf(matrice[current.i][current.j]));
frontiera.remove(current);
int goodness_i=-1;
int goodness_j=-1;
try{
goodness_i=h(matrice[current.i+1][current.j],numero);
} catch(ArrayIndexOutOfBoundsException ex){};
try{
goodness_j=h(matrice[current.i][current.j+1],numero);
} catch(ArrayIndexOutOfBoundsException ex){};
if (goodness_i>=0){
if (goodness_j>=0){
frontiera.add(new Coppia(current.i,current.j+1,goodness_j));
frontiera.add(new Coppia(current.i+1,current.j,goodness_i));
}else{
frontiera.add(new Coppia(current.i+1,current.j,goodness_i));
}
}else{
if (goodness_j>=0){
frontiera.add(new Coppia(current.i,current.j+1,goodness_j));
}
}
}
return false;
}

public static void main(String[] args){
int[][] matrice=new int[3][3];
matrice[0][0]=1;
matrice[0][1]=4;
matrice[0][2]=7;
matrice[1][0]=2;
matrice[1][1]=5;
matrice[1][2]=8;
matrice[2][0]=5;
matrice[2][1]=6;
matrice[2][2]=9;

int numeroEsistente=8;
int numeroMinoreNonEsistente=3;
int numeroMaggioreNonEsistente=19;

boolean conNumeroEsistente=isInConAStar(matrice,numeroEsistente);
System.out.println("Finita prima ricerca");
boolean conNumeroNonEsistenteMinore=isInConAStar(matrice,numeroMinoreNonEsistente);
System.out.println("Finita seconda ricerca");
boolean conNumeroNonEsistenteMaggiore=isInConAStar(matrice,numeroMaggioreNonEsistente);
System.out.println("Finita terza ricerca");

System.out.println("A* - Con numero esistente:"+String.valueOf(conNumeroEsistente)+" - con numero non esistente minore:"+String.valueOf(conNumeroNonEsistenteMinore)+" - con numero non esistente maggiore:"+String.valueOf(conNumeroNonEsistenteMaggiore));
}
}nel secondo caso di test quando ci metto un numero che non esiste nella matrice minore del massimo ci mette solo 2 iterazioni a scoprire che non esiste

UPDATE: qualcuno me lo tradurrebbe in python che son curioso di vedere come esce?? Devo ancora calcolarci la complessità, che ad occhio sembra essere sublineare

[beppegrillo]

Questo non funziona.
Se la matrice avesse avuto una colonna in piu', e se ci fosse stato il 13 nella seconda riga, non l'avresti trovato.

puoi farmi un esempio della matrice con i valori?

[^TiGeRShArK^]

Sorry non avevo capito... e' sabato anche per me (stavo per dire "sabato mattina... :asd:)

no, mi sa che sono diversi, avevo capito male io :asd:

[^TiGeRShArK^]

ecco il mio algoritmo in C# con qualche bug fix rispetto allo pseudo-codice di cui sopra :p

class Prova
{
int x = 10;

public Prova()
{
string notFound = string.Format("Il numero {0} non è stato trovato.", x);
string found = string.Format("Trovato il numero {0}.", x);
int[,] matrix = { {1, 4, 7, 8, 9, 11, 12},
{2, 5, 8, 18, 22, 23, 25},
{5, 6, 9, 19, 25, 25, 26},
{8, 13, 13, 20, 27, 28, 29},
{10, 15, 18, 22, 29, 20, 35}};
int m = matrix.GetLength(0) - 1;
int n = matrix.GetLength(1) - 1;
int i = 0;
int j = 0;

while (matrix[i, j] <= x && i < m && j < n)
{
i++;
j++;
}
i--;
j--;
if (matrix[i, j] == x)
{
exit(found);
}

int a = i;
int b = j;
while (matrix[m, j] >= x || matrix[i, n] >= x || i > 0)
{
for (int u = m; u > a; u--)
{
if (matrix[u, j] == x)
exit(found);
}

for (int v = n; v > b; v--)
{
if (matrix[i, v] == x)
exit(found);
}
i--;
j--;
}

exit(notFound);
}

private static void exit(string message)
{
Console.WriteLine(message);
Console.ReadLine();
Environment.Exit(0);
}

static void Main(string[] args)
{
new Prova();
}
}

con il secondo caso funziona trovando i numeri 10 e 12 e non trovando il 24.
Ma nel secondo caso c'è una peculiarità che non era presente nel primo requisito, o che almeno mi era sfuggito, ovvero che la cella a destra o la cella inferiore possa avere un valore uguale alla cella corrente, mentre io avevo capito che dovessero essere strettamente crescenti :p

[71104]

scusate, non ho minimamente letto il thread, ma affascinato dal problema voglio provare la mia soluzione :D

se non vi spiace la scrivo in C#


class MatrixTest
{
static int[,] Matrix =
{
{1, 4, 7, 8, 9, 11},
{2, 5, 8, 10, 11, 12},
{5, 6, 9, 12, 14, 15},
{7, 8, 12, 15, 17, 20},
{8, 9, 17, 18, 19, 20},
};

static bool[,] Auxiliary = new bool[Matrix.GetLength(0), Matrix.GetLength(1)];

static void Initialize()
{
for (int i = 0; i < Auxiliary.GetLength(0); i++)
{
for (int j = 0; j < Auxiliary.GetLength(1); j++)
{
Auxiliary[i, j] = true;
}
}
}

static bool Exists(int Value, int x, int y)
{
if (!Auxiliary[y, x])
{
return false;
}

if (Matrix[y, x] == Value)
{
return true;
}

if (x + 1 < Matrix.GetLength(1))
{
if (Matrix[y, x + 1] <= Value)
{
if (Exists(Value, x + 1, y))
{
return true;
}
}
}

if (y + 1 < Matrix.GetLength(0))
{
if (Matrix[y + 1, x] <= Value)
{
if (Exists(Value, x, y + 1))
{
return true;
}
}
}

Auxiliary[y, x] = false;
return false;
}

static bool Exists(int Value)
{
Initialize();
return Exists(Value, 0, 0);
}

static void Main(string[] Arguments)
{
for (int i = 1; i <= 20; i++)
{
if (Exists(i))
{
System.Console.WriteLine(i + " is present");
}
else
{
System.Console.WriteLine(i + " isn\'t present");
}
}
}
}

[71104]

ho provato il mio programma usando la matrice di TigerShark, funziona.

[gugoXX]

Posso gentilmente chiedervi se potete adoperare una classe matrice tipo questa
Oppure se comunque potete tenere il conto di tutte le volte che leggete un valore dalla matrice (anche per confronti, in qualsiasi caso)
cosi' possiamo poi confrontare i numeri di letture e in qualche modo dedurne la complessita' anche senza valutare l'algoritmo.

Sto preparando 2 belle matricione, una 250x200, l'altra 8.000x10.000.
sara' un file di testo comma separated.
prima riga: numero colonne,numero righe
righe successive: 5,6,90,150,...
i valori sono da intendersi interi positivi.

La set dei valori l'ho piazzata solo nel caso in cui la usassimo per caricare i dati dall'esterno.

// Modificate pure a piacere, l'importante e' il conteggio dei get.
public class Matrix
{
int[,] matrix = { {1, 4, 7, 8, 9, 11, 12},
{2, 5, 8, 18, 22, 23, 25},
{5, 6, 9, 19, 25, 25, 26},
{8, 13, 13, 20, 27, 28, 29},
{10, 15, 18, 22, 29, 20, 35}};

public int GetCount = 0;

public int this[int y,int x]
{
get
{
GetCount++;
return matrix[y,x];
}
set
{
matrix[y, x] = value;
}
}
}

[^TiGeRShArK^]

ho provato il mio programma usando la matrice di TigerShark, funziona.

mmm..
ma non c'è un modo per inizializzare la matrice di booleani direttamente a true?
in quel modo hai complessità O(m*n) solo per l'inizializzazione di Auxiliary :stordita:

[gugoXX]

Per i pigroncelli, in C# la classe Matrice potrebbe essere qualcosa tipo questa
compresa la lettura da file.

public class Matrix
{
int[,] matrix = null;
public Matrix(int y, int x)
{
matrix = new int[y, x];
}

public Matrix(StreamReader sr)
{
string dimrow = sr.ReadLine();
string[] dimstrings = dimrow.Split(',');
if (dimstrings.Length != 2) throw new Exception("Head Error");
int dx = int.Parse(dimstrings[0]);
int dy = int.Parse(dimstrings[1]);
matrix = new int[dy, dx];
for (int row = 0; row < dy; row++)
{
string rowstring = sr.ReadLine();
string[] valoristringa = rowstring.Split(',');
if (valoristringa.Length != dx) throw new Exception(string.Format("Record Error: {0}", row));
var convertiti = valoristringa.Select((t,index) => new{ index=index, val=int.Parse(t)} );
convertiti.ToList().ForEach(t => matrix[row,t.index]=t.val );
}
}

public int GetCount = 0;

public int GetLength(int dimension)
{
return matrix.GetLength(dimension);
}

public int this[int y,int x]
{
get
{
GetCount++;
return matrix[y,x];
}
}
}


e questo il contenuto del file di prova di base

7,5
1, 4, 7, 8, 9, 11, 12
2, 5, 8, 18, 22, 23, 25
5, 6, 9, 19, 25, 25, 26
8, 13, 13, 20, 27, 28, 29
10, 15, 18, 22, 29, 30, 35

[shinya]

Non ho ancora letto le soluzioni, e mi paiono promettenti.
Forse c'e' ancora qualcosina da aggiustare.
Provate ad applicare gli algoritmi anche a questo esempio

http://img.photobucket.com/albums/v314/gugogugo/Ex2.gif

In cui ci sia da trovare il 10, il 12 oppure il 24

Con l'ultima matrice che hai dato il mio codice con l'heap funziona... l'ho snellito un attimo...


import java.util.*;

public class Contest2 {
public static void main(String[] args) {
List<Integer> values = Arrays.asList(1, 4, 7, 8, 9, 11, 12,
2, 5, 8, 18, 22, 23, 25,
5, 6, 9, 19, 25, 25, 26,
8, 13, 13, 20, 27, 28, 29,
10, 15, 18, 22, 29, 30, 35);

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(values);
int [] tests = {10, 12, 24};
for (int i : tests) search(pq, i);
}

private static void search(PriorityQueue<Integer> pq, int guess) {
int elem;
do {
elem = pq.poll();
if (elem == guess) {
System.out.println("Found " + guess);
return;
}
} while (elem < guess);

System.out.println(guess + " not found! :(");
}
}

Output:
Found 10
Found 12
24 not found! :(


Probabilmente la soluzione proposta da tigershark però è più efficiente, sto cercando di capirla rileggendo i post :)

[gugoXX]

Con l'ultima matrice che hai dato il mio codice con l'heap funziona... l'ho snellito un attimo...


La complessita' di questo algoritmo e' quadratica non e' vero?
E' una O(N*M).
Diciamo triangolare
O(N*M/2)
Anzi, mediamente meno, O(N*M/4)

vero?

Riesci a calcolare quante celle leggi prima di dire il risultato?

[^TiGeRShArK^]

per il numero 10 ho 21 letture, per il numero 12 24 letture e per il 24 26 letture.
Questo perchè avevo fatto un paio di cappellate e facevo delle letture inutili tanto perchè ero masochista :D
Ora ho 18 letture per i numeri trovati e 19 per quello non trovato.
Tutto questo utilizzando la ricerca lineare e non quella binaria :p
e secondo me ancora faccio ancora una lettura inutile perchè contando a mano dovrei metterci 17 passi per trovare il 10, mentre ce ne metto 18 con l'implementazione attuale :D
EDIT: ora vedo di implementare la ricerca binaria :p

[shinya]

Riesci a calcolare quante celle leggi prima di dire il risultato?

Edit: no scusate scusate, avevo sbagliato tutto...
Questo è l'output corretto:

Found 10 in 13 steps.
Found 12 in 15 steps.
24 not found in 26 steps.


e questo il codice...quello di prima era sbagliato, funzionava per caso. Rimuovevo elementi dall'heap e usavo il resto per calcolare gli altri test.


import java.util.*;

public class Contest2 {
public static void main(String[] args) {
List<Integer> values = Arrays.asList(1, 4, 7, 8, 9, 11, 12,
2, 5, 8, 18, 22, 23, 25,
5, 6, 9, 19, 25, 25, 26,
8, 13, 13, 20, 27, 28, 29,
10, 15, 18, 22, 29, 30, 35);

int [] tests = {10, 12, 24};
for (int i : tests) search(values, i);
}

private static void search(List<Integer> values, int guess) {
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(values);
int elem;
int guessing = 0;
do {
elem = pq.poll();
guessing++;
if (elem == guess) {
System.out.println("Found " + guess + " in " + guessing + " steps.");
return;
}
} while (elem < guess);

System.out.println(guess + " not found in " + guessing + " steps.");
}
}

[gugoXX]

Edit: no scusate scusate, avevo sbagliato tutto...
Questo è l'output corretto:

Found 10 in 13 steps.
Found 12 in 15 steps.
24 not found in 26 steps.


Shinya scusa, ma la priority queue nel costruttore non ordina tutta l'enumerazione?
Se la ordina tutta significa che leggi tutti gli elementi almeno una volta.
Per leggerla tutta ti fermi li'... cerchi se c'e' il valore.

[shinya]

Si hai ragione, li legge tutti per forza...fa cagare cosi...

[morskott]

Aggiunta una piccola interfaccetta grafica, la matrice si puo sia scrivere nell'interfaccetta che caricare da file, il formato deve essere per esempio
matrice
numero da cercare,per esempio1 4 7
2 5 8
5 6 9
6 l'ho provato scrivendo a mano i valori ma non caricando il file (ma dovrebbe funzionare anche in questo caso), il codice èimport java.util.*;
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.io.*;

public class CercaNumero extends JFrame{
private JTextArea matriceJTA;
private JLabel risJL;
private JLabel numValutatoJL;

public CercaNumero(){
Container cpain=this.getContentPane();
matriceJTA=new JTextArea();
JScrollPane jsp=new JScrollPane();
JPanel jpa=new JPanel();
jpa.add(matriceJTA);
jsp.add(jpa);
this.setLayout(new BorderLayout());
JButton caricaDaFileJB=new JButton("Valuta da File");
caricaDaFileJB.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent e){
caricaDaFile();
}
});
cpain.add(matriceJTA,BorderLayout.CENTER);
JPanel buttonsJP=new JPanel();
buttonsJP.add(caricaDaFileJB);
JButton caricaDaTextJB=new JButton("Valuta matrice scritta");
caricaDaTextJB.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent e){
caricaDaText();
}
});
buttonsJP.add(caricaDaTextJB);
risJL=new JLabel();
cpain.add(buttonsJP,BorderLayout.NORTH);
JPanel south=new JPanel();
numValutatoJL=new JLabel();
south.add(new JLabel("Numero valutato:"));
south.add(numValutatoJL);
south.add(new JLabel("Risultato:"));
south.add(risJL);
cpain.add(south,BorderLayout.SOUTH);
this.setSize(300,200);
this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
}

private void caricaDaFile(){
String nomeFile=JOptionPane.showInputDialog("Inserisci il nome del file");
try{
FileInputStream fis=new FileInputStream(nomeFile);
InputStreamReader isr=new InputStreamReader(fis);
BufferedReader br=new BufferedReader(isr);

String matrix=br.readLine();
String input;
while((input=br.readLine())!=null) matrix+="\n"+input;
boolean ris=calcola(matrix);
risJL.setText(String.valueOf(ris));

br.close();
isr.close();
fis.close();
}catch(Exception ex){}
}

private void caricaDaText(){
boolean ris=calcola(matriceJTA.getText());
risJL.setText(String.valueOf(ris));
}

private boolean calcola(String mat){
StringTokenizer st=new StringTokenizer(mat,"\n");
java.util.List<String> righe=new LinkedList<String>();
while(st.hasMoreTokens()){
String tmp=st.nextToken();
righe.add(tmp);
}
int[][] matrix=new int[righe.size()-1][];
for (int i=0;i<matrix.length;i++){
String intRiga=righe.get(i);
StringTokenizer st1=new StringTokenizer(intRiga);
matrix[i]=new int[st1.countTokens()];
for (int j=0;j<matrix[i].length;j++){
matrix[i][j]=Integer.parseInt(st1.nextToken());
}
}
int numero=Integer.parseInt(righe.get(righe.size()-1));
numValutatoJL.setText(String.valueOf(numero));
stampaMatrice(matrix);
return isInConAStar(matrix,numero);
}

private static int h(int curr,int numero){
return numero-curr;
}

private static void stampaMatrice(int[][] matrix){
for (int i=0;i<matrix.length;i++){
System.out.println(Arrays.toString(matrix[i]));
}
}

public static boolean isInConAStar(int[][] matrice,int numero){
class Coppia implements Comparable<Coppia>{
int i,j;
int goodness;

Coppia(int i,int j,int goodness){
this.i=i;
this.j=j;
this.goodness=goodness;
}

public int compareTo(Coppia c){
return this.goodness-c.goodness;
}

public boolean equals(Object o){
if (o!=null && this.getClass().equals(o.getClass())){
Coppia c=(Coppia)o;
return this.i==c.i && this.j==c.j;
}else
return false;
}

public int hashCode(){
return this.i+31*this.j;
}
}
SortedSet<Coppia> frontiera=new TreeSet<Coppia>();
frontiera.add(new Coppia(0,0,h(matrice[0][0],numero)));
while(!frontiera.isEmpty()){
Coppia current=frontiera.first();
if (matrice[current.i][current.j]==numero) return true;
System.out.println("Visistato il numero:"+String.valueOf(matrice[current.i][current.j]));
frontiera.remove(current);
int goodness_i=-1;
int goodness_j=-1;
try{
goodness_i=h(matrice[current.i+1][current.j],numero);
} catch(ArrayIndexOutOfBoundsException ex){};
try{
goodness_j=h(matrice[current.i][current.j+1],numero);
} catch(ArrayIndexOutOfBoundsException ex){};
if (goodness_i>=0){
if (goodness_j>=0){
frontiera.add(new Coppia(current.i,current.j+1,goodness_j));
frontiera.add(new Coppia(current.i+1,current.j,goodness_i));
}else{
frontiera.add(new Coppia(current.i+1,current.j,goodness_i));
}
}else{
if (goodness_j>=0){
frontiera.add(new Coppia(current.i,current.j+1,goodness_j));
}
}
}
return false;
}

public static void main(String[] args){
int[][] matrice=new int[3][3];
matrice[0][0]=1;
matrice[0][1]=4;
matrice[0][2]=7;
matrice[1][0]=2;
matrice[1][1]=5;
matrice[1][2]=8;
matrice[2][0]=5;
matrice[2][1]=6;
matrice[2][2]=9;

int numeroEsistente=6;
int numeroMinoreNonEsistente=3;
int numeroMaggioreNonEsistente=19;

boolean conNumeroEsistente=isInConAStar(matrice,numeroEsistente);
System.out.println("Finita prima ricerca");
boolean conNumeroNonEsistenteMinore=isInConAStar(matrice,numeroMinoreNonEsistente);
System.out.println("Finita seconda ricerca");
boolean conNumeroNonEsistenteMaggiore=isInConAStar(matrice,numeroMaggioreNonEsistente);
System.out.println("Finita terza ricerca");

System.out.println("A* - Con numero esistente:"+String.valueOf(conNumeroEsistente)+" - con numero non esistente minore:"+String.valueOf(conNumeroNonEsistenteMinore)+" - con numero non esistente maggiore:"+String.valueOf(conNumeroNonEsistenteMaggiore));
CercaNumero cn=new CercaNumero();
cn.setVisible(true);
}
}fa prima una prova con una matrice standard e numeri già fissati e poi inizializza la grafica, quando si carica la matrice sia da file che scrivendola on the fly la stampa su console e stampa sempre su console ogni numero che visita. Tutte quelle righe son piu per scrivere la GUI e per passare da una rappresentazione stringa ad una matriciale che per l'algoritmo vero e proprio.

Ho preso in prestito un metodo utilizzato in intelligenza artificiale!! (Albero A*)

[gugoXX]

Ho messo sul primo post un collegamento ad una matrice 250 x 200
Sto gettando giu' l'algoritmo anche io. Per ora ho fatto il contorno, che mi e' servito per creare la mattrice e per trovare i valori di test, anch'essi nel primo post.

-----------------------------------------------
- Matrix Dimensions: 250, 200
- MinimumValue: 26
- MaximumValue: 32539
- CheckIpothesis: True
- Minimo non esistente 0
- Massimo non esistente 32538
- Mediana non esistente 20985
-----------------------------------------------

[gugoXX]

Azz stiamo andando anche sui metodi AI?
Pensavo di introdurre stimoli per algortmi Greedy in qualche Contest piu' avanti, eventualmente risolvibile con tecniche di AI (Scritto giusto stavolta, che vergogna)
Penso che per questo mi limitero' ad una ricerca normale.

[shinya]

Si credo che A* in questo contesto dovrebbe essere illegale...

Credo che la soluzione postata da marco sia la migliore (e la più elegante anche...).

[morskott]

Azz, ho provato con i primi numeri esistenti e me li trovava abbastanza velocemente, appena ho messo su 11672 entravo in un ciclo infinito!!! (che ad occhio è impossibile, l'algoritmo che uso deve (ha la caratteristica di) terminare sempre!!!! (e non venitemi a dire che il problema della terminazione è indecidibile:O )) Domani faccio un po di debug ragionato (la funzione core è "isInConAStar").

Per spiegare l'algoritmo in 3 parole ho un Set di indici che voglio considerare, all'inizio lo inizializzo con solo l'elemento a posizione (0,0), controllo se quell'elemento è quello cercato (se si torno subito true) sennò lo rimuovo e applico una funzione di goodness all'elemento appena sotto e a quello appena a destra (una banale distanza tra il numero cercato e il valore considerato), se l'indice è negativo (ho sforato la matrice o l'elemento è maggiore) non faccio niente sennò inserisco le coordinate nel set di indici e continuo il ciclo finchè il set non mi si svuota. Non considero mai 2 volte lo stesso elemento (anzi, quelli piu grandi non li tocco proprio) e ad ogni iterazione tolgo un elemento dal set, quindi come mai non termina???? Misteri della programmazione!!!

[morskott]

Si credo che A* in questo contesto dovrebbe essere illegale...

Credo che la soluzione postata da marco sia la migliore (e la più elegante anche...).

Perchè illegale? è sempre un algoritmo che sfrutta l'ordine della matrice e che (credo, non l'ho dimostrato formalmente) ad intuito sia sublineare di costo, se solo terminasse la mia implementazione.......(vedi post sopra)

[shinya]

Perchè illegale?

Dai era per fare una battuta :p

[gugoXX]

Ecco, ci sono, per ora posto un output castrato.
Forse riesco a migliorare ancora un pochino, ma non sono convinto
Non metto il numero di letture da matrice per ora, per non svelare le carte.

Quella di Marco mi piace. Mi piacerebbe vederla all'opera sul matricione.
Quella di morskott dovrei vederla con piu' calma, vediamo anche i risultati e il numero di letture da matrice.
Consiglio anche a te di fare in Java la classe matrice, per far contare a lei il numero di volte che si fa una get di una cella.
Anche Tiger e 71104 mi piacerebbe vedere i risultati sul matricione.


0 : Not Found

100 : Not Found

32538 : Not Found

20984 : Not Found

32767 : Not Found

32539 : Found - Coords 248,199

26 : Found - Coords 0,0

11672 : Found - Coords 248,0

9790 : Found - Coords 0,199

14089 : Found - Coords 87,110

[^TiGeRShArK^]

Ecco, ci sono, per ora posto un output castrato.
Forse riesco a migliorare ancora un pochino, ma non sono convinto
Non metto il numero di letture da matrice per ora, per non svelare le carte.

Quella di Marco mi piace. Mi piacerebbe vederla all'opera sul matricione.
Quella di morskott dovrei vederla con piu' calma, vediamo anche i risultati e il numero di letture da matrice.
Consiglio anche a te di fare in Java la classe matrice, per far contare a lei il numero di volte che si fa una get di una cella.
Anche Tiger e 71104 mi piacerebbe vedere i risultati sul matricione.

si vabbè....ma così non vale :asd:
dicci almeno in che ordine di grandezza sei con il tuo algoritmo :O
io i limiti del mio con la ricerca binaria + o - li so, se vedo che il tuo è migliore già in partenza nemmeno mi metto ad implementarla la ricerca binaria che mi rompo le bolls :p
Comunque finora il + elegante postato mi sembra essere quello di marco...
X il + prestante in effetti ancora ho qualche dubbio...
a parte quello tuo che è completamente incognito :p

[^TiGeRShArK^]

Doppio..:mbe:

[^TiGeRShArK^]

Triplo....:rolleyes:

[Vincenzo1968]

Questa è, per il momento, la mia soluzione:


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace Matrix
{
public class Matrix
{
private int _NumRows;
private int _NumCols;

int[,] matrix = null;

public Matrix(int y, int x)
{
matrix = new int[y, x];
}

public Matrix(StreamReader sr)
{
string dimrow = sr.ReadLine();
string[] dimstrings = dimrow.Split(',');

if (dimstrings.Length != 2)
throw new Exception("Head Error");

_NumCols = int.Parse(dimstrings[0]);
_NumRows = int.Parse(dimstrings[1]);

matrix = new int[_NumRows, _NumCols];

for (int row = 0; row < _NumRows; row++)
{
string rowstring = sr.ReadLine();
string[] valoristringa = rowstring.Split(',');
if (valoristringa.Length != _NumCols)
throw new Exception(string.Format("Record Error: {0}", row));
var convertiti = valoristringa.Select((t, index) => new { index = index, val = int.Parse(t) });
convertiti.ToList().ForEach(t => matrix[row, t.index] = t.val);
}
}

public int GetCount = 0;

public int GetLength(int dimension)
{
return matrix.GetLength(dimension);
}

public int NumRows
{
get
{
return _NumRows;
}
}

public int NumCols
{
get
{
return _NumCols;
}
}

public int this[int y, int x]
{
get
{
GetCount++;
return matrix[y, x];
}
}
}

class Program
{
static public bool RicercaBinaria(Matrix mtx, int k, out int riga, out int colonna)
{
int b, a, m;
int r = 0;

riga = colonna = -1;

while (r < mtx.NumRows)
{
b = 0;
a = mtx.NumCols - 1;

while (b <= a)
{
m = (b + a) / 2;
if (k < mtx[r, m])
a = m - 1;
else if (k > mtx[r, m])
b = m + 1;
else
{
riga = r;
colonna = m;
return true; // Trovato
}
}
++r;
}

return false;
}

static void Main(string[] args)
{
StreamReader sr = new StreamReader(@"C:\Scaricamenti\Temp\MatProva_250_200.txt");
Matrix mt = new Matrix(sr);

Console.WriteLine();

int riga, colonna;

int k = 0;

if ( RicercaBinaria(mt, k, out riga, out colonna) )
Console.WriteLine(k + " Trovato! Coord " + riga + ", " + colonna);
else
Console.WriteLine(k + " Non trovato!");

k = 100;
if (RicercaBinaria(mt, k, out riga, out colonna))
Console.WriteLine(k + " Trovato! Coord " + riga + ", " + colonna);
else
Console.WriteLine(k + " Non trovato!");

k = 32538;
if (RicercaBinaria(mt, k, out riga, out colonna))
Console.WriteLine(k + " Trovato! Coord " + riga + ", " + colonna);
else
Console.WriteLine(k + " Non trovato!");

k = 20984;
if (RicercaBinaria(mt, k, out riga, out colonna))
Console.WriteLine(k + " Trovato! Coord " + riga + ", " + colonna);
else
Console.WriteLine(k + " Non trovato!");

k = 32767;
if (RicercaBinaria(mt, k, out riga, out colonna))
Console.WriteLine(k + " Trovato! Coord " + riga + ", " + colonna);
else
Console.WriteLine(k + " Non trovato!");

k = 32539;
if (RicercaBinaria(mt, k, out riga, out colonna))
Console.WriteLine(k + " Trovato! Coord " + riga + ", " + colonna);
else
Console.WriteLine(k + " Non trovato!");

k = 26;
if (RicercaBinaria(mt, k, out riga, out colonna))
Console.WriteLine(k + " Trovato! Coord " + riga + ", " + colonna);
else
Console.WriteLine(k + " Non trovato!");

k = 11672;
if (RicercaBinaria(mt, k, out riga, out colonna))
Console.WriteLine(k + " Trovato! Coord " + riga + ", " + colonna);
else
Console.WriteLine(k + " Non trovato!");

k = 9790;
if (RicercaBinaria(mt, k, out riga, out colonna))
Console.WriteLine(k + " Trovato! Coord " + riga + ", " + colonna);
else
Console.WriteLine(k + " Non trovato!");

k = 14089;
if (RicercaBinaria(mt, k, out riga, out colonna))
Console.WriteLine(k + " Trovato! Coord " + riga + ", " + colonna);
else
Console.WriteLine(k + " Non trovato!");

}
}
}


In pratica applico la ricerca binaria riga per riga. L'algoritmo dovrebbe avere, dunque, complessità O((log N)*M) nel caso peggiore(N = numero colonne, M = numero righe).

Spero di riuscire a postare una soluzione migliore.

[Vincenzo1968]

Credo di aver migliorato i tempi di ricerca utilizzando una lista concatenata.
Per la prima riga effettuo una ricerca lineare aggiornando la lista concatenata con gli indici delle colonne valide.

Dalla seconda riga in poi si effettua la ricerca binaria(escludendo le colonne calcolate al passo precedente).


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Diagnostics;

namespace Matrix
{
public class Lista
{
public int colonna;
public Lista next;
}

public class Matrix
{
private int _NumRows;
private int _NumCols;

int[,] matrix = null;

public Matrix(int y, int x)
{
matrix = new int[y, x];
}

public Matrix(StreamReader sr)
{
string dimrow = sr.ReadLine();
string[] dimstrings = dimrow.Split(',');

if (dimstrings.Length != 2)
throw new Exception("Head Error");

_NumCols = int.Parse(dimstrings[0]);
_NumRows = int.Parse(dimstrings[1]);

matrix = new int[_NumRows, _NumCols];

for (int row = 0; row < _NumRows; row++)
{
string rowstring = sr.ReadLine();
string[] valoristringa = rowstring.Split(',');
if (valoristringa.Length != _NumCols)
throw new Exception(string.Format("Record Error: {0}", row));
var convertiti = valoristringa.Select((t, index) => new { index = index, val = int.Parse(t) });
convertiti.ToList().ForEach(t => matrix[row, t.index] = t.val);
}
}

public int GetCount = 0;

public int GetLength(int dimension)
{
return matrix.GetLength(dimension);
}

public int NumRows
{
get
{
return _NumRows;
}
}

public int NumCols
{
get
{
return _NumCols;
}
}

public int this[int y, int x]
{
get
{
GetCount++;
return matrix[y, x];
}
}
}

class Program
{
static public bool RicercaBinaria(Matrix mtx, int k, out int riga, out int colonna, out int passi)
{
Lista lst = null;
Lista temp = null;
int b, a, m;
int r = 0;

passi = 0;

riga = colonna = -1;

for (int j = 0; j < mtx.NumCols; j++)
{
passi++;
if (k == mtx[0, j])
{
riga = 0;
colonna = j;
return true;
}
else
{
if (k > mtx[0, j])
{
if (lst != null)
{
temp = lst;
while (temp.next != null)
temp = temp.next;
temp.next = new Lista();
temp.next.colonna = j;
temp.next.next = null;
}
else
{
lst = new Lista();
lst.colonna = j;
lst.next = null;
}
}
}
}

r = 1;
while (r < mtx.NumRows)
{
passi++;
if (lst == null)
return false;

b = lst.colonna;
a = mtx.NumCols - 1;

while (b <= a)
{
passi++;
m = (b + a) / 2;
if (k < mtx[r, m])
a = m - 1;
else if (k > mtx[r, m])
b = m + 1;
else
{
riga = r;
colonna = m;
return true; // Trovato
}
}
++r;
lst = lst.next;
}


b = 0;
a = mtx.NumCols - 1;
r = mtx.NumRows - 1;
while (b <= a)
{
passi++;
m = (b + a) / 2;
if (k < mtx[r, m])
a = m - 1;
else if (k > mtx[r, m])
b = m + 1;
else
{
riga = r;
colonna = m;
return true; // Trovato
}
}


return false;
}

static void Main(string[] args)
{
StreamReader sr = new StreamReader(@"C:\Temp\MatProva_250_200.txt");
Matrix mt = new Matrix(sr);

Console.WriteLine();

int riga, colonna;
int passi;

int k = 0;

Stopwatch watch = new Stopwatch();
watch.Start();

if ( RicercaBinaria(mt, k, out riga, out colonna, out passi) )
Console.WriteLine(k + " Trovato in " + passi + " passi. Coord " + riga + ", " + colonna);
else
Console.WriteLine(k + " Non trovato in " + passi + " passi.");

k = 100;
if (RicercaBinaria(mt, k, out riga, out colonna, out passi))
Console.WriteLine(k + " Trovato in " + passi + " passi. Coord " + riga + ", " + colonna);
else
Console.WriteLine(k + " Non trovato in " + passi + " passi.");

k = 32538;
if (RicercaBinaria(mt, k, out riga, out colonna, out passi))
Console.WriteLine(k + " Trovato in " + passi + " passi. Coord " + riga + ", " + colonna);
else
Console.WriteLine(k + " Non trovato in " + passi + " passi.");

k = 20984;
if (RicercaBinaria(mt, k, out riga, out colonna, out passi))
Console.WriteLine(k + " Trovato in " + passi + " passi. Coord " + riga + ", " + colonna);
else
Console.WriteLine(k + " Non trovato in " + passi + " passi.");

k = 32767;
if (RicercaBinaria(mt, k, out riga, out colonna, out passi))
Console.WriteLine(k + " Trovato in " + passi + " passi. Coord " + riga + ", " + colonna);
else
Console.WriteLine(k + " Non trovato in " + passi + " passi.");

k = 32539;
if (RicercaBinaria(mt, k, out riga, out colonna, out passi))
Console.WriteLine(k + " Trovato in " + passi + " passi. Coord " + riga + ", " + colonna);
else
Console.WriteLine(k + " Non trovato in " + passi + " passi.");

k = 26;
if (RicercaBinaria(mt, k, out riga, out colonna, out passi))
Console.WriteLine(k + " Trovato in " + passi + " passi. Coord " + riga + ", " + colonna);
else
Console.WriteLine(k + " Non trovato in " + passi + " passi.");

k = 11672;
if (RicercaBinaria(mt, k, out riga, out colonna, out passi))
Console.WriteLine(k + " Trovato in " + passi + " passi. Coord " + riga + ", " + colonna);
else
Console.WriteLine(k + " Non trovato in " + passi + " passi.");

k = 9790;
if (RicercaBinaria(mt, k, out riga, out colonna, out passi))
Console.WriteLine(k + " Trovato in " + passi + " passi. Coord " + riga + ", " + colonna);
else
Console.WriteLine(k + " Non trovato in " + passi + " passi.");

k = 14089;
if (RicercaBinaria(mt, k, out riga, out colonna, out passi))
Console.WriteLine(k + " Trovato in " + passi + " passi. Coord " + riga + ", " + colonna);
else
Console.WriteLine(k + " Non trovato in " + passi + " passi.");

watch.Stop();
Console.WriteLine();
Console.WriteLine("Tempo impiegato -> {0}", watch.ElapsedMilliseconds);

}
}
}


Questi sono i risultati:

http://www.guidealgoritmi.it/images/ImgForums/RicercaMatrice.jpg

[gugoXX]

Ciao Vincenzo.
Per sapere quante volte hai letto una cella dalla matrice e' sufficiente utilizzare la proprieta'.
nomeMatrice.GetCount

Tenendo conto che dopo la lettura probabilmente vorrai anche resettare il conteggio con nomeMatrice.GetCount=0;

Comunque si' direi che ad occhio e' un O(n log m)
qualcosa in meno per la semplificazione iniziale, ma non vorrei appunto che tale semplificazione sia troppo controproducente. Prova a testare con la GetCount.

Per quanto riguarda me ho cercato di ottimizzare il mio algoritmo, ma mi e' venuto un incubo stile assembly che fa pena.
Ed inoltre ho solo peggiorato il numero di lettura, quindi ritorno sui miei passi.
E' un algoritmo semplice. Putroppo sento che e' migliorabile, ma non riesco proprio a trovare come.

[71104]

mmm..
ma non c'è un modo per inizializzare la matrice di booleani direttamente a true?
in quel modo hai complessità O(m*n) solo per l'inizializzazione di Auxiliary :stordita: azz, è vero :muro:

be' potrei invertire nell'algoritmo il significa di Auxiliary e così potrei accontentarmi di usare una matrice ausiliaria inizializzata interamente a false, ma mi sa che non faccio altro che spostare il problema dal mio codice al framework... il quale framework però dovrebbe comunque svolgere il compito in maniera più efficiente del mio codice visto che non è codice managed e quindi non effettua bound checking.


Posso gentilmente chiedervi se potete adoperare una classe matrice tipo questa
Oppure se comunque potete tenere il conto di tutte le volte che leggete un valore dalla matrice (anche per confronti, in qualsiasi caso)
cosi' possiamo poi confrontare i numeri di letture e in qualche modo dedurne la complessita' anche senza valutare l'algoritmo. non sarebbe utile più di tanto, dovresti aggiungere il costo per costruire eventuali strutture ausiliarie; nel mio caso la matrice, nel caso di shinya l'heap.

[gugoXX]

Ok.
Ipotizziamo pero' che il costo vero sia la lettura dalla Matrice.
Ipotizziamo che le celle siano remote e che leggere una cella costi 1 minuto, mentre invece qualsiasi altra operazione sia inifluente.
Solo per valutare la complessita' algoritmica, non la velocita' computazionale vera.

Per costruire l'Heap occorre conoscere il valore di tutte le celle remote, mentre la tua struttura ausiliaria e' locale. Inizializzare qualcosa a True o a False sarebbe comunque immediato.

Atlrimenti, se proprio come discorso non ti piace, prova a valutare se per te una Dictionary<Point,bool> inizialmente vuota sia sufficiente,
Dove popolare la Dictionary ogni volta che trovi un Point da gettarci dentro.
Se sceglierai cosi' fai attenzione agli operatori di eguaglianza. In particolare la
GetHashCode, che e' la funzione che viene usata dalle Dictionary.
che dovra' restituire un valore univoco per ciascun Point.

[71104]

ok, in effetti il discorso della matrice remota e delle strutture ausiliari locali ha senso.

ho sistemato un po' il mio codice e ho anche inserito un contatore che conta le chiamate; ipotizzando che ogni chiamata abbia un costo O(1) il contatore dovrebbe dare una stima della complessità dell'algoritmo secondo un certo input.


class MatrixTest
{
static int[,] matrix =
{
{1, 4, 7, 8, 9, 11},
{2, 5, 8, 10, 11, 12},
{5, 6, 9, 12, 14, 15},
{7, 8, 12, 15, 17, 20},
{8, 9, 17, 18, 19, 20},
};

static bool[,] auxiliary;
static int counter;

static bool Exists(int value, int x, int y)
{
if ((x >= matrix.GetLength(1)) || (y >= matrix.GetLength(0)))
{
return false;
}

if (auxiliary[y, x])
{
return false;
}

counter++;

if (matrix[y, x] == value)
{
return true;
}

if (matrix[y, x] > value)
{
auxiliary[y, x] = true;
return false;
}

if (Exists(value, x + 1, y))
{
return true;
}

if (Exists(value, x, y + 1))
{
return true;
}

auxiliary[y, x] = true;
return false;
}

static bool Exists(int value)
{
auxiliary = new bool[matrix.GetLength(0), matrix.GetLength(1)];
counter = 0;
return Exists(value, 0, 0);
}

static void Main(string[] Arguments)
{
for (int i = 1; i <= 35; i++)
{
if (Exists(i))
{
Console.WriteLine(i + " is present - " + counter + " calls");
}
else
{
Console.WriteLine(i + " isn\'t present - " + counter + " calls");
}
}
}
}


a proposito, tanto per la cronaca quando a questo algoritmo viene chiesto di cercare un numero superiore al massimo presente (cioè un numero maggiore di matrix[n - 1, m - 1], n ed m dimensioni della matrice) vengono effettuate 30 chiamate. potrebbe essere considerato un difetto... :stordita:
in effetti prima di eseguire qualunque calcolo non sarebbe insensato aggiungere un banale controllo su matrix[0, 0] e matrix[n - 1, m - 1] per vedere se il numero cercato può esistere nella matrice.

[71104]

i miei risultati col matricione:

0 isn't present - 1 calls
100 isn't present - 6 calls
32538 isn't present - 50000 calls
20984 isn't present - 38115 calls
32767 isn't present - 50000 calls
32539 is present - 449 calls
26 is present - 1 calls
11672 is present - 250 calls
9790 is present - 11418 calls
14089 is present - 755 calls


certi fanno un po' schifo :stordita:

[shinya]

Ho rivisto un pò la soluzione con l'heap usando il file con la matriciona.
Mi sono accorto che l'heap può essere inizializzato una volta sola se i casi di test sono in ordine... quindi ho barato un pò, e ho ordinato l'array con i casi di test...


import java.util.*;
import java.io.*;

public class Contest2 {
public static void main(String[] args) throws Exception {
String filename = "MatProva_250_200.txt";
Scanner scanner = new Scanner(new File(filename));

scanner.nextLine(); // salto la prima riga con le dimensioni
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
while(scanner.hasNextLine()) {
String line = scanner.nextLine();
String[] numbers = line.split(",");
for (String number : numbers) {
pq.add(Integer.parseInt(number));
}
}

int[] tests = {0, 100, 32538, 20984, 32767, 32539, 26, 11672, 9790, 14089};
Arrays.sort(tests);

for (int test : tests)
search(pq, test);
}

private static void search(PriorityQueue<Integer> pq, int guess) {
Integer head = pq.peek();

if (head != null && guess < head) {
System.out.println(guess + " not found in 1 step.");
return;
}

int guessing = 0;
while(head <= guess) {
guessing++;
head = pq.peek();

if (head == null) break;
if (head == guess) {
System.out.println("Found " + guess + " in " + guessing + " steps.");
return;
}

if (head < guess) pq.poll();
}

System.out.println(guess + " not found in " + guessing + " steps.");
}
}


Output:


0 not found in 1 step.
Found 26 in 1 steps.
100 not found in 4 steps.
Found 9790 in 11115 steps.
Found 11672 in 4380 steps.
Found 14089 in 6185 steps.
20984 not found in 16245 steps.
32538 not found in 12076 steps.
Found 32539 in 1 steps.
32767 not found in 2 steps.


Ordinare i casi di test è barare?

[gugoXX]

Ho rivisto un pò la soluzione con l'heap usando il file con la matriciona.
Mi sono accorto che l'heap può essere inizializzato una volta sola se i casi di test sono in ordine... quindi ho barato un pò, e ho ordinato l'array con i casi di test...

Ordinare i casi di test è barare?

No, ovviamente ordinare i casi non e' barare.

Ma la soluzione cosi' non va bene.
Dovresti supporre di ricevere una Matrice dall'esterno, con determinate caratteristiche, e non di caricare l'heap e poi cominciare a contare gli accessi da li'.
Perche' per costruire l'heap devi comunque leggere tutta la matrice.
Ogni cella verra' letta almeno una volta.

Diciamo cosi', ogni volta che leggi una cella dalla matrice ci impeghi un minuto. Ma ce lo impieghi anche per costruire l'heap...
Una volta che hai costruito l'heap, e ti sei portato i valori in locale, e' tutto gratis. Ma il problema e' che anche per costruire l'heap avrai letto tutto. O(N * M).

E infatti c'e' un problema di base, non stai usando le 2 informazioni che i valori della matrice sono crescenti sulle righe e sulle colonne.
Se ti fosse stata data una matrice disordinata, avresti avuto le stesse performance. L'heap ordina tutto, indipendentemente dalla situazione di base. Ovvio che c'e' qualcosa che non va.

Inoltre se proprio devi leggere tutto fai che usare una hastable, non una Heap, cosi' in seguito in O(1) dirai se il valore c'e' o non c'e'.

[marco.r]

Questo dopo aver trasformato la ricerca lineare iniziale in una ricerca binaria:

def linearSearch( matrix, value, rowmin, colmin, rowmax,colmax ):
i = rowmin
j = colmin
while i < rowmax and j < colmax and matrix(i,j) <= value:
i+=1
j+=1
return [i,j]


def binarySearch( matrix, value, rowmin, colmin, rowmax, colmax ):
size = min( rowmax-rowmin, colmax-colmin )
if size < 5:
return linearSearch(matrix,value,rowmin,colmin,rowmax,colmax)

n = size/2

current = matrix( rowmin+n, colmin+n )
next = matrix( rowmin+n+1, colmin+n+1 )
if current <= value and next > value:
return [rowmin+n,colmin+n]
if current > value:
return binarySearch( matrix, value, rowmin, colmin, rowmin+n,colmin+n)
else:
return binarySearch( matrix, value, rowmin+n, colmin+n, rowmax,colmax)

positionOfGreatestLowerOrEqualThan = binarySearch

(ho cambiato anche la notazione della matrice in matrix(i,j) per poter registrare gli accessi)

[71104]

ho fatto qualche modifica al mio algoritmo; ci credete se vi dico che ho ottenuto questi risultati?

0 isn't present - 0 calls
100 isn't present - 252 calls
32538 isn't present - 201 calls
20984 isn't present - 354 calls
32767 isn't present - 0 calls
32539 is present - 200 calls
26 is present - 250 calls
11672 is present - 1 calls
9790 is present - 449 calls
14089 is present - 63 calls

:ciapet: :ciapet: :ciapet:

[marco.r]

ops. forse la mia versione ha un bug concettuale... meglio se ora controllo :p

[^TiGeRShArK^]

ho fatto qualche modifica al mio algoritmo; ci credete se vi dico che ho ottenuto questi risultati?

0 isn't present - 0 calls
100 isn't present - 252 calls
32538 isn't present - 201 calls
20984 isn't present - 354 calls
32767 isn't present - 0 calls
32539 is present - 200 calls
26 is present - 250 calls
11672 is present - 1 calls
9790 is present - 449 calls
14089 is present - 63 calls

:ciapet: :ciapet: :ciapet:
:mbe:
no, perchè è impossibile che tu riesca a sapere se un numero non è presente nella matrice senza leggere alcun valore.. :fagiano:
a meno che non hai inventato l'algoritmo "nostradamus" :asd:

[71104]

l'ho ottimizzato ancora:

0 isn't present - 0 calls
100 isn't present - 251 calls
32538 isn't present - 200 calls
20984 isn't present - 352 calls
32767 isn't present - 0 calls
32539 is present - 200 calls
26 is present - 250 calls
11672 is present - 1 calls
9790 is present - 449 calls
14089 is present - 63 calls


credo che meglio di così non si possa fare, il mio attuale algoritmo è di una semplicità disarmante :Prrr:

la complessità è O(N + M) :ciapet:
edit - e con queste ultime modifiche ho anche ridotto l'occupazione di memoria: ho tolto la matrice ausiliare, non serviva più.

[71104]

:mbe:
no, perchè è impossibile che tu riesca a sapere se un numero non è presente nella matrice senza leggere alcun valore.. :fagiano:
a meno che non hai inventato l'algoritmo "nostradamus" :asd: leggi bene, non c'è scritto "0 letture", c'è scritto "0 chiamate"; l'algoritmo in quel caso termina subito perché vede che il valore cercato è out-of-range. :Prrr:

[gugoXX]

Mamma mia che risultatoni che leggo. E' dura qui. Tutti professionisti.
Marco.r, non ho capito come fai a gestire una matrice rettangolare con una sola riga e tante colonne. Mi spiego, potrebbe capitare che a forza di dividere il lavoro arrivi a dover leggere solo una riga. Mi sarei aspettato un qualcosa che incrementi solo sulla riga (o sulla colonna per il problema duale).

Mi sa che ho perso. Non sono tanto distante, ma non riesco a guadagnare di piu' se non facendo assunzioni non oneste.

Vi posto i miei risultati


0 : Not Found
Letture da matrice: 11

100 : Not Found
Letture da matrice: 14

32538 : Not Found
Letture da matrice: 10

20984 : Not Found
Letture da matrice: 302

32767 : Not Found
Letture da matrice: 10

32539 : Found - Coords 249,199
Letture da matrice: 9

26 : Found - Coords 0,0
Letture da matrice: 10

11672 : Found - Coords 249,0
Letture da matrice: 454

9790 : Found - Coords 0,199
Letture da matrice: 1

14089 : Found - Coords 88,110
Letture da matrice: 169

Media di letture, su 1000 ricerche casuali con range 0 - 32539 : 125.54


E vi spiego il mio algoritmo.
A differenza di praticamente tutti voi, io sono partito dall'angolo in basso a sinistra.
Mi muovo lungo la riga, alla ricerca del primo valore immediatamente superiore al valore target. Una volta che lo trovo, sono sicuro che tutta la sottomatrice a sinistra non conterra' il target, essendo che saranno tutti valori inferiori al mio penultimo toccato, che era di sicuro inferiore al target.
A questo punto mi muovo verso l'alto, alla ricerca del primo valore minore del valore target. Non appena lo trovo sono sicuro che la sottomatrice basso-destra e' da escludere, essendo che contiene tutti valori maggiori o uguali al penultimo toccato, che era per definizione maggiore del valore target.
Ricomincio a muovermi verso destra, alla ricerca del primo valore superiore al target, poi di nuovo verso l'alto, alla ricerca del primo valore inferiore del target. etc.
In pratica mi muovo cercando di stare in equilibrio tra lavori immediatamente minori e valori immediatamente maggiori del target, lungo la "curva di potenziale", fino a che non lo trovo o fino a che non esco dalla matrice.

Questo algoritmo dovrebbe essere O(M + N) con il pregio che sono sicuro che il target lo trovero' in al piu' M+N mosse (ogni volta mi muovo o verso destra o verso l'alto)

Poi ho visto che cosi' stavo perdendo.
Allora ho dato un boost iniziale.
Alla prima ricerca mi muovo lungo la riga inferiore ( o lungo la colonna sinistra se il valore e' gia' > di quello target) con un divide et impera.
Ma solo per la prima ricerca, poi ho visto che per muoversi lungo la "curva di potenziale" era meglio procedere per passetti piccoli.

Quindi calcolare la compelssita' e' un casino, essendo che sono di fatto 2 algoritmi messi insieme.

Posto l'algoritmo senza divide et impera, che avra' valori un po' piu' alti, soprattuto nei limiti ( ma non tanto nei medi)


public static Result Contains3(Matrix mat, int val)
{
int indx = 0;
for (int indy = mat.DY-1; indy >= 0; indy--)
{
do
{
int test = mat[indy, indx ];
if (test == val) return new Result(val, true, indx, indy, mat.GetCount);
if (test > val) break;
indx++;
if (indx == mat.DX) return new Result(val, false, -1, -1, mat.GetCount);
} while (true);
}
return new Result(val, false, -1, -1, mat.GetCount); ;
}

[71104]

A differenza di praticamente tutti voi, io sono partito dall'angolo in basso a sinistra. io invece sono partito da quello in alto a destra :D
abbiamo avuto la stessa idea, solo che l'abbiamo applicata in modi opposti :)
se cambiassi un po' di cose nel mio algoritmo sono sicuro che avrei i tuoi stessi risultati.


Mi muovo lungo la riga, alla ricerca del primo valore immediatamente superiore al valore target. Una volta che lo trovo, sono sicuro che tutta la sottomatrice a sinistra non conterra' il target, essendo che saranno tutti valori inferiori al mio penultimo toccato, che era di sicuro inferiore al target.
A questo punto mi muovo verso l'alto, alla ricerca del primo valore minore del valore target. Non appena lo trovo sono sicuro che la sottomatrice basso-destra e' da escludere, essendo che contiene tutti valori maggiori o uguali al penultimo toccato, che era per definizione maggiore del valore target.
In pratica mi muovo cercando di stare in equilibrio tra lavori minori e valori maggiori del target, lungo la "curva di potenziale", fino a che non lo trovo o fino a che non esco dalla matrice. bla bla bla :blah:
sveglia, stai semplicemente visitando un albero binario di ricerca di altezza N+M :D


Questo algoritmo dovrebbe essere O(M + N) con il pregio che sono sicuro che il target lo trovero' in al piu' M+N mosse (ogni volta mi muovo o verso destra o verso l'alto) precisamente :)


posto il mio codice:

static bool Exists2(int value, int x, int y)
{
if ((x < 0) || (y >= matrix.GetLength(0)))
{
return false;
}

if ((value < matrix[y, 0]) || (value > matrix[matrix.GetLength(0) - 1, x]))
{
return false;
}

counter++;

if (value < matrix[y, x])
{
return Exists2(value, x - 1, y);
}
else if (value > matrix[y, x])
{
return Exists2(value, x, y + 1);
}
else
{
return true;
}
}

static bool Exists2(int value)
{
counter = 0;
return Exists2(value, matrix.GetLength(1) - 1, 0);
}

static void CheckValue(int value)
{
if (Exists2(value))
{
Console.WriteLine(value + " is present - " + counter + " calls");
}
else
{
Console.WriteLine(value + " isn\'t present - " + counter + " calls");
}
}

static void Main(string[] Arguments)
{
ReadMatrix();

// not present
CheckValue(0);
CheckValue(100);
CheckValue(32538);
CheckValue(20984);
CheckValue(32767);

// present
CheckValue(32539);
CheckValue(26);
CheckValue(11672);
CheckValue(9790);
CheckValue(14089);
}

[gugoXX]

io invece sono partito da quello in alto a destra :D
abbiamo avuto la stessa idea, solo che l'abbiamo applicata in modi opposti :)
se cambiassi un po' di cose nel mio algoritmo sono sicuro che avrei i tuoi stessi risultati.


bla bla bla :blah:
sveglia, stai semplicemente visitando un albero binario di ricerca di altezza N+M :D



Be' il boost iniziale ha alleggerisce i casi particolari.
Comunque per poter dire "0 not present", devi avere almeno letto il valore delle 2 celle limite. Almeno 2 letture ci sono. Mi sa che dovresti sommare 2 a tutti i risultati.

Non lo stavo vedendo come albero binario di ricerca, lo stavo vedendo come un problema fisico, come la ricerca di un valore specifico di potenziale di un campo, che pero' puo' assumere valori discreti.

Comunque quello di Marco mi piace di piu' perche' e' generalizzabile al problema multidimensionale (ovvero un parallelepipedo, non una matrice, di pari caratteristiche),
mentre invece il nostro non lo e' in modo molto semplice.

[71104]

Be' il boost iniziale ha alleggerisce i casi particolari. io quel boost non ce lo metterei, potrebbe essere inefficiente: metti che alla prima mossa devi fare un passo in una direzione e alla mossa successiva devi farne uno nell'altra direzione? il risultato è che alla prima mossa hai dovuto fare log(N) passi (con N lunghezza della prima riga o della prima colonna, a seconda di come ti muovi la prima volta) quando avresti potuto farne uno solo. insomma, inutile darsi pena con la ricerca binaria, tanto la visita dell'albero sempre O(N+M) è.


Comunque per poter dire "0 not present", devi avere almeno letto il valore delle 2 celle limite. Almeno 2 letture ci sono. Mi sa che dovresti sommare 2 a tutti i risultati. in realtà no, le letture sono molte di più: se guardi il codice risultano essere il triplo delle chiamate :D questo perché ad ogni chiamata vengono letti dalla matrice 3 valori distinti. con il contatore io intendevo contare la complessità dell'algoritmo in funzione del numero di chiamate.

in realtà però prima di incrementare il contatore e contare la chiamata ho messo un paio di controlli uno dei quali (bound checking degli indici) è necessario, mentre l'altro lo potrei anche togliere; si tratta di verificare ad ogni singolo passo verso l'altro capo della matrice se è ancora possibile che il valore cercato sia presente, cioè se è ancora compreso tra il valore della foglia massima e quello della foglia minima. questo controllo è effettivamente utile solo se l'incidenza dei valori è bassa (cioè se viene richiesto spesso di cercare valori che si rivelano non essere presenti), perché in quei casi permette all'algoritmo di terminare prima di avere una delusione :D; ma altrimenti peggiora la performance in termini di numero di letture (non in numero di chiamate).


Non lo stavo vedendo come albero binario di ricerca, lo stavo vedendo come un problema fisico, come la ricerca di un valore specifico di potenziale di un campo, che pero' puo' assumere valori discreti. volevi dire che il campo stesso è discreto, non i valori, dico bene?

[gugoXX]

io quel boost non ce lo metterei, potrebbe essere inefficiente: metti che alla prima mossa devi fare un passo in una direzione e alla mossa successiva devi farne uno nell'altra direzione? il risultato è che alla prima mossa hai dovuto fare log(N) passi (con N lunghezza della prima riga o della prima colonna, a seconda di come ti muovi la prima volta) quando avresti potuto farne uno solo. insomma, inutile darsi pena con la ricerca binaria, tanto la visita dell'albero sempre O(N+M) è.


MA si' infatti ho postato l'algoritmo senza boost.
Se dovessi implementarlo davvero il boost non lo metteri. E' brutto a leggersi, con check su casi particolari,etc.
E' solo che i valori che avevo scelto erano un po' "particolari".
Ipotizzando che le riceche vengano normalmente fatte all'interno della matrice in effetti non fa bene. C'e' anche da dire che come giustamente hai notato alla peggio ci sono Log2(N) passi in piu', e direi che ce li si puo' permettere.


volevi dire che il campo stesso è discreto, non i valori, dico bene?

Sisi, volevo dire che il campo e il suo potenziale sono discreti.
Un po' come la montagnola di QBert. Chi se lo ricorda? Gradoni su cui saltellare, pero' di altezze irregolari.
Occorre cercare il gradone di una ben precisa altezza.
http://www.adamryder.com/qbert.jpg
Mi sa che non lo conosceva nessuno. Mi sento un po' vecchio.

[k0nt3]

Una soluzione che almeno nel caso di test funziona ènel secondo caso di test quando ci metto un numero che non esiste nella matrice minore del massimo ci mette solo 2 iterazioni a scoprire che non esiste

UPDATE: qualcuno me lo tradurrebbe in python che son curioso di vedere come esce?? Devo ancora calcolarci la complessità, che ad occhio sembra essere sublineare
interessante l'idea di usare A* :fagiano: però così a occhio mi sembra che manca qualcosa (dai importanza solo all'euristica? se è così è un algoritmo greedy)
io l'ho implementato così (ci sono altre due classi che sono Matrix e Node che però è evidente cosa fanno):

import java.util.ArrayList;
import java.util.Collection;


public class Ricerca {

/**
* @param args
*/
public static void main(String[] args) {
Matrix m = new Matrix();
int[] goals = {0,100,32538,20984,32767,32539,26,11672,9790,14089};
for (int goal : goals) {
m.resetCount();
boolean found = find(m, goal);
System.out.println("searching for: "+goal+"\nfound: "+found+"\ncount: "+m.getCount()+"\n");
}
}

private static boolean find(Matrix m, int goal) {
ArrayList<Node> visited = new ArrayList<Node>();
ArrayList<Node> fringe = new ArrayList<Node>();

Node s = new Node(m, m.getWidth()/2, m.getHeight()/2, 0);
fringe.add(s);

while(fringe.size() > 0) {
Node current = selectNode(fringe, goal);
fringe.remove(current);
if(current.getValue() == goal) {
return true;
}
visited.add(current);
fringe.addAll(expand(m, current, goal, visited));
}

return false;
}

private static Node selectNode(ArrayList<Node> fringe, int goal) {
int selected = 0;
for (int i = 1; i < fringe.size(); i++) {
if(evaluate(fringe.get(i), goal) < evaluate(fringe.get(selected), goal))
selected = i;
}
return fringe.get(selected);
}

private static int evaluate(Node node, int goal) {
if(goal > node.getValue())
return node.getCost() + (goal - node.getValue());
else
return node.getCost() + (node.getValue() - goal);
}

private static Collection<? extends Node> expand(Matrix m, Node s, int goal, ArrayList<Node> visited) {
ArrayList<Node> expanded = new ArrayList<Node>();
Node n1 = null,n2 = null;

if(goal > s.getValue()) {
if(s.getX()+1<m.getWidth())
n1 = new Node(m, s.getX()+1, s.getY(), s.getCost()+1);
if(s.getY()+1<m.getHeight())
n2 = new Node(m, s.getX(), s.getY()+1, s.getCost()+1);
} else {
if(s.getX()>0)
n1 = new Node(m, s.getX()-1, s.getY(), s.getCost()+1);
if(s.getY()>0)
n2 = new Node(m, s.getX(), s.getY()-1, s.getCost()+1);
}
if(n1 != null && !visited.contains(n1))
expanded.add(n1);
if(n2 != null && !visited.contains(n2))
expanded.add(n2);
return expanded;
}
}

come mi aspettavo però ha prestazioni nettamente inferiori agli algoritmi che avete implementato voi..

partendo dal centro della matrice:

searching for: 0
found: false
count: 25226

searching for: 100
found: false
count: 25228

searching for: 32538
found: false
count: 24780

searching for: 20984
found: false
count: 5003

searching for: 32767
found: false
count: 24778

searching for: 32539
found: true
count: 427

searching for: 26
found: true
count: 415

searching for: 11672
found: true
count: 1488

searching for: 9790
found: true
count: 1313

searching for: 14089
found: true
count: 173

il problema di A* in questo caso è che la funzione costo non è molto significativa (io ho usato il numero di movimenti nella matrice), inoltre anche l'euristica (differenza tra obiettivo e numero corrente) non è particolarmente efficente. è però un'euristica ammissibile, quindi in teoria l'algoritmo dovrebbe terminare sempre in un tempo finito.

ps. come al solito gli errori nel codice sono certi :D in effetti mi sembra strano che a volte esplora più elementi di quelli che contiene la matrice... vedrò di capire come mai

[k0nt3]

sembra meglio partire dall'angolo in basso a sinistra come dice gugoXX

searching for: 0
found: false
count: 200

searching for: 100
found: false
count: 206

searching for: 32538
found: false
count: 253

searching for: 20984
found: false
count: 860

searching for: 32767
found: false
count: 250

searching for: 32539
found: true
count: 250

searching for: 26
found: true
count: 200

searching for: 11672
found: true
count: 1264

searching for: 9790
found: true
count: 1

searching for: 14089
found: true
count: 438

[marco.r]

Marco.r, non ho capito come fai a gestire una matrice rettangolare con una sola riga e tante colonne. Mi spiego, potrebbe capitare che a forza di dividere il lavoro arrivi a dover leggere solo una riga. Mi sarei aspettato un qualcosa che incrementi solo sulla riga (o sulla colonna per il problema duale).

Infatti finora non l'ho gestita :p. Non a caso ci mette parecchio nei casi limite.
Adesso provo a mettere un check in modo che nel caso di matrice riga o colonna faccia una ricerca binaria.


import numpy


class Result:
def __init__(self,x,y):
self.x = x
self.y = y


class Matrix:
def __init__(self,*data):
self.matrix = numpy.array(*data)
self.gets = 0
self.totalGets=0

def __call__(self,x,y):
self.gets+=1
self.totalGets+=1
self.positions[x][y] += 1
return self.matrix[x][y]

def rows(self):
return len(self.matrix)

def cols(self):
return len(self.matrix[0])

def linearSearch( matrix, value, rowmin, colmin, rowmax,colmax ):
i = rowmin
j = colmin
while i < rowmax and j < colmax:
v = matrix(i,j)
if v == value:
raise Result(i,j)
elif v < value:
i+=1
j+=1
else:
return [i-1,j-1]
return [i-1,j-1]


def binarySearch( matrix, value, rowmin, colmin, rowmax, colmax ):
size = min( rowmax-rowmin, colmax-colmin )
if size < 5:
return linearSearch(matrix,value,rowmin,colmin,rowmax,colmax)

n = size/2

current = matrix( rowmin+n, colmin+n )
if current == value:
raise Result(rowmin+n,colmin+n)

next = matrix( rowmin+n+1, colmin+n+1 )
if current < value and next > value:
return [rowmin+n,colmin+n]
if current > value:
return binarySearch( matrix, value, rowmin, colmin, rowmin+n,colmin+n)
else:
return binarySearch( matrix, value, rowmin+n, colmin+n, rowmax,colmax)

positionOfGreatestSmallerThan = binarySearch

def findNumber( matrix, value, rowmin, colmin, rowmax, colmax ):
if rowmin == rowmax or colmin == colmax:
return False

[i,j] = positionOfGreatestSmallerThan( matrix, value, rowmin, colmin, rowmax, colmax )
return findNumber( matrix, value, rowmin, j+1, i+1, colmax ) or findNumber( matrix, value, i+1, colmin, rowmax, j+1 )


I risultati che ottengo sono i seguenti

Did not find 0 after 13 gets
Did not find 100 after 18 gets
Did not find 32538 after 162 gets
Did not find 20984 after 579 gets
Did not find 32767 after 64 gets
Found 32539 with 64 gets in position [199, 249]
Found 26 with 13 gets in position [0, 0]
Found 11672 with 113 gets in position [0, 249]
Found 9790 with 647 gets in position [199, 0]
Found 14089 with 136 gets in position [22, 208]


Andando con valori presi a caso, mi va un po' meglio, e su 50000 valori ottengo una media un po' inferiore a 250, ovvero max(m,n)

Total of 12305370 for 50000 values, with a mean of 246.1074

[k0nt3]

in realtà no, le letture sono molte di più: se guardi il codice risultano essere il triplo delle chiamate :D questo perché ad ogni chiamata vengono letti dalla matrice 3 valori distinti. con il contatore io intendevo contare la complessità dell'algoritmo in funzione del numero di chiamate.

questo si chiama barare :read:

[71104]

questo si chiama barare :read: c'era scritto chiaramente "calls" dopo le stime :O
ho spiegato tutto in maniera cristallina e ho anche postato il codice sorgente; che altro vuoi? :O

adesso ho provato a rimuovere il controllo di esistenza del valore cercato (cosicché il numero di chiamate corrisponda al numero di letture dalla matrice) e ottengo il seguente risultato:

0 isn't present - 250 calls
100 isn't present - 252 calls
32538 isn't present - 201 calls
20984 isn't present - 354 calls
32767 isn't present - 200 calls
32539 is present - 200 calls
26 is present - 250 calls
11672 is present - 1 calls
9790 is present - 449 calls
14089 is present - 63 calls


come dicevo, effettuare il controllo conviene solamente se il valore si rivela non presente (le prime 5 stime sono più alte delle prime 5 dell'algoritmo comprensivo di controllo).


edit - per chiarezza, questo era l'algoritmo risultante:

static bool Exists2(int value, int x, int y)
{
if ((x < 0) || (y >= matrix.GetLength(0)))
{
return false;
}

counter++;

if (value < matrix[y, x])
{
return Exists2(value, x - 1, y);
}
else if (value > matrix[y, x])
{
return Exists2(value, x, y + 1);
}
else
{
return true;
}
}

static bool Exists2(int value)
{
counter = 0;
return Exists2(value, matrix.GetLength(1) - 1, 0);
}

[k0nt3]

direi che a questo punto A* non si comporta così male come pensavo :fagiano:

@71104
ancora non incrementi il contatore per ogni lettura da matrice ;) a volte fai due letture in quel metodo (non fai prima a usare una classe come quella postata da gugoXX per la matrice? è l'unico modo che abbiamo per paragonare i nostri algoritmi)

[k0nt3]

io in Java l'ho implementata così (la matrice)

public class Matrix {
private int[][] matrix;
private int count = 0;
private int width = 0;
private int height = 0;

public Matrix() {
super();
int x = 0;
int y = 0;
Scanner scanner = null;
try {
scanner = new Scanner(new File("prova.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
Scanner headerScanner = new Scanner(scanner.nextLine());
headerScanner.useDelimiter(", ");

width = headerScanner.nextInt();
height = headerScanner.nextInt();
matrix = new int[width][height];
while(scanner.hasNext() && y < height) {
Scanner lineScanner = new Scanner(scanner.next());
lineScanner.useDelimiter(",");
while(lineScanner.hasNext()) {
if(x >= width) {
++y;
x = 0;
}

matrix[x][y] = lineScanner.nextInt();
++x;
}
}
}

public int getCount() {
return count ;
}

public void resetCount() {
count = 0;
}

public int getElement(int x, int y) {
++count;
return matrix[x][y];
}

public int getWidth() {
return width;
}

public int getHeight() {
return height;
}
}

[71104]

@71104
ancora non incrementi il contatore per ogni lettura da matrice ;) a volte fai due letture in quel metodo (non fai prima a usare una classe come quella postata da gugoXX per la matrice? è l'unico modo che abbiamo per paragonare i nostri algoritmi) ritenevo che la tua intelligenza fosse all'altezza di immaginare la seguente modifica:

static bool Exists2(int value, int x, int y)
{
if ((x < 0) || (y >= matrix.GetLength(0)))
{
return false;
}

counter++;

int matrixValue = matrix[y, x];
if (value < matrixValue)
{
return Exists2(value, x - 1, y);
}
else if (value > matrixValue)
{
return Exists2(value, x, y + 1);
}
else
{
return true;
}
}

static bool Exists2(int value)
{
counter = 0;
return Exists2(value, matrix.GetLength(1) - 1, 0);
}


:fagiano: :fagiano: :fagiano:

[k0nt3]

non c'è bisogno di tirare in ballo le capacità intellettuali, mi era sfuggito che stavi leggendo lo stesso valore :fagiano:

[71104]

non c'è bisogno di tirare in ballo le capacità intellettuali, mi era sfuggito che stavi leggendo lo stesso valore :fagiano: non ho potuto farne a meno, mi era sembrato eccessivamente palese :fagiano:

[^TiGeRShArK^]

ecco il mio codice con la ricerca binaria e i risultati:

class Prova
{
Matrix matrix;
int m, n;

public Prova()
{
int[] values = { 0, 100, 32538, 20984, 32767, 32539, 26, 11672, 9790, 14089 };
matrix = new Matrix();
m = matrix.RowLength - 1;
n = matrix.ColLength - 1;

foreach (int x in values)
{
int i;
matrix.GetCount = 0;

if (x < matrix[0, 0] || x > matrix[m, n])
{
result(false, x);
continue;
}

if (scanDiag(x, out i))
{
result(true, x);
continue;
}

if (scanMatrix(x, i))
result(true, x);
else
result(false, x);
}
Console.ReadLine();
}

private bool scanMatrix(int x, int i)
{
int originalIndex = i;
int firstNum = matrix[m, i];
int secondNum = matrix[i, n];

while ((firstNum >= x || secondNum >= x) && (i >= 0))
{
if (firstNum == x || secondNum == x)
{
return true;
}

if (scanRightMatrix(x, i, originalIndex))
{
return true;
}

if (scanLowerMatrix(x, i, originalIndex))
{
return true;
}

firstNum = matrix[m, i];
secondNum = matrix[i, n];
if (firstNum == x || secondNum == x)
return true;
i--;
}
return false;
}

private bool scanRightMatrix(int x, int i, int originalIndex)
{
int low = originalIndex;
int high = n;

while (low <= high)
{
int mid = (low + high) / 2;
int num = matrix[i, mid];
if (num > x)
high = mid - 1;
else if (num < x)
low = mid + 1;
else
{
return true;
}
}
return false;
}

private bool scanLowerMatrix(int x, int i, int originalIndex)
{
int low = originalIndex;
int high = m;

while (low <= high)
{
int mid = (low + high) / 2;
int num = matrix[mid, i];
if (num > x)
high = mid - 1;
else if (num < x)
low = mid + 1;
else
{
return true;
}
}
return false;
}

private bool scanDiag(int x, out int i)
{
i = 0;
int low = 0;
int high = n;
if (m < n)
high = m;
int max = high;

while (low <= high)
{
i = (low + high) / 2;
int num = matrix[i, i];
if (num > x)
high = i - 1;
else if (num < x)
low = i + 1;
else
{
if (i > 0 && i < max)
i--;
return true;
}
}
if (i > 0 && i < max)
i--;
return false;
}

private void result(bool found, int x)
{
if (found)
Console.WriteLine("Trovato il numero {0}.", x);
else
Console.WriteLine("Il numero {0} non è stato trovato.", x);
Console.WriteLine("Letture effettuate: {0}", matrix.GetCount);
}

static void Main(string[] args)
{
new Prova();
}
}


Il numero 0 non è stato trovato.
Letture effettuate: 1
Il numero 100 non è stato trovato.
Letture effettuate: 30
Il numero 32538 non è stato trovato.
Letture effettuate: 30
Il numero 20984 non è stato trovato.
Letture effettuate: 1255
Il numero 32767 non è stato trovato.
Letture effettuate: 2
Trovato il numero 32539.
Letture effettuate: 12
Trovato il numero 26.
Letture effettuate: 9
Trovato il numero 11672.
Letture effettuate: 1343
Trovato il numero 9790.
Letture effettuate: 1160
Trovato il numero 14089.
Letture effettuate: 198

La media è 404

[ndakota]

La media è 404

cioè non trovato? non picchiatemi.. è squallida lo so.. :stordita:

[banryu79]

cioè non trovato? non picchiatemi.. è squallida lo so.. :stordita:
ma lol :D

[gugoXX]

cioè non trovato? non picchiatemi.. è squallida lo so.. :stordita:

Ahahah

OT.

State cercando un regalo per la vostra ragazza?
http://gizmodo.com/assets/resources/2007/02/httpanties.jpg

Fine OT

[^TiGeRShArK^]

:asd:

[banryu79]

Ahahah
OT.
State cercando un regalo per la vostra ragazza?
Fine OT

OT
Se poi l'effetto è che l'indossatrice mantiene quel che la mutanda promette prenoto una cinnquantina di slip mod. "OK" da distribuire tra le amiche :D
FINE OT

[shinya]

Ahahah

OT.

State cercando un regalo per la vostra ragazza?


Oh gesù cristo...

[^TiGeRShArK^]

Oh gesù cristo...

http://www.askanun.com/nunsense/nunderwear.jpg
:huh:

[marko.fatto]

salutate il topic :asd:

[ndakota]

ho scatenato 7 posts di flood :cry:

[gugoXX]

7 post su 100 non e' tanto. Sempre meglio do quei thread dove si vedono solo faccine.

comunque, tornando in Topic.
Abbiamo trovato un metodo, quello di Marco, che mi sembrerebbe logaritmico.
Pero' ho un dubbio. Ogni volta che si entra in ricorsione, si raddoppia il numero di sottomatrici potenziali da controllare. Questo influisce per forza nel calcolo della complessita', ma non ho tempo ora di valutare.

Abbiamo trovato un metodo lineare, con Complessita' O(N + M)

Abbiamo trovato piu' metodi logaritmici, con complessita' O(N * Log(M))

Non male direi, soprattutto la velocita' con cui sono venuti fuori.
Come dico sempre noi Italiani siamo molto bravi e apprezzati quando si tratta di fare le cose "in singolo".
Purtroppo si sente dire spesso che non ce la caviamo altrettanto bene in quanto gruppo.

Per intanto che magari vengono fuori altre considerazioni o magari altre soluzioni ancora migliori provo a tirare giu' un altro contest.

[shinya]

Per intanto che magari vengono fuori altre considerazioni o magari altre soluzioni ancora migliori provo a tirare giu' un altro contest.

Se non interessa trovare qualcosa di originale, qui ce ne sono un puttanaio di problemi interessanti (alcuni mi fanno ancora rigirare nel letto certe notti di luna piena...)

http://www.spoj.pl/problems/classical/

[gugoXX]

Se non interessa trovare qualcosa di originale, qui ce ne sono un puttanaio di problemi interessanti (alcuni mi fanno ancora rigirare nel letto certe notti di luna piena...)

http://www.spoj.pl/problems/classical/

Bello grazie.
Trarro' ispirazione, perche' e' ovvio che tutti andrebbero a cercare li' se c'e' pubblicato un algoritmo ottimo o quantomento consigliato.

[k0nt3]

perchè si possono vedere le soluzioni? :fagiano:

[gugoXX]

perchè si possono vedere le soluzioni? :fagiano:

mmmh. Forse no. Ho visto che c'era il link Code cliccabile e pensavo fosse per scaricare un esempio... bene, meglio.

[71104]

mi interessava vedere quand'è che la soluzione lineare (O(N+M)) è preferibile a quella in O(N*logM), e quindi stavo provando a cavare qualcosa da questa disequazione:

N + M < N * logM

N * logM - N > M

N * (logM - 1) > M

N > M / (logM - 1)


cioè la mia soluzione è preferibile a quella di non mi ricordo chi (shinya?) quando una delle due dimensioni è maggiore dell'altra diviso il logaritmo in base 2 dell'altra meno 1 (che casino :D).

di conseguenza stavo provando a studiare la funzione:

f(x) = x / (log2(x) - 1)

per vedere che comportamento ha (log2 sarebbe ovviamente il logaritmo in base 2), ma purtroppo mi sono fermato perché non ricordo più come si facevano i limiti :cry:

sono partito in quarta a scrivere le condizioni di dominio:

x > 0 (il logaritmo in base 2 prende solo valori strettamente positivi)

log2(x) - 1 != 0 (denominatore diverso da zero)
log2(x) != 1
x != 2 (perché 2 alla 1 fa 2)


poi ho provato a vedere a cosa tende il limite per x che tende a +oo e mi viene una forma indeterminata (infinito su infinito) e lì mi sono fermato.

scommetto che marco.r può darmi una mano :D

[gugoXX]

Ricordatevi di piazzare delle costanti (a,b,c,d) moltiplicative per ciascun fattore prima di fare gli studi.

O(aM +bN)
O(cM * Log dN))

Per i limiti notevoli che vanno ad infinito, usa de l'Hopital. Lo spiegano, dicono di non usarlo perche' senno' e' troppo facile e cosi' tutti se lo dimenticano...

[^TiGeRShArK^]

ma tra l'altro il lim x / log(x) per x che tende ad infinito non è infinito poichè x è di ordine superiore rispetto a log x senza stare a scomodare de l'hopital? :stordita:
sempre se non ho detto una cazzata :asd:

[71104]

ma tra l'altro il lim x / log(x) per x che tende ad infinito non è infinito poichè x è di ordine superiore rispetto a log x senza stare a scomodare de l'hopital? :stordita:
sempre se non ho detto una cazzata :asd:
uhm, in effetti il logaritmo diverge ma lo fa più lentamente di x, però questo vale per il logaritmo naturale; non cosa succeda con altre basi

[^TiGeRShArK^]

uhm, in effetti il logaritmo diverge ma lo fa più lentamente di x, però questo vale per il logaritmo naturale; non cosa succeda con altre basi

il logaritmo(x) è sempre un infinito di ordine inferiore rispetto ad x qualunque sia la base se non ricordo male... :fagiano:

[71104]

il logaritmo(x) è sempre un infinito di ordine inferiore rispetto ad x qualunque sia la base se non ricordo male... :fagiano: ok, famo finta che per x -> +oo la funzione diverge e bonanotte :D

[marko.fatto]

tiger ha ragione...
comunque per de l'hopital basta calcolare la derivata sopra e sotto la linea della frazione e ricalcolare il limite..
tutta roba fatta quest'anno :fagiano:

[^TiGeRShArK^]

tiger ha ragione...
comunque per de l'hopital basta calcolare la derivata sopra e sotto la linea della frazione e ricalcolare il limite..
tutta roba fatta quest'anno :fagiano:

:eek:
Per me sono passati dieci anni dal primo anno di univ...:stordita:

:old::sob::cry:

[marko.fatto]

:eek:
Per me sono passati dieci anni dal primo anno di univ...:stordita:

:old::sob::cry:

ma io l'ho fatta in quarta itis :stordita:

[^TiGeRShArK^]

ma io l'ho fatta in quarta itis :stordita:

vabbè io pure in 4° superiore, il primo anno all'univ è stato l'ultima volta che l'ho incontrato :p

[Dark Phoenix]

Wow non mi ero accorto dei contest di programmazione....

volevo chiedervi una cosa.... se anche qui c'è libertà assoluta di rappresentazione il problema si risolve in tempo costante (togliendo il caricamento della matrice logicamente)...

basta rappresentare la matrice non banalmente con un array di array.
Se pensiamo ad una matrice essa non è altro che una funziona che associa a due indici "i" e "j" un valore "v", be io potrei dire che ad un valore "v" è associato un insieme di coppie "(i, j)" dove "i" e "j" sono gli indici della matrice.

Il problema così si trasforma e diventa semplicemente vedere se esiste un valore come chiave nella mia struttura dati (circa costante per un hash map per dirne una)


Faccio un esempio pratico:
Matrice

[ 1, 2, 3]
[ 2, 4, 6]
[ 8, 9, 9]


la rappresento così

1 -> [(1, 1)]
2 -> [(1, 2), (2, 1)]
3 -> [(1, 3)]
4 -> [(2, 2)]
6 -> [(2, 3)]
8 -> [(3, 1)]
9 -> [(3, 2), (3,3)]

e voilà ricerca costante, che ne pensate?

[gugoXX]

Wow non mi ero accorto dei contest di programmazione....
...

e voilà ricerca costante, che ne pensate?

Certo. Complessita' costante proporzionale al numero di celle, ovvero
O(N * M)

Se non sbaglio le ultime soluzioni erano O(N + M)
(d'altronde non stai usando l'informazione di ordinamento della matrice originale, che in qualche modo potrebbe aiutarti nella ricerca)

[Dark Phoenix]

Aspetta non capisco.... il caricamento della matrice lo debbono pagare tutti altrimenti si sta creando un programma che non risolve il problema in generale o no :confused: :help:

edit

a meno che non ipotizzino delle cose sul file (come i bit per valore) e ne vadano a caricare solo delle porzioni leggendo i valori. È così?

[gugoXX]

Aspetta non capisco.... il caricamento della matrice lo debbono pagare tutti altrimenti si sta creando un programma che non risolve il problema in generale o no :confused: :help:

edit

a meno che non ipotizzino delle cose sul file (come i bit per valore) e ne vadano a caricare solo delle porzioni leggendo i valori. È così?

Fai finta di dover costruire una funzione che,
data in ingresso una matrice avente quelle caratteristiche... etc.

Non e' detto che la matrice sia per forza su un file. Magari e' una matrice ottenuta da un passo precedente di esecuzione di un qualcosa.
E infatti nei computi abbiamo tralasciato la lettura della matrice.

[Dark Phoenix]

aah ok ora ho capito grazie

al prossimo contest ^^

[Vincenzo1968]

up

:bimbo: