Се мислев како да го именувам денешново пишување. Даден ни е следниот проблем:
Дадена ни е матрица. Секој член на матрицата има некоја вредност. Се смета дека вредностите на матрицата нема да се менуваат периодично (ова е многу важен услов чие значење ќе биде објаснето подоцна).
Ќе го дефинираме поимот подматрица.
Ќе го објаснам графички. На сликата ни е дадена матрица А, и нејзина подматрица B.
Се бара да се напише алгоритам кој на најефикасен начин би го пресметал збирот на елементите во подматрицата B.
Ова е интересен проблем кој бара размислување и анализа. Би го класифицирал во архетипот динамичко програмирање иако може слободно да го вметнеме и во групата на математички проблеми (подоцна ќе објасниме зошто). Со проблемов се сретнав на втор колоквиум по предметот Алгоритми и структури на податоци.
Постепено ќе го анализирам проблемот во чекори. Следниве чекори можат да се применат и во други проблеми.
Прво треба проблемот добро да се сфати. Треба да се анализира што се бара и да се разгледаат примерите доколку ги има. Доколку уште не е јасно, треба да се проба со свои примери да се сфати и анализира проблемот. На пример во случајот со нашата задача
ред 1: 1 2 3
ред 2: 4 5 6
ред 3: 7 8 9
Ги нумерирам редовите и колоните почнувајќи од еден наместо од нула заради полесна имплементација. Со анализа на кодот ќе биде појасно зошто.
Ние треба да напишеме функција sum(x1, y1, x2, y2) каде што (x1, y1) ни е горниот лев агол на подматрицата, а (x2, y2) ни е долниот десен агол на матрицата. Оваа функција треба да го врати збирот на елементите во овој потправоаголник (подматрица). Во нашиот пример:
sum(1, 1, 3, 3) = 45
sum(1, 1, 2, 3) = 27
sum(1, 1, 1, 3) = 12
sum(2, 1, 3, 3) = 33
sum(2, 1, 2, 1) = 2
...
Никогаш не преминувајте на следната фаза доколку добро не го сфатите проблемот. Дури и кога мислите дека сте го сфатиле, напишете си неколку примерчиња, за секој случај. Не само што тоа ќе ви помогне да го сфатите проблемот подобро, туку може и да ви даде идеја за наоѓање на решение!
Следна фаза, барање на решение на проблемот.
Најпрост алгоритам е следниот. Ја читаме цела матрица и потоа "со два фора" ги поминуваме сите елементи што се во подматрицата и ги собираме. Многу едноставно. Но се бара најефикасен начин. Претходниов начин би бил брз да речеме за матрица со 1000x1000 елементи, релативно брз затоа што тоа би се извршило за помалку од секунда по повик на функцијата sum(x1, y1, x2, y2). Оставам на вас да размислете зошто не е ефикасно, што би можело да се подобри овде, дали можеби некои пресметки би се вршеле по повеќе пати? На кој начин би можело ова да се оптимизира?
Ефикасноста се подобрува со користење на некои готови резултати.
Прва оптимизација би била ако имаме една акумулациона матрица за колони (аналогно е за редови). Оваа матрица би имала ист број на елементи како и оригиналната матрица. Што е логиката на оваа акумулациона матрица за колони. Елементот со индекс (i, j) означува сума на сите вредности од оригиналната матрица кои што се наоѓаат во ј-тата колона, а кои се наоѓаат во ред со индекс <= i. Потоа во методот sum би имале само еден "for" т.е. би имале линеарна комплесност од една димензија на матрицата! Нема да навлегувам во детали како би се имплементирала функцијата sum во овој случај бидејќи не е тешко да се сфати доколку се размисли малку.
Откако ќе го сфатиме претходниот начин, се прашуваме дали можеме да одиме подалеку, т.е. дали можеме да ја оптимизираме функцијата толку многу што таа ќе работи во време O(C) каде што C е константа со мала вредност? Одговорот на ова прашање е да. Се служиме со сличен принцип како претходниот. Имаме две фази, имплементирање на акумулационата матрица и втора фаза имплементирање на методот sum.
Акумулациона матрица. Оваа матрица има исти димензии како и оригиналната матрица. Индексот (i, j) во матрицата означува дека вредноста поврзана со тој индекс е збир на сите елементи во матрицата кои се наоѓаат во ред со индекс <= i и во колона со индекс <= j.
Во примерот даден претходно, матрицата на акумулација би ги имала следниве вредности
ред 1: 1 3 6
ред 2: 5 12 21
ред 3: 12 27 45
Генерирањето на оваа матрица се одвива во време на едно читање на матрицата, што значи најбрзо можно. Откако ќе ги објасниме принципите како се користи акумулационата матрица, ќе се навратиме на делот како најефикасно да се креира оваа акумулациона матрица.
Кратките и едноставни формули се добар показател дека користиме динамичко програмирање. Во зависност од тоа дали имаме bottom-to-up или up-to-bottom пристап, динамичкото програмирање можеме да го имплементираме итеративно или со рекурзија и мемоизација. Подетално за овие техники во друга прилика. Динамичкото програмирање овде е покарактеристично кај создавањето на акумулационата матрица, техниката за пресметка во методот sum би го нарекол само "математичка финта" :)
Значи при дадена акумулациона матрица М (да напоменеме дека во случајот x1 <= x2 и y1 <= y2),
sum(x1, y1, x2, y2) = m(x2, y2)-m(x1, y2)-m(x2, y1)+m(x2, y2)
Оваа формула многу добро се објаснува графички. Ако со симболи ги означиме правоаголниците тогаш добиваме дека:
area(E) = area(A)-area(B)-area(C)+area(D)
Акумулационата матрица може да се добие на сличен принцип. Тоа убаво се гледа од кодот, поточно во фукцијата generate(). Во програмата вметнав и една функција за тестирање.
Се надевам го сфативте начинот на кој треба да се пристапи кон решавање на оваа задача. Да бидам искрен, тогаш на колоквиум не ми текна овој начин, туку ја решавав задачата со вториот принцип со акумулациона матрица по колони. Пред неколку месеци се навратив на проблемот и ми текна на интересниот принцип што се користи кај двојните интеграли. Добар е проблемов за да се извежба принципот на оптимизирање на решенијата и динамичко програмирање иако не се користи баш тој архетип.
Проблемот би бил целосно поинаков доколку вредностите во матрицата се менуваат периодично. Во тој случај нема да важи опишаниот алгоритам бидејќи нашите пресметки се засноваа на почетната пресметка, периодичното менување на вредностите во матрицата би предизвикало и менување на акумулационата матрица, а токму постојаноста на акумулационата матрица беше факт врз кој ја градевме функцијата sum(x1, y1, x2, y2). Проблемот кога можеме да имаме промени на вредности и повикувања на функцијата sum се решава на принцип многу поразличен од претходно опишаниот, тој принцип не се вбројува во архетипот динамичко програмирање. Еден од начините за решавање на овој проблем е со користење на бинарни индексни стебла, многу ефикасни и навидум сложени, но сепак едноставни структури доколку се сфати принципот на кој тие функционираат. Овде нема да се задржувам на бинарните индексни стебла, но сигурно во некој од наредните post-ови ќе пишувам опширно.
