AVL стебла

AVL стебло е балансирано бинарно стебло. За AVL стеблата важи, висините на двете потстебла секој јазол се разликуваат најмногу за 1 па затоа се вели дека е балансирано по висина. Пребарување, додавање на елемент и бришење се со комплексност O(log N) време, ова е просечно време и најлошо време истовремено, кадe N е број на јазли во стеблото пред операцијата. Додавање и бришење на елемент како операции може да вклучат ребалансирање на стеблото со една или повеќе ротации на стеблото.

AVL е многу корисно за решавање на разни типови на проблеми кај кои се бара голема ефикасност. Следува мојата имплементација (во Java) и објаснување за секоја операција поединечно. Ви препорачувам пред да го разгледате кодот да прочитате повеќе за AVL стеблата, на крај има линкови.

class Node {
Node left;
Node right;
Node parent;
int value;
int height;

Node () {
 left = null;
 right = null;
 parent = null;
 height = 1;
}

Node (int value) {
 left = null;
 right = null;
 this.value = value;
 height = 1;
}

}

Јазелот е посебна класа која се состои од покажувачи кон левото и десното дете, покажувач кон родителот, вредноста што ја чува јазелот т.е. клучната информација според која се сортираат податоците (во овој случај е број) и висина на стеблото.

int getHeight(Node mom) {
if (mom == null) return 0;
return mom.height;
}

int ballanceFactor(Node mom) {
if (mom == null) return 0;
int lh = getHeight(mom.left);
int rh = getHeight(mom.right);
return rh-lh;
}

getHeight ја имплементирав посебно, иако во секој јазел постои променлива height. Ова е со цел да се избегне разгледување на специјален случај кога нема лево или (и) десно дете. Втората функција го дава факторот на балансираност на левото и десното потстебло, доколку вредноста што се враќа е позитивна, тоа значи дека десното потсетбло има поголема висина од левото.

Следува објаснувањето за "најкомплицираниот" дел, ротацијата. На сликата се објаснети четирите случаи (кои воглавно се сведуваат на два симетрични).

Node rightRightCase(Node mom) {
if (mom == null) return null;

Node R = mom.right;
Node T2 = R.left;

if (mom.parent.left == mom) {
 mom.parent.left = R;
} else {
 mom.parent.right = R;
}

R.parent = mom.parent;

R.left = mom;
mom.parent = R;

mom.right = T2;
if (T2 != null) T2.parent = mom;

mom.height = Math.max(getHeight(mom.left), getHeight(mom.right))+1;
R.height = Math.max(getHeight(R.left), getHeight(R.right))+1;

return R;
}

Оваа функција како аргумент прима некој јазел кој е корен на стебло. После ротацијата како резултат функцијата го враќа новиот корен на ова потстебло, т.е. десното дете. Напомена, за да работи оваа функција, јазелот кој се испраќа како аргумент треба да има десно дете (во спротивно нема логика да се прави ваква ротација и стеблото не може да има фактор на балансираност -1 кој пак е основен предуслов за некоја друга функција да го повика овој метод).

R е десното дете, а Т2 е левото дете на јазелот mom. Она што во овој код го правиме е известување до родителот на mom дека дете веќе нема да му биде mom туку R. Потоа ги менуваме местата на mom и R, ротираме на лево. Потстеблото Т2 станува десно потстебло на Т2. Правиме ажурирање на висините на mom и R и како резултат функцијата враќа покажувач кон R, за да знае повикувачот на овој метод кој е јазелот кој си го сменил местото со mom.

Node rightLeftCase(Node mom) {
leftLeftCase(mom.right);
return rightRightCase(mom);
}

Овој случај е двојна ротација. Прво го ротираме на десно стеблото чиј корен е mom.right, па потоа вршиме ротација на лево со референтен јазел во mom.

Напомена: rightRightCase е аналогно со ротација на лево, а leftLeftCase е аналогно со ротација на десно.

