Pogledajte određenu poruku
Staro 04. 08. 2007.   #6
filmil
хардвераш
Qualified
 
Datum učlanjenja: 04.01.2007
Lokacija: Маунтин Вју, САД
Poruke: 117
Hvala: 4
25 "Hvala" u 10 poruka
filmil is on a distinguished road
Default

Падају ми на памет два приступа. Један је грубом силом, а сложеност је 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 je offline   Odgovorite uz citat