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]

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

ф

kao najvecu sastavljenu od samih jedinica, bez ijedne nule.

[filmil]

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

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

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

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

ф

[dee]

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

Да објасним: шта се дешава ако имаш две пуне подматрице 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 да откријемо да ли је посматрана подматрица пуна. Ако јесте, сачувамо је као највећу, под условом да је већа од највеће дотад пронађене.

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

ф

[filmil]

Други метод је мало сложенији. Заснива се на парцијалном решавању.

Да би решио проблем за матрицу [(0,0),(m,n)] треба прво да га решиш за матрице: [(0,0),(m,n)], [(0,0),(m-1,n)], [(0,0),(m,n-1)] и [(0,0),(m-1,n-1)].

То значи да треба да кренемо са решавањем од [(0,0),(1,1)] и да радимо ка већим матрицама.

За сваку матрицу коју испиташ, памтиш следеће: листу максималних пуних матрица дотад откривених; листу максималних пуних матрица дотад откривених, које се наслањају на доњу ивицу подматрице; и листу максималних пуних матрица које се наслањају на десну ивицу подматрице.

Ове листе могу инкрементално да се праве на основу претходно израчунатих матрица. На пример, на основу срачунатих листа за [(0,0),(p,q)], можеш да срачунаш листе за [(0,0),(p+1,q)] и [(0,0),(p,q+1)]. Листе са „ослоњеним“ подматрицама требају ти, јер то су једине које могу да „порасту“ додавањем једног додатног реда или колоне на постојећу подматрицу.

Оне могу да „порасту“ додавањем пуне подматрице-колоне или подматрице-реда, које имају одговарајуће димензије. За проверу да ли су подматрица-колона одн. подматрица ред пуни, можеш да користиш предикат из претходне поруке.

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

ф

[dee]

drugi nisam bas razumio, ali prvi mi je vise manje jasan i cini mi se sasvim dovoljan.


puno ti hvala!