Node leftLeftCase(Node mom) {
if (mom == null) return null;
Node L = mom.left;
Node T2 = L.right;

if (mom.parent.left == mom) {
 mom.parent.left = L;
} else {
 mom.parent.right = L;
}

L.parent = mom.parent;

L.right = mom;
mom.parent = L;

mom.left = T2;
if (T2 != null) T2.parent = mom;

mom.height = Math.max(getHeight(mom.left), getHeight(mom.right))+1;
L.height = Math.max(getHeight(L.left), getHeight(L.right))+1;

return L;
}

Node leftRightCase(Node mom) {
rightRightCase(mom.left);
return leftLeftCase(mom);
}

Овие два случаи се симетрични со rightRightCase(Node mom) и rightLeftCase(Node mom) и затоа нема повторно да ги објаснувам.

void ballanceTreeInsertion(Node root, Node mom) {
int a, p;

while (mom != root) {
 p = ballanceFactor(mom);
 if (p == 2) {
  // right subtree outweighs the left subtree
  // If the balance factor of R is +1, a left rotation is needed with P as the root.
  // If the balance factor of R is -1, a double left rotation is needed
 
  a = ballanceFactor(mom.right);
 
  if (a == 1) {
   mom = rightRightCase(mom);
  } else {
   if (a == -1) {
    mom = rightLeftCase(mom);
   }
  }
 
 } else {
  if (p == -2) {
   a = ballanceFactor(mom.left);
  
   if (a == -1) {
    mom = leftLeftCase(mom);
   } else {
    if (a == 1) {
     mom = leftRightCase(mom);
    }
   }
  }
 }

 mom = mom.parent;

 // we update the height of mom
 mom.height = Math.max(getHeight(mom.left), getHeight(mom.right))+1;

}

}

Во мојата имплементација, секое балансирано стебло има единствен корен root. Вистинскиот корен е во левото дете на root. Ова е со цел за да може да се претстави стебло со 0 елементи (root.left ќе биде null во тој случај). Исто така, ваква динамична структура често се менува внатрешно и root.left во различни моменти од времето може да има различни јазли, што е тешко да се претстави доколку не постои некој "поврховен" јазел како коренот со кој единствено се претставува и еднозначно се карактеризира секое стебло.

Оваа функција е клучна за добивање на балансираност на стеблото при додавање на нов елемент. Како аргумент се праќа корен на дрвото и јазелот од кој почнуваме да го балансираме дрвото. Го балансираме јазелот mom и потоа се качуваме нагоре по стеблото се додека не стигнеме до коренот. Алгоритмот за балансирање е следен: во p го сместуваме факторот на балансираност на јазелот кој го обработуваме. ДОколку овој број е 2 или -2, тоа значи дека стеблото во тој јазел е небалансирано (понатаму накратко ќе го употребувам поимот балансираност во јазел, наместо балансираност на стеблото чиј корен е конкретниот јазел). Во зависност од тоа дали десното (левото) дете има фактор на балансираност 1 или -1 се одвива единечна или двојна ротација. Пред да се качиме нагоре по хиерархијата ја ажурираме висината на јазелот кој моментално го обработуваме.

void ballanceTreeDeletion(Node root, Node mom) {
int a, p;

while (mom != root) {
 mom.height = Math.max(getHeight(mom.left), getHeight(mom.right))+1;

 p = ballanceFactor(mom);
 if (p == 2) {
  // right subtree outweighs the left subtree
  // If the balance factor of R is +1, a left rotation is needed with P as the root.
  // If the balance factor of R is -1, a double left rotation is needed
 
  a = ballanceFactor(mom.right);
 
  if ((a == 1)||(a == 0)) {
   mom = rightRightCase(mom);
  } else {
   if (a == -1) {
    mom = rightLeftCase(mom);
   }
  }
 
 } else {
  if (p == -2) {
   a = ballanceFactor(mom.left);
  
   if ((a == -1)||(a == 0)) {
    mom = leftLeftCase(mom);
   } else {
    if (a == 1) {
     mom = leftRightCase(mom);
    }
   }
  }
 }

 mom = mom.parent;

 // we update the height of mom
 mom.height = Math.max(getHeight(mom.left), getHeight(mom.right))+1;

}

}

