Опсежно пребарување е техника за решавање на проблеми која се базира на фактот дека компјутерите, всушност, се неверојатно многу брзи, и можат да извршуваат милиони операции во секунда. Оваа техника, иако е навистина едноставна како идеја, треба да е првото нешто на што ќе помислите кога разгледувате одреден проблем и размислувате за негово решавање. Истата е позната и под името “создади и провери”, бидејќи начинот на решавање се состои од создавање на сите можни решенија, и потоа проверка кое од нив ги задоволува критериумите на задачата која ни е дадена. Притоа, самото пишување на програмскиот код е најчесто многу едноставно.

На пример, нека за време на еден натпревар ни е дадена задача каде треба да изброиме колку делители има даден број N. Притоа, во задачата е наведено ограничување дека N ќе биде цел број не поголем од 1000. Во овој случај, решението со техниката на опсежно пребарување се состои во проверка на сите броеви помеѓу 1 и 1000, и броење колку од нив се навистина делители на N. Бидејќи компјутерите се навистина брзи при правење на пресметки, ова решение ќе работи исклучително брзо, и ќе го отпечати точниот одговор за само неколку милисекунди.

#include <iostream>
using namespace std;

int countDivisors(int N)
{
     int divisors = 0;
     
     for(int i=1; i <= N; i++)
     {
          if (N%i == 0) 
          {
               divisors++;
          }
          
     }
     
     return divisors;
}

int main()
{
     int N;
     cin >> N;
     
     cout << countDivisors(N) << endl;
     return 0;
}

Забележете како целата идеја кај опсежното пребарување се состои во фактот дека истото го користиме кога не не интересира дали постои поефикасно решение за одреден проблем. Едноставно, познавајќи го фактот дека компјутерите се брзи, и имајќи ги предвид ограничувањата кои ни се дадени во проблемот кој го решаваме, одлучуваме дека оваа техника е доволно добра за решавање на соодветниот проблем.

Притоа, постојат огромен број на проблеми каде опсежното пребарување ќе ви користи, и каде ќе можете брзо и едноставно да дојдете до бараната пресметка без непотребно усложнување на проблемот или барање на поефикасни решенија. Доколку, додека работите како инженер за развој на софтвер во одредена компанија, некој ве замоли да пресметате колкава е просечната плата која им се исплатува на работниците во компанијата, а вие знаете дека во вашата компанија има до 100 вработени – едноставно, напишете програма која ќе се поврзе на системот на компанијата, ќе ја земе платата за секој работник, и ќе ја отпечати просечната вредност. Повторно, иако можеби постои поефикасно решение за овој проблем (на пример, можеби сите инженери во компанијата добиваат идентична плата и слично, па тоа може да се искористи за пишување на побрзо решение), вас тоа не ве интересира, и нема потреба таквата идеја понатака да се анализира. Едноставно, компјутерите немаат проблем да прават илјадници пресметки во краток временски интервал, и тоа треба да го користите колку што е можно.

Да го цитирам KISS принципот забележан од Американската Морнарица во 1960 година: “Нека биде едноставно, и глупаво”. Многу системи функционираат најдобро кога се чуваат и дизајнираат едноставни. Непотребната сложеност треба да се избегнува секогаш кога е тоа возможно.

Да разгледаме сега уште еден пример. Нека ни е дадена шаховска табла (со стандардна големина, 8x8), и 3 топови (топот претставува шаховска фигура) распоредени на таблата. На колку различни позиции на таблата може да се стави 4-тиот топ, така што тој нема да биде нападнат од ниту еден од другите топови. Притоа, доколку не сте играле шах досега, треба да знаете дека топовите може да напаѓаат фигури кои се наоѓаат во нивниот ред на таблата (значи, хоризонтално) или во нивната колона (вертикално).

И кај овој пример, забележете колку малку состојби навистина има на таблата. Имено, бидејќи таблата е со големина 8x8=64, само толку полиња треба да провериме како можна позиција на новиот топ. Доколку одредена позиција е слободна (на неа нема топ), и таа позиција не се наоѓа во ред или колона нападната од некој од 3-те почетни топа, се работи за валидна позиција.

Да разгледаме програма која го решава овој проблем. За чување на позициите на 3-те почетни топа, ќе користиме пар од цели броеви pair<>. Забележете како, во функцијата possiblePositions(), ги испробуваме сите 8x8 можни позиции за новиот топ.

#include <iostream>
using namespace std;

int possiblePositions(pair<int, int> rook1, pair<int, int> rook2, pair<int, int> rook3)
{
     int counter = 0;
     
     for(int row=1; row <= 8; row++)
          for(int col=1; col <= 8; col++)
          {
               if(rook1.first == row || rook1.second == col)
               {
                    //ista pozicija kako rook1, ili napadnata od rook1
                    continue;
               }
               
               if(rook2.first == row || rook2.second == col)
               {
                    //ista pozicija kako rook2, ili napadnata od rook2
                    continue;
               }
               
               if(rook3.first == row || rook3.second == col)
               {
                    //ista pozicija kako rook3, ili napadnata od rook3
                    continue;
               }
               
               //validna pozicija, ne e napadnata od nitu eden top
               counter++;
          }
     
     return counter;
}

