DevProTalk

DevProTalk (http://www.devprotalk.com/index.php)
-   Programiranje (http://www.devprotalk.com/forumdisplay.php?f=23)
-   -   Matematicki problem (http://www.devprotalk.com/showthread.php?t=3298)

dee 03. 08. 2007. 23:03

Matematicki problem
 
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 03. 08. 2007. 23:37

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

ф

dee 03. 08. 2007. 23:39

Citat:

Originalno napisao filmil (Napišite 39790)
Како дефинишеш највећу (под)матрицу?

ф

kao najvecu sastavljenu od samih jedinica, bez ijedne nule.

filmil 03. 08. 2007. 23:46

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

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

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

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

ф

dee 03. 08. 2007. 23:51

Citat:

Originalno napisao filmil (Napišite 39792)
Разумео сам да је попуњена јединицама. Али шта значи „највећа“.

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

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

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

ф

u pravu si, nisam do kraja precizan.

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

filmil 04. 08. 2007. 02:53

Падају ми на памет два приступа. Један је грубом силом, а сложеност је 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 04. 08. 2007. 03:17

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

Да би решио проблем за матрицу [(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 06. 08. 2007. 18:28

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


puno ti hvala!


Vreme je GMT +2. Trenutno vreme je 22:08.

Powered by vBulletin® Verzija 3.6.8
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Copyright © DevProTalk. All Rights Reserved.

Mišljenja, saveti, izjave, ponude ili druge informacije ili sadržaji nastali na Sajtu su vlasništvo onoga ko ih je kreirao, a ne DevProTalk.com, tako da ne morate da se oslanjate na njih.
Autori poruka su jedini odgovorni za ovakve sadržaje. DevProTalk.com ne garantuje tačnost, kompletnost ili upotrebnu vrednost informacija, stavova, saveta ili datih izjava. Ne postoje uslovi pod kojima bi mi bili odgovorni za štetu ili gubitak koji je posledica bilo čijeg oslanjanja na nepouzdane informacije, ili bilo kakve informacije nastale kroz komunikaciju između registrovanih članova.
Web sajt može sadržavati linkove na druge web sajtove na Internetu ili neke druge sadržaje. Ne kontrolišemo niti podržavamo te druge web sajtove, niti smo pregledali bilo kakve sadržaje na takvim sajtovima. Mi nećemo biti odgovorni za legalnost, tačnost ili prikladnost bilo kog sadržaja, oglasa, proizvoda, usluga ili informacije lociranim na ili distribuiranih kroz druge web sajtove, niti za bilo kakvu štetu nastalu kao posledica takvih informacija. DevProTalk.com drži i čuva druga prava vlasništva na web sajtu. Web sajt sadrže materijale zaštićene copyright-om, zaštitne znakove i druge informacije o pravu vlasništva ili softver. Članovi mogu poslatu informacije zaštićene pravima vlasništva njihovih nosilaca i ona ostaju zaštićena bez obzira da li su oni koji prenose te informacije to naveli ili ne. Osim informacija koje su u javnom vlasništvu ili za koje dobijete dozvolu, nemate pravo da kopirate, modifikujete ili na bilo koji način menjate, objavljujete, prenosite, distribuirate, izvršavate, prikazujete ili prodajte bilo koju informaciju zaštićenu pravima vlasništva. Slanjem informacija ili sadržaja na bilo koji deo DevProTalk.com, Vi automatski dozvoljavate i predstavljate garanciju da imate pravo da dozvolite DevProTalk.com ili članovima DevProTalk.com bespovratnu, kontinualnu, neograničenu, globalnu dozvolu da koriste, kopiraju, izvršavaju, prikazuju i distribuiraju takve informacije i sadržaje i da iz takvih sadžaja koriste bilo koji deo u bilo koje svrhe, kao i pravo i dozvolu da koriste gore navedene sadržaje. Svi zaštitni znakovi (trademarks), logotipi, oznake usluga, firme ili imena proizvoda koji se pominju na ovom web sajtu su vlasništvo kojim raspolažu njihovi vlasnici.