Оваа функција е скоро идентична на претходната, со таа разлика што овде се применува ротација на лево доколку p = 2 и (а = 1 или а = 0), и ротација на десно доколку p = 2 и (а = -1 или а = 0). Првата функција ќе ја употребуваме за балансирање при додавање на елемент, втората при бришење на елемент. Доколку ве интересира зошто е ваква имплементацијата можете да прочитате повеќе во разни книги кои се занимаваат со тематика од областа на алгоритмите и структурите на податоци.

void addNode(Node root, int value) {
Node mom = root.left;
Node newnode = new Node(value);
Node prev = root;

while (mom != null) {
 if (value <= mom.value) {
  prev = mom;
  mom = mom.left;
 } else {
  prev = mom;
  mom = mom.right;
 }
}

newnode.parent = prev;

if (value <= prev.value) {
 prev.left = newnode;
} else {
 prev.right = newnode;
}

// now we need to balance the tree
mom = newnode;

ballanceTreeInsertion(root, mom);

}

addNode прима како аргумент корен и вредност која што сакаме да се смести во стеблото. Се изминува стеблото надоле додека не се дојде до некој "null елемент" и на негово место се сместува новиот. Овде важи правилото, сите лементи во левото потстебло на даден јазел се помали или еднакви на вредноста на тој јазел, а сите елементи во десното потстебло на јазелот се поголеми од неговата вредност. Откако ќе го внесеме јазелот, го балансираме новиот јазел т.е. ја повикуваме функцијата ballanceTreeInsertion која врши верижно балансирање на стеблото нагоре се до коренот.

void deleteNode(Node root, int value) {
Node mom = root.left;
Node prev = root;
Node T;
boolean found = false;

while (mom != null) {
 if (mom.value == value) {
  found = true;
  break;
 }
 if (value <= mom.value) {
  prev = mom;
  mom = mom.left;
 } else {
  prev = mom;
  mom = mom.right;
 }
}

if (found == false) {
 //System.out.println("The element was not found");
 return;
}

Node orig = mom;

if ((orig.left == null)&&(orig.right == null)) {
 // we remove the node
 mom = orig.parent;
 if (mom.left == orig) {
  mom.left = null;
 } else {
  mom.right = null;
 }
 orig = null;

 // we should be sure that the subtree with mom with it's main root element
 // has correct heights and as parametar we give valid element
 mom.height = 1;
 ballanceTreeDeletion(root, mom);
 return;
}

if ((orig.left == null)^(orig.right == null) == true) {
 // if there is exactly one subtree
 mom = orig.parent;
 if (orig.left != null) {
  T = orig.left;
  if (mom.left == orig) {
   mom.left = orig.left;
   orig.left.parent = mom;
  } else {
   mom.right = orig.left;
   orig.left.parent = mom;
  }
 } else {
  T = orig.right;
  if (mom.left == orig) {
   mom.left = orig.right;
   orig.right.parent = mom;
  } else {
   mom.right = orig.right;
   orig.right.parent = mom;
  }
 }
 orig = null;
 ballanceTreeDeletion(root, T);
 return;
}

// the node has 2 subtrees, we need to find the smallest element of the right subtree of mom
mom = orig.right;

if (mom.left == null) {
 // special case, it is more complicated to change the relations
 if (orig.parent.left == orig) {
  orig.parent.left = mom;
 } else {
  orig.parent.right = mom;
 }

 orig.left.parent = mom;
 mom.left = orig.left;
 mom.parent = orig.parent;
 orig = null;
 ballanceTreeDeletion(root, mom);
 return;
}

prev = mom;

while (mom != null) {
 prev = mom;
 mom = mom.left;
}

mom = prev;
prev = mom.parent;

// we are changing the relations instead of just changing the value

if (mom.right != null) {
 mom.right.parent = mom.parent;
}

T = mom.parent;
mom.parent.left = mom.right;

mom.parent = orig.parent;
mom.left = orig.left;
mom.right = orig.right;

if (orig.parent.left == orig) {
 orig.parent.left = mom;
} else {
 orig.parent.right = mom;
}

orig.left.parent = mom;
orig.right.parent = mom;

// now we need to balance the tree
T.height = Math.max(getHeight(T.left), getHeight(T.right))+1;
ballanceTreeDeletion(root, T);

}

Бришењето на јазел од стеблото е малку покомплицирано. Оваа функција како аргумент прима референца кон коренот и клучната вредност на јазелот што сакаме да биде избришан. Прво го пронаоѓаме јазелот во стеблото. Потоа разгледуваме неколку специјални случаи.

Доколку јазелот е лист, т.е. нема лево и десно потстебло, тогаш јазелот едноставно го бришеме, така што ги отстрануваме врските на неговиот родител кон него, и потоа ги балансираме сите јазли додека не стигнеме нагоре до коренот на стеблото.

Доколку јазелот Т има само едно потстебло, тогаш јазелот Т го отстрануваме, а притоа дете на неговиот родител ќе стане детето на Т.

Доколку јазелот Т има две потстебла, тогаш го бараме најмалиот елемент од неговото десно потстебло т.е. го бараме јазелот L (ја употребувам оваа ознака за да објаснам поубаво, во кодот е имплеменирано со променливи со друго име) кој се наоѓа "најлево" во неговото десно потстебло. Ја отстрануваме врската од неговиот родител кон L и овој јазел го ставаме на местото на Т. Т го отстрануваме. Разбирливо, потоа вршиме балансирање на стеблото од јазелот кој претходно беше родител на L. Овде разгледав специјален случај кога L e дете на T. Малку е покомплицирано да се менуваат врските доколку јазлите се директно поврзани. На крај се одвива балансираност која започнува од претходниот родител на L.

void inorder(Node mom) {
if (mom == null) return;

inorder(mom.left);
System.out.println(mom.value);
inorder(mom.right);
}

void inorderRoot(Node root) {
inorder(root.left);
}

Со повикувањето на inorderRoot(Node root) се врши inorder изминување на стеблото, а тоа значи дека ќе бидат отпечатени вредностите што ги содржи стеблото и тие ќе бидат сортирани во неопаѓачки редослед.

Се надевам дека сега некои работи ќе бидат појасни за AVL стеблата и ќе пробате самите да искодирате AVL стебло. За некои од можните примени на овие интересни и многу ефикасни структури во некоја следна прилика.

Овој код може и да содржи некои bug-ови, па се надевам дека доколку забележете некоја ќе ме информирате, а и јас ќе сменам нешто доколку мислам дека е грешно. На тестирањата кои ги вршев стеблото си ја вршеше добро својата функција.

Доколку сакате повеќе да прочитате за AVL стеблата ви препорачувам:

Introduction to Algorightms
Algorithms in C
http://en.wikipedia.org/wiki/AVL_tree

и уште многу ресурси кои можете да ги најдете пребарувајќи на google
http://www.google.com/search?hl=en&source=hp&q=avl+tree&aq=f&oq=&aqi=g7g-s1g2

Кодот заедно со некои тестови кои ги правев можете да го симнете овде:

http://www.mediafire.com/?2vnjyn2nguj

Збор два за O(logN) и стеблата

Структурите секогаш одат заедно со алгоритмите. Ефикасна имплементација е збир од ефикасни податочни структури и ефикасен алгоритам. Некогаш треба и да се прави компромис. Кај многу решенија големата комплексност може да се намали со користење на добри податочни структури. На пример, кај сортирањето, комплексноста од O(N*N) значи дека за N = 1000000 програмата нема во разумно време да даде решение.

