Транспортни мрежи (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

CodeFu, 2008 Seasonal competition!

Во недела 7 декември, во 12 часот ќе се одржи Codefu натпреварот во програмирање. Сигурно повеќето од вас имаат слушнато за овој натпревар кој иако има традиција само две години издигна стандарди за тоа како треба да се организираат натпревари кај нас, а уште поважно, на индиректен начин создаде нови програмери, како што имам кажано, за мене програмер е човек кој што знае да решава проблеми и да размислува "алгоритамски", без навреда кон сите останати. Исто така на тие малкуте квалитетни програмери им го издигна нивото. На овој натпревар задачите се решаваат во Java. Задaчите се алгоритамски и логички и поделени се на тежини.

Мој совет до сите што знаат да програмираат во Java (не треба којзнае колку да си специјалист во Java) но и до тие што не знаат Java , а знаат Pascal, C или C++, да се пријават. Ништо не можат да изгубат туку само да добијат. Java се учи брзо. Од лично искуство кажувам дека да се совлада само тој дел од Java кој ќе ви овозможи да решавате задачи не е многу тешко. Лани специјално за Codefu натпреварот почнав да учам Java и буквално во една вечер ги научив основите на Java. Следниот ден веќе решавав задачи од Codefu. Уште една добра работа. Кога ќе се регистрирате имате пристап до задачите од претходните години. Има околу 50 задачи од различна тежина кои можете да ги решавате и да проверите дали ви се точни или не. Слободно можете да го тестирате системот.

Натпреварот ќе трае 2 часа и ќе се одвива преку Интернет. 5 задачи за 2 часа... малку звучи застрашувачки :) Наградите се примамливи iPod за победникот и уште еден за некој по случаен озбор од оние што имат над нула поени ;) Еве уште една мотивација да учествувате. Што помасовен натпревар значи поголем квалитет на кој ќе се издигнеме сите ние. Секоја чест на организаторите кои ги овозможуваат овие натпревари.

Учествувајте, нема да зажалите!

Прости броеви

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

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

int i,j;
int N = 100;

boolean isprime[] = new boolean[N+1];

for (i=2;i<=N;i++) {
  isprime[i]=true;
}

for (i=2;i<=N;i++) {
  if (isprime[i]==true) {
      for (j=2*i;j<=N;j+=i) {
          isprime[j]=false;
      }
  }
}

Вториот алгоритам генерира низа во која се чуваат простите проеви.

int i,j;
int prime[] = new int[1000];
int numofprimes=1;
boolean pom;
prime[0]=2;

for (i=3;i<1000;i++) {
   // we check if i is a prime number
   pom=true;
   for (j=0;j<numofprimes;j++) {
       if (prime[j]<=Math.sqrt((double)i)) {
           if (i%prime[j]==0) {
               pom=false;
               break;
           }
       } else {
           break;
       }   
   }
   if (pom==true) {
       prime[numofprimes]=i;
       numofprimes++;
   }
}

Пресметување на комбинации

In combinatorial mathematics, a combination is an un-ordered collection of distinct elements, usually of a prescribed size and taken from a given set.

Овде ќе зборувам за алгоритам за пресметување на комбинации. Според основната дефиниција може да се направи една функција, но како што може да се забележи е многу неефикасна во смисла на тоа што n! тешко може да се смести во променлива, поради големината. На пример 15! = 1,307,674,368,000. Ова не го собира во long, а да не зборуваме за int. Ова не е единствениот недостаток на овој алгоритам, има премногу пресметки па дури и да го поправиме овој алгоритам. Има уште една работа освен комплексноста за која нема да зборувам овде. Еднаш при решавање на задача, го решив најголемиот дел на задачата, и кога дојде она "најлесното", пресметување на комбинациите го оптимизирав овој алгоритам и цело време ми паѓаше на време, се додека не ми текна на нешто што го знаев од часовите по математика. Потоа направив брз алгоритам, но ми беше криво што порано не сум се сетил на тоа :) Но од грешките се учи, па тоа ми беше една добра лекција, доколку некој алгоритам е точен, но паѓа на време, размисли дали проблемот може да се реши со друг алгоритам.

