[Algorytmy] Tablica dwuwymiarowa- maksymalna suma podtablicy

Awatar użytkownika
cyberciq
Użytkownik
Użytkownik
Posty: 450
Rejestracja: 19 kwie 2010, o 15:03
Płeć: Mężczyzna
Podziękował: 5 razy
Pomógł: 43 razy

[Algorytmy] Tablica dwuwymiarowa- maksymalna suma podtablicy

Post autor: cyberciq » 28 sie 2011, o 19:40

Myślę, że jest to dosyć znane zadanie. Mamy sobie tablicę dwuwymiarową liczb całkowitych. Zadaniem programu jest wypisać maksymalną sumę liczb spójnej prostokątnej podtablicy zawartej w naszej tablicy. Jeśli tablica jest wypełniona tylko dodatnimi lub tyko ujemnymi liczbami to rezultat jest trywialny. Jeśli jednak mamy pomieszane liczby dodatnie i ujemne to pierwsze rozwiązanie, które od razu nasuwa się na myśl jest takie, że bierzemy sobie jakiś "róg" danej tablicy i za pomocą pętli znajdujemy wszystkie możliwe podtablice, których dany wierzchołek jest odpowiednio w tym wierzchołku powtarzając dla pozostałych pól,podtablice sumujemy i porównując otrzymujemy szukaną wartość. Oczywiście taki algorytm działa wolno dla dużych danych więc jeśli ktoś ma jakieś pomysły jak zoptymalizować jego działanie lub wymyślić coś innego to proszę aby się nim podzielił.

pozdrawiam
Ostatnio zmieniony 29 sie 2011, o 14:53 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.

Awatar użytkownika
argv
Użytkownik
Użytkownik
Posty: 569
Rejestracja: 27 maja 2009, o 01:27
Płeć: Mężczyzna
Podziękował: 51 razy
Pomógł: 66 razy

[Algorytmy] Tablica dwuwymiarowa- maksymalna suma podtablicy

Post autor: argv » 28 sie 2011, o 20:18

Całkiem niezłe rezultaty daje zastosowanie sum prefiksowych. Założe, że tablica jest kwadratowa. O sumach prefiksowych w tablicy 2d możesz poczytać w książeczce do 8 oi (zadanie Mapa Gęstości).

Kod: Zaznacz cały

for ( i = 1; i <= n; i++) {    for ( j = 1; j <= n; j++) {            wczytaj(sum[i][j]) ;            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + sum[i][j] ;    }}  
No i teraz 4 pętle:

Kod: Zaznacz cały

int max_sum(int n){    int temp;    int max = -INF ;    for(int i = 1; i <= n; i++)    for(int j = 1; j <= n; j++)        // Podprostokąt zaczynający się w (p,q)        for(int p = i; p <= n; p++)        for(int q = j; q<= n; q++) {            temp = sum[p][q] - sum[p][j-1] - sum[i-1][q] + sum[i-1][j-1] ;            if (temp > max)                max = temp ;        }        return max ;}  
Przechodzi testy na UVa Online Judge (to chyba stamtąd robiłem to zadanie). Istnieje lepszy algorytm, ale skoro ten działał dość szybko i był prosty, to nie chciało mi się tamtego zgłębiać.

adambak
Użytkownik
Użytkownik
Posty: 1272
Rejestracja: 8 sty 2011, o 18:18
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 295 razy
Pomógł: 115 razy

[Algorytmy] Tablica dwuwymiarowa- maksymalna suma podtablicy

Post autor: adambak » 28 sie 2011, o 20:34

argv, to drugie rozwiązanie pewnie opiera się o drzewo przedziałowe?

Awatar użytkownika
Zordon
Gość Specjalny
Gość Specjalny
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 909 razy

[Algorytmy] Tablica dwuwymiarowa- maksymalna suma podtablicy

Post autor: Zordon » 28 sie 2011, o 20:37

Z tego co widzę to powyższe jest \(\displaystyle{ O(n^4)}\), już dużo lepiej niż brutalnie, ale można poprawić do \(\displaystyle{ O(n^3)}\) i algorytm wciąż będzie bardzo prosty.
Robimy sobie powiedzmy sumy prefiksowe dla każdej kolumny: \(\displaystyle{ s[i][j]=t[0][j]+t[1][j]...+t[i-1][j]}\), to dosyć łatwo wyliczyć w \(\displaystyle{ O(n^2)}\). Teraz mogę liczyć takie sumy: \(\displaystyle{ t[k][j]+t[k+1][j]...+t[l][j]}\) w czasie \(\displaystyle{ O(1)}\) (dla dowolnych \(\displaystyle{ k,l,j}\)).
Dzięki temu możemy dla każdego poziomego paska (taki pasek to wiersze od pozycji \(\displaystyle{ p}\) aż do \(\displaystyle{ q}\)) rozwiązać problem dla jednowymiarowej tablicy (maksymalna suma podtablicy). Czyli złożoność to \(\displaystyle{ O(n^2 \cdot T(n))}\) gdzie \(\displaystyle{ T(n)}\) to koszt rozwiązania problemu w wersji 1-wymiarowej, który jest liniowy. Polecam wymyślić samemu.

edit: chyba da się też zrobić to w czasie \(\displaystyle{ O(n^2\cdot p(\log n))}\) gdzie \(\displaystyle{ p}\) jest wielomianem, chyba kwadratowym. W praktyce raczej zadziała to nawet wolniej.

Xitami

[Algorytmy] Tablica dwuwymiarowa- maksymalna suma podtablicy

Post autor: Xitami » 1 wrz 2011, o 12:01


ODPOWIEDZ