Проблемот на сортирање е добро проучен и познати се алгоритми кои даваат решение во време O(N*logN). Овде ќе ги спомнам merge sort и мојот омилен heap sort. Другите сортирања имаат комлексност од O(N*N) во најлош случај. Но, другите сортирања освен оригиналната низа не користат друга меморија и некои релативно комплицирани структури (со исклучок на некои променливи како бројачи и променливи во кои привремено се чуваат податоци).

Кај merge sort и heap sort приказната е поинаква. Merge sort користи две низи, значи оригиналната низа и уште една низа со иста мемориска големина (едно од следните мои пишувања ќе го посветам целосно на сортирања). Heap sort пак користи само една низа, но таа низа е организирана на друг начин кој овозможува сите операции како вметнување на елемент во структурата, бришење, наоѓање на максимум или минимум да се извршуваат во O(1) или O(logN), овие неколку операции индиректно придонесуваат во она што се бара, сортирање на низата.

Стеблото е структура или поим кој се поврзува со посакуваната комплексност O(logN). Значи директно или индиректно, доколку некој проблем бара решение кое е од ред O(logN), тогаш ние ќе треба да се занимаваме со стебло, иако понекогаш стеблото не е очигледно на прв поглед, овде мислам општо, на стебло како структура и стебло како поим, како логичка организација која во својата суштина го има гранењетo.

Очекувана вредност

Последниот SRM 448 ме натера да размислувам за една од моите омилени теми - Веројатност. Првата задача беше поврзана со оваа тема. Како прва и најлесна задача, решението се добиваше рекурзивно, со собирање на веројатностите за сите можни настани. Брзо го напишав ова затоа што инстинктот ми велеше дека ова мора да биде главниот начин за добивање на конечниот резултат. Требаше да се погоди очекуваниот број на карти кои ќе се извлечат, а кои ќе донесат победа. Нема да објаснувам што се бара во задачата, неа можете да ја погледнете на topcoder. Она што не знаев е како сите информации за веројатноста да се искористат за да се добие конечниот резултат. Брзо го искодирав кодот за пресметување на веројатноста. Прво размислував малку како да го искористам она што веќе го имав, но не ми доаѓаше идеја. Потоа на 40 минути до крај малку погуглав и за среќа најдов една страна каде што многу едноставно беше објаснето како се добива очекувана вредност. Формулата е следна:

очекувана вредност = Сума од на сите настани(веројатноста за настан i * вредноста за тој настан i)

Еве да објаснам за еден едноставен пример. Имаме коцка, таа има 6 страни и на секоја страна има по една вредност од 1 до 6. При фрлање на коцката која е очекуваната вредност што ќе ја добиеме?

Значи според формулата:

expected = (1/6)*1+(1/6)*2+(1/6)*3+(1/6)*4+(1/6)*5+(1/6)*6 = (1/6)*21 = 3.5

Можеби и малку е нелогичен примеров ама добро покажува како се применува формулата за пресметување на очекувана вредност.

Повеќе за ова можете да прочитате на wikipedia.

Инаку да се вратам на приказната со настапот на SRM 448. Го имплементирав ова, и програмата не ми ги даваше потребните резултати. Значи имаше две потенцијални работи кои се причина за грешното решение. Прво, алгоритмот не е точен, и второ, имам некоја грешка во кодот. Втората опција брзо ја елиминирав мислејќи дека во толку прост код и не може да има некоја грешка, скенирајќи го набрзина кодот за да имам време да размислувам за точноста на алгоритмот. Бидејќи малку бев скептичен во врска со точноста на формулата се обидував да наоѓам други малку поинакви пристапи во крајниот алгоритам и менував некои работи во кодот кои не ми донесоа успех. На крај се откажав. Моја среќа што имаше многу натпреварувачи со ниедна решена па не ми падна многу рејтингот, сега е 1224 и останувам во DIV 1.

Кога заврши натпреварот одлучив да одморам малку. Размислував што би можело да ми биде грешката и полека го анализирав мојот код во главата. Наеднаш дојдов до проблематичниот дел. Наместо for (j=0;j0) што е грешка при брзање... Оваа грешка ме чинеше добар пласман. Алгоритмот бил добар, но сум имал грешка во имплемнтацијата.

Поука за друг пат. Секогаш разгледувај ги сите потенцијални причинители на грешната програма, и никогаш не елиминирај ниедна од можните причини колку и да изгледа дека непотребно се губи време на некоја од нив.

Тест задача

Случајно најдов на еден многу интересен сајт http://www.scarky.com/ каде може да се постави задача по програмирање. Сите параметри се местат од страна на креаторот, кодот за натпреварот сам се генерира. Можеби тоа што не би го сметал за професионален начин за организирање на натпревари е што нема можност повеќе input-и. Се надевам тоа ќе се поправи во иднина. Ајде сега да го тестираме системот. Производ на два броеви :) Напишете кодче и праќајте. Ќе се обидам наредниве денови да ставам некој попредизвикувачки проблем од областа на програмирањето.

USACO

USACO (http://ace.delos.com/usacogate) е тренинг сајт за програмирање каде секој може да се регистрира и да решава. Според мене, секој кој има елементарни познавања од програмирање и се интересира за решавање на проблеми мора задолжително да го посети сајтот. Вкупно има околу 100 задачи кои се групирани во 6 chapters. Секој chapter се состои од sections. Во секоја секција има околу 3-4 задачи. Убавата и интересната работа е тоа што задачите мора да се решаваат по ред. Не може да се решава задача од некоја повисока секција додека не се решат сите претходни задачи. Во почетокот задачите се лесни, а како се напредува задачите се се потешки. Покрај задачите има и посебни лекции наречени TEXTS. Во секој TEXT е обработена некоја одредена тема од областа на програмирањето и алгоритмите. Сите основни принципи на програмирање и најбитни и најосновни алгоритми се обработени во овој тренинг. Овој тренинг пред се е наменет за средношколци кои се спремаат за натпреварите по информатика, овде пред се мислам на IOI (International Olympiad in Informatics).

На овој тренинг сајт почнав да решавам кон крајот на четврта година средно (пред 2 години) кога се спремав за IOI 2007. Поради обврски кон факултетот пред се, решавав на сајтот со повремени прекини, па така дури денес можам да кажам дека ги решив сите задачи :) Сите задачи се предизвикувачки, но сепак најинтересни ми беа последните три од chapter 6. При решавање се вежба логиката и размислувањето. Некои задачи некогаш и би рекол дека се невозможни на почетокот но кога навистина добро ќе се размисли - за се има решение, само треба да се најде. Начин на решавање на задачите, прво добро да се прочита и да се сфати што е проблемот. Потоа анализа, разгледување на примери, размислување како да се тргне кон решавање. Разгледување на разни начини. Треба да се одбере најлогичниот начин кој претходно треба да е добро анализиран, прво умствено да се изврши па потоа тоа да се преточи во програмски код. Доколку некоја од овие фази се обидете да ја прескокнете или да ја поминете набрзина без добро размислување тоа најчесто се одразува на време и на нерви :) Кога ќе напишете неколку стотина линии код, гледате дека се грешка, па потоа пак од почеток - секако никој не го сака ова. Во кој програмски јазик ќе се програмира мислам дека е најмал проблем иако ова не е баш работа која може да се занемари. Предноста е кај оние кои знаат повеќе програмски јазици бидејќи ги знаат предностите и недостатоците на секој па во дадена ситуација ќе знаат да го искористат најдобриот избор. Во почетокот, кога почнав да навлегувам во водите на програмирањето кодирав во Pascal, тогаш за мене Pascal беше програмски јазик со кој можев буквално се да искодирам :) толку бев уверен и во себе и во моќта на Pascal. Потоа научив C, овој програмски јазик би го споредил во брзината и перформансите со брза спортска кола, но недостатокот е во тешкото управување со воланот :) За попрости проблеми лесно е да се пишува код во C, но кога ќе наидете на посложени проблеми кои бараат користење на посложени структури и кои имаат потреба од готови библиотеки доаѓа потреба од друг програмски јазик кој ќе ги надмине недостатоците на C, а сепак ќе ја задржи брзината. Погодувате, тоа е C++. Немам баш многу искуство во C++ bидејќи брзо мигрирав од C во Java, но тоа е јазикот кој ми беше алтернатива при решавањето доколку наидев на проблем кој го надминува временскиот лимит во Java. Иста програма напишана во Java и C++ не дава иста брзина на извршување. C++ e далеку побрз. Но сепак Java ми е омилен програмски јазик за програмирање пред се заради неговата едноставност и моќ. Во Java може да се напише буквално се и тоа процесот на кодирање е многу побрз затоа што нуди подршка од многу корисни библиотеки и добри IDE како Eclipse


It's time for a new challenge :)

Алгоритми. Вовед.

Многу луѓе кои се занимаваат со информатичка технологија малку знаат за тоа што се алгоритми. Напишав еден мал вовед во тоа што се алгоритми. Сите оние што се ентузијасти во полето на информатичката технологија е неопходно да имаат барем општи познавања од алгоритмите. Тоа е еден посебен свет на размислување, техники за решавање на проблеми, употреба на логика за да се стигне до резултат. Многу од помладите се скриени таленти за решавање на алгоритамски проблеми, но за жал, малку нашето образование посветува на тој дел од информатиката кој сепак е најбитен.

Ги земам за пример земјите од соседството. Хрватаска е одличен пример за тоа како треба да се едуцираат млади кадри и пример за тоа како државата се грижи за своите таленти, Бугарија редовно е меѓу првите 10 земји во свет, Романија отсекогаш ги имала едни од најдобрите програмери (зборувам во светски рамки). Наскоро планирам да напишам и за тоа кои земји колку имаат постигнато во полето на програмирањето. Во ова што го напишав и што го поставив овде се вклучени и мои размислувања. Некои од податоците се земени од Интернет (wikipedia).

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

Algoritmi.pdf

Транспортни мрежи (Network Flow)

Транспортна мрежа е ориентиран граф, без циклуси во кој на секое ребро (i, j) му е придружен реален број аij>=0 што се нарекува пропусна способност на реброто, и за кој важи

• постои едно и само едно теме s, за кое важи дека нема ребра што влегуваат во тоа теме, кое се нарекува влезно теме или влез на мрежата
• постои едно и само едно теме t за кое важи дека нема ребра кои што излегуваат од тоа теме, кое се нарекува излезно теме или излез од мрежата

Протокот низ секое ребро не е поголем од неговата пропусна способност.
За секое теме освен влезното и излезното важи дека вкупниот проток што влегува во темето е еднаков со вкупниот проток што излегува од темето

Алгоритмот за наоѓање максимален проток од влезот (s) до излезот (t) е следен:

Алгоритмот ја започнува работата со произволен проток, што може да биде и нулти поток (се ставаат сите моментални проводности на нула). Потоа, протокот постојано се зголемува со систематска проверка на сите аугментални патеки од s кон t. Барањето на овие аугментални патеки се прави со помош на доделување ознаки на темињата кои кажуваат во правец на кои ребра и за колку потокот може да биде зголемен. Така, потокот се зголемува за максимално можна вредност и потоа повторно се ажурираат ознаките на темињата. Постапката се повторува се додека има аугментални патеки од s кон t.

Овој алгоритам е познат како алгоритам на Форд-Фалкерсон и доколку потокот секогаш го зголемуваме по најкусата аугментална патека, максималниот поток се добива за помалку од |V|*|E|/2 итерации каде што со V го означуваме бројот на темиња, а со E бројот на ребра во графот.

