Matematicki problem

[dee]

imamo matricu MxN. popunjena je nulama, osim na proizvoljnim mjestima jedinicama. potrebno je pronaci najvecu matricu popunjenu samo jedinicama unutar velike.


dakle, nesto kao

0 0 1 1 0
0 1 1 1 0
0 0 1 1 1
1 1 1 1 1
0 0 0 0 0

ako je ovo pocetna matrica, algoritam bi trebao vratiti 3. i 4. stupac (bez zadnjeg reda)


ima li ko ideju kako uopce pristupit problemu?


bilo bi dosta jednostavnije da se trazi kvadratna, ali treba bas proizvoljan mxn

[Edit: dana matrica slucajno je kvadratna. opci slucaj je mxn osnovne matrice, takodjer]

[filmil]

Како дефинишеш највећу (под)матрицу?

ф

[dee]

Originalno napisao filmil

Како дефинишеш највећу (под)матрицу?

ф

kao najvecu sastavljenu od samih jedinica, bez ijedne nule.

[filmil]

Разумео сам да је попуњена јединицама. Али шта значи „највећа“.

Да објасним: шта се дешава ако имаш две пуне подматрице 3x4? Која од те две подматрице је највећа?

Шта се дешава ако имаш пуну подматрицу 1x12 и 3x4? Која од те две подматрице је највећа?

Кад се каже „највећа“ онда се подразумева да може да постоји само једна. Кад се каже „максимална“, онда може да буде више максималних. Али прво мора да се установи мера по којој се матрице уређују. Кад сам питао, мислио сам на дефиницију мере.

ф

[dee]

Originalno napisao filmil

Разумео сам да је попуњена јединицама. Али шта значи „највећа“.

Да објасним: шта се дешава ако имаш две пуне подматрице 3x4? Која од те две подматрице је највећа?

Шта се дешава ако имаш пуну подматрицу 1x12 и 3x4? Која од те две подматрице је највећа?

Кад се каже „највећа“ онда се подразумева да може да постоји само једна. Кад се каже „максимална“, онда може да буде више максималних. Али прво мора да се установи мера по којој се матрице уређују. Кад сам питао, мислио сам на дефиницију мере.

ф

u pravu si, nisam do kraja precizan.

najveca je ona koja ima najvise jedinica i takva je uvijek samo jedna.

[filmil]

Падају ми на памет два приступа. Један је грубом силом, а сложеност је O[max(m,n)^4].

Други треба да обори сложеност на нешто мање.

Први је лакши за објашњавање.

Прво нам треба предикат који за задате координате углова подматрице (нпр. горњи-леви и доњи-десни) одређује да ли је подматрица пуна. Подматрица је пуна ако у њој нема нула.

То се уради тако што се направи табела димензија m*n у којој, у ћелији (m,n) стоји збир свих поља почетне матрице, у подматрици [(0,0),(m,n)]. (тзв. дискретни интеграл) .

Ова табела се лако прави једним пролазом кроз изворну матрицу, тако што се почне од подматрице [(0,0),(0,0)], чији је дискретни интеграл просто вредност уписана у ћелију (0,0). Дискретни интеграл суседних матрица се добија на основу већ израчунатих вредности и нове ћелије.

Када се има ова табела, лако је да се одреди дискретни интеграл било које подматрице [(p,q),(r,s)] као:

DI[(p,q),(r,s)] = DI[(0,0),(r,s)]*[r>0,s>0] - DI[(0,0),(p-1,r)]*[p>1,r>0] - DI[(0,0),(s,q-1)]*[s>0,q>1] + DI[(0,0),(p-1,q-1)]*[p>1,q>1]

овде је DI(x) дискретни интеграл подматрице, а x = [(x,y),(z,т)], тј. пар тачака које редом одређују горњи-леви и доњи десни угао. (ћелија 0,0 је горе-лево а координате расту надесно, одн. надоле); [.] је индикатор функција (тзв. Ајверсонов [Iverson] индикатор), који има вредност 1 када је услов наведен унутар индикатора тачан, одн. 0 ако је услов наведен у индикатору нетачан.

(НБ: [t>=0] је Хевисајдова функција, позната свима који су се бавили рецимо обрадом сигнала)

Ако је дискретни интеграл неке подматрице једнак њеној површини, онда је матрица пуна. Ова провера може да се одради у константном времену, кад смо једном срачунали DI.

Онда направимо два итератора по елементима матрице и пробамо све могуће комбинације горњих левих и доњих десних ћошкова подматрице. То су укупно 4 обгрљене петље.

Проверимо DI да откријемо да ли је посматрана подматрица пуна. Ако јесте, сачувамо је као највећу, под условом да је већа од највеће дотад пронађене.

Када се петље заврше, највећа пуна подматрица је сачувана.

ф