Решението на нашиот проблем лежи во Паскаловиот триаголник. Колку просто :)



Нема да објаснувам многу за ова, повеќе можете да прочитате на wikipedia.

Еве една инплементација на пресметување на комбинации со помош на Паскалов триаголник.

long N=20;
int i,j;
long comb[][] = new long[N][N];

for (j=0;j<N;j++) {
  comb[0][j]=1;
  comb[j][j]=1;
  for (i=1;i<j;i++) {
       comb[i][j]=comb[i-1][j-1]+comb[i][j-1];
  }
}

Како што се гледа, комплексноста на алгоритмот е O(N), а кога ни се пресметани "претходните" комбинации, пресметувањето на една комбинација е во константно време O(1). За да пресметаме N "последователни" комбинации ни треба O(N). Нема да навлегувам во понатамошни анализи :)

Теорија на веројатност

Една од математичките дисциплини кои често се предмет на проучување од страна на програмерите е Теоријата на веројатност. Една од примените е кај проблемите од типот, колкави ми се шансите да фатам на лото :)

Во математиката, веројатноста да се случи еден настан А се претставува како реален број во опсегот од 0 до 1 и се запишува како P(A). Невозможен настан има веројатност 0, и сигурен настан име веројатност 1.

Спротивно или комплемент на настанот A е настанот [not A] (ова е, настанот A не се случил). Неговата веројатност се означува со P(not A) = 1 - P(A)> На пример, шансата да не ти се падне шестка при фрлање на коцка е 1 - (шансата да ти се падне шест) = 1 - (1/6) = (5/6).



Ако двата настани А и B се случат во исто време додека се врши експериментот, ова се нарекува "joint probability" на A и B.
Ако двата настани А и В се независни, тогаш "joint probability" е:

P(A and B) = P(A) * P(B)

пример: ако две монети се фрлени, шансата да се погоди "глава" и кај двете е (1/2) * (1/2) = (1/4).



Ако се случи настанот А или настанот В, или пак се случат и двата настани истовремено, ова се нарекува унија на настаните А и В.
Ако настаните А и В не можат да се случат истовремено т.е. тие се зависни, тогаш веројатноста да се случи еден од нив е:

P(A or B) = P(A) + P(B)