int main()
{
     pair<int, int> rook1;
     cin >> rook1.first >> rook1.second;
     
     pair<int, int> rook2;
     cin >> rook2.first >> rook2.second;
     
     pair<int, int> rook3;
     cin >> rook3.first >> rook3.second;
     
     cout << possiblePositions(rook1, rook2, rook3) << endl;
     return 0;
}

Многу важен проблем кој се среќава при работа со текстуални низи од податоци (стрингови), е проверка дали еден стринг се содржи во друг. На пример, “abc” се содржи во “xyabcZ”. Да се обидеме да напишеме програма која го решава овој проблем со техниката на опсежно пребарување. Алгоритамот кој ќе го напишеме ќе го прави следното: најпрвин, истиот ќе провери дали бараниот стринг се содржи на почеток (првите знаци), па дали се содржи почнувајќи од втората позиција, итн, се додека за истиот не биде пронајдена неговата почетна позиција (се разбира, доколку таква воопшто постои).

#include <iostream>
#include <string>
using namespace std;

bool contains(string large, string small)
{
     for(int i=0; i + small.size() <= large.size(); i++)
     {
          bool allMatched = true;
          for(int j=0; j < small.size(); j++)
          {
               if(small[j] != large[i + j])
               {
                    allMatched = false;
                    break;
               }
          }
          
          if(allMatched == true)
          {
               //go pronajdovme vo large, istiot pocnuva od pozicija i
               return true;
          }
     }
     
     return false;
}

int main()
{
     string large, small;
     cin >> large >> small;
     
     cout << contains(large, small) << endl;
     return 0;
}

Притоа, во програмата дадена погоре, може да забележите дека за почетна позиција ги разгледуваме сите броеви од 0, па се додека важи условот (i + small.size() <= large.size()), бидејќи нема потреба да разгледуваме позиции на крајот доколку во large нема доволно преостанати знаци за да се пронајдат сите кои се наоѓаат во стрингот small.

Во наредните предавања, ќе разгледаме и како, со помош на рекурзија, може да создаваме потенцијални решенија, но и како ефикасно да ги создадеме сите можни подмножества од некои елементи. На пример, нека имаме три лица, и нека тие треба да поминат одреден мост, а програмата да провери дали е најдобро да отиде само 1 (и тоа кој), двајца (кои), или сите тројца наеднаш. Поконкретно, за {1, 2, 3}, валидни подмножества се {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}. Верувале или не, сите овие подмножества можеме да ги создадеме со само една for наредба.

Засега, да повториме уште еднаш дека техниката за опсежно пребарување е нешто на што треба сериозно да сметате кога се обидувате да решите одреден проблем. Како конкретна бројка, можете да земете дека еден компјутер може да направи околу 100 000 000 (100 милиони) операции во една секунда. Доколку вашиот алгоритам се базира на опсежно пребарување, понатаму за него се потребни малку операции, и временските ограничувања кои и се дадени на вашата програма го дозволуваат тоа, тогаш искористете ја техниката на опсежно пребарување. Едноставно, нема причина непотребно да усложнувате одредени проблеми, или да барате поефикасни решенија од она што е потребно.

Конкретно, за примерот со делители кој го споменавме на почеток, доколку ви е дадено дека максималната вредност за N е 1000, тоа очигледно е доволно брзо. Доколку N може да е многу поголем број (на пример, до 1 000 000 000 000), тогаш е потребно да бараме поефикасен алгоритам (каков и ќе разгледаме во предавањето за алгоритми поврзани со математика).

Притоа, кога веќе знаете како да ја пресметате временската сложеност на вашите алгоритми, можете и лесно да пресметате како одредено решение ќе се однесува во реалноста. На пример, доколку максималната вредност за N e 1 000 000, алгоритам со линеарна сложеност O(N) лесно ќе заврши за помалку од една секунда, но алгоритам со квадратна сложеност O(N²) нема.

Забелешка за натпреварувачи по информатика: Голем број на задачи доделуваат парцијални поени (на пример, 30 поени од можните 100 за задачата), доколку создадете алгоритам кој функционира за помали ограничувања. Кај овие задачи, доколку е тоа возможно и не ви текнува ништо попаметно, користете опсежно пребарување за освојување на тие поени - бидејќи за време на натпревар, секој поен кој ќе го освоите е значаен. Дополнително, кога користите опсежно пребарување, можете и, по извршување на алгоритамот на вашиот компјутер, да забележите нешто кај задачата кое не ви било очигледно на почеток (на пример, сите решенија се прости броеви или слично), што ќе ви помогне таа задача да ја решите и целосно - за сите поени.

Дозвола за користење: CC BY-NC 2.5 ©