Имплементацијата во Java е следна:

 static int M;        // M is the number of vertices
 static long c[][] = new long[50][50];
 static long f[][] = new long[50][50];  // the flow
 
 static boolean busy[] = new boolean[50];
 static long ver[] = new long[50];
 static int who[] = new int[50];
 
 static void updateNeighbours(int mom) {
  int i;
  long newver;
  
  for (i=1;i<=M;i++) {
   if (busy[i] == false) {
    newver = Math.min(ver[mom], c[mom][i]-f[mom][i]);
    
    if (newver > ver[i]) {
     ver[i] = newver;
     who[i] = mom;
    }
   }
  }
 }
 
 static boolean findPath() {
  // we set all the vertices as unvisited
  int i;
  int bestv;
  long bestscore;
  long dec;
  
  for (i=1;i<=M;i++) {
   busy[i] = false;
   ver[i] = 0;
  }
  
  busy[1] = true;
  ver[1] = Integer.MAX_VALUE;
  who[1] = 0;
  updateNeighbours(1);
  
  while (busy[M] == false) {
   // we find the best vertex found so far
   bestv = 0;
   bestscore = 0;
   
   for (i=1;i<=M;i++) {
    if (busy[i] == false) {
     if (ver[i] > bestscore) {
      bestscore = ver[i];
      bestv = i;
     }
    }
   }
   
   if (bestv == 0) {
    // this means that a path has not been found
    return false;
   }
   
   busy[bestv] = true;
   updateNeighbours(bestv);
   
  }
  
  dec = ver[M];
  i = M;
  while (i!=1) {
   // we work with the segment from i to who[i]
   f[who[i]][i]+=dec;
   f[i][who[i]]=-f[who[i]][i];
   i=who[i];
  }
  
  return true;
 }
 
 static void networkFlow() {
  while (findPath() == true) {
   
  }
 }

M е бројот на темиња.
c[i][j] е пропусната способност на реброто од i до j.
f[i][j] е моменталната проводност по патот од i до j.

Пред да се повика функцијата networkFlow() треба да се иницијализираат пропусните способности на сите ребра. Доколку нема пат од едно теме i до друго теме j тогаш c[i][j]=0. Доколку графот е насочен, т.е. може да се оди само од i до j тогаш само c[i][j] > 0, а c[j][i] = 0. Доколку може да се оди во двете насоки тогаш c[i][j] == c[j][i] > 0. Треба да се напомене дека при повикувањето на networkFlow(), сите елементи f[i][j] треба да бидат иницијализирани на нула.
busy[], ver[] и who[] се низи кои се потребни за работа на алгоритмот на Дијкстра (правилниот изговор е Диџкстра, но јас го викам Дијкстра :) со кој го наоѓаме патот од изворот до излезното теме.

Овој алгоритам може да се примени и за други проблеми, како што е bipartite matching problem. Проблемот може да се дефинира вака.
Дадени ни се група на машки и група на женски и дадено ни е кој со кој си одговара :)
Да се одреди максималниот број на парови што можат да бидат направени така што да си одговараат машкото и женското од секој пар :)




Како може да го решиме проблемот со помош на тоа што веќе го знаеме за транспортните мрежи? Земаме две темиња кои ќе бидат влезно и излезно теме. Сите темиња од групата машки ги поврзуваме со изворот, а сите темиња од групата женски ги поврзуваме со излезното теме. Ги поврзуваме само оние машки и женски кои си одговараат. Сите врски се со тежина 1, т.е. доколку темињата i и j се поврзани, тогаш c[i][j] = 1.

Објаснувањето зошто треба вака да се реши проблемот го оставам на вас :)

Алгоритмот за решавање на овој проблем на транспортни мрежи многу често се применува во задачи. Многу убаво објаснување за овој алгоритам и за многу други, заедно со задачи со нивна примена може да се најдат на сајтот на USACO. Во скоро време ќе напишам и повеќе околу овој сајт и тоа што тој го нуди за едукација.

Користена литература:
USACO
Introduction to Algorithms - Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Algorithms in C - Robert Sedgewick