пример: шансата да ти се погоди 1 или 2 при фрлање на коцка е P(1 or 2) = P(1) + P(2) = (1/6 + (1/6) = (1/3)

Ако настаните А и В не се зависни еден од друг тогаш:

P(A or B) = P(A) + P(B) - P(A and B).

На пример, при извлекувањето на една карта по случајност од еден шпил од карти, шансата да добијам "срце" или карта во боја (J, Q, K) (или една што е и во срце и е карта во боја) е (13/52) + (12/52) - (3/52) = (22/26), затоа што од 52 карти, 13 се во "срце", 12 се карти во боја, и 3 се и двете: овде веројатноста вклучена во "3 што се и двете" се вклучени во секоја од "13 срца" и "12 карти во боја", но треба да бидат избројани само еднаш.



Условна веројатност е веројатноста да се случи некој настан А, при дадена веројатноста на друг настан B. Симболот погоре се чита "веројатност на А, при дадено В". Се дефинира како:

P(A | B) = P(A and B) / P(B)

На пример. Земаме два настани А и В. Две фрлања на коцки А и В.

A: Првата коцка паѓа на 3.
В: Вкупната сума на погодени броеви по фрлањето на втората коцка е 8.

Да претпоставиме дека ги фрламе двете коцки истовремено и ја покриваме втората коцка, па само ја гледаме коцката 1; и забележуваме дека коцката 1 паднала на 3. При дадена половична информација, веројатноста дека збирот на двете коцки ќе даде 8 не е 5/36 (2+6; 3+5, 4+4, 5+4, 6+3 од сите можни збирови на двете коцки кои се 6*6 на број) туку е 1/6, затоа што втората коцка мора да падне точно на 5 за да се постигне бараниот резултат.

Повеќе информации и примери за условна веројатност.

Најмал заеднички содржател

Евклидов алгоритам за најголем заеднички делител и најмал заеднички содржател. Може да послужи некогаш за натпревари по програмирање, па го постирам овде за да имам брз пристап до него и да го користам copy paste.

int nzd(int a, int b) {
   return ( b != 0 ? nzd(b, a % b) : a );
}

int nzs(int a, int b) {
   return (a*b)/nzd(a,b);
}

Ојлеров циклус

Да се одреди дали еден граф има Ојлеров пат или циклус е лесно, се применуваат две правила.

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

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

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

• Ако темето нема соседи, тогаш го додаваме темето на циклусот и се враќаме
• Ако темето има соседи, тогаш правиме листа на сите соседи и нив ги обработуваме (што вклучува нивно бришење од листата на темиња на кои треба да работиме) додека темето нема повеќе соседи
• За да процесираме теме, го бришеме реброто помеѓу моменталното теме и неговиот сосед, вршиме рекурзија на соседот, и го додаваме моменталното теме на циклусот

Овој алгоритам работи во O(m + n) време, каде m е бројот на ребра и n е бројот на темиња, ако се чува графот во "листа на соседи".

Литература: USACO

Google Code Jam

Google Code Jam е алгоритамско натпреварување на кое може да учествува секој. Има примамливи награди, а и натпреварот е одлично организиран (претпоставувам бидејќи го организира Google, но до сега не сум учествувал). Значи на 16 јули ќе има квалификациска рунда каде што ќе се одберат најдобрите 500 кои ќе одат понатаму.

Квалификациската рунда ќе трае 24 часа. Во правилата пишува дека ќе има од 4-6 задачи. Оние што ги дадоа за practice рундата ми се интересни, не се баш многу тешки, но за добар успех сепак треба рутина во кодирање.

Им го препорачувам овој натпревар на сите кои што се разбираат од програмирање, и за почетници се разбира. Нема ништо да изгубат, туку само ќе добијат. Јас можеби ќе учествувам, но имам еден технички проблем кој се обидувам да го решам. Таму треба да се работи со датотеки и се чита влез од фајл, и излезот се испраќа до главниот сервер. Е сега не можам да се одлучам во кој програмски јазик да програмирам. Од кога научив Java пред 2-3 месеци заради codefu натпреварот тој ми стана омилен јазик за програмирање, само проблем е што не знам како да работам со датотеки. Втор омилен јазик ми е C++, го знам прилично добро овој јазик, но имам еден проблем кога читам од датотеки. Се надевам во брзо време ќе го решам ова. C го знам и може да ми послужи, но сепак ми е "понапорен" од C++. За Pascal нема ни да зборувам, него го баталив со завршувањето на Светската Олимпијада по Информатика. Значи ако го решам овој технички проблем со читање и запишување во датотеки учествувам на Google Code Jam. Да си ја пробам среќата.

Здраво

Здраво на сите што случајно или намерно ќе налетаат на мојот блог.

Името на блогот е малку долго ама ми се допаѓа, интересно е. Инаку ќе пишувам на македонски и на англиски. Прво отворив блог на wordpress ама ме изнервира тоа што плугини не се дозволени од "безбедносни причини". Сега за сега мислам дека blogspot ќе ми овозможи најдобар простор за искажување на тоа што сакам да го искажам.

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

Кој сум јас? Јас сум Игор Кулев, студент на ФЕИТ (или како си го викаме електро) прва година, всушност сега завршив прва. Имам искуство во натпревари по информатика и ме интересира компјутерската наука, логиката и вештачката интелигенција најмногу.