1. Основни понятия. Варианти на алгоритми. Влияние върху производителността. Въведение в анализа Алгоритъм



страница4/5
Дата31.12.2017
Размер0.81 Mb.
1   2   3   4   5

Off-line алгоритми
Сега можем да аналзираме цялата поредица, преди да подреждаме. Големият проблем на on-line алгоритмите е че не пакетират добре големи ел. когато те идват към края. Добре би било големите да ги сортираме отпред.
Това е алгоритъмът first fit decreasing:

В случая това е и оптимал.решение. Не винаги е така. Значи считаме, всички ел. са вече подредени намаляващо.Ще док, че ако оптимал.пакетиране изисква М торби, сега са нужни не-повече от (4М + 1)/3



Лема 1 Нека N ел. (сортирани намаляващо) с размери s1…sN могат да се подрдят оптимално в М торби.Тогава всички ел., които first fit decreasing поставя в допълнителни торби (над М) имат размер най-много 1/3.
Док. Нека елемент i е първия в торба М+1. Да докажем si <=1/3. Предполагаме si >1/3. Следва s1,…si-1 >1/3 (иначе лемата е доказана). Тогава в торби В1….ВМ има най-много ел ( нали са >1/3). Тогава в първите торби има по 1 ел. а в оставащите до М по 2 ел.
Ако приемем обратното: в торба Вx има 2 ел. , а в торба By à 1 el. и 1<= x < y <= M. Нека x1 и x2 са елементите в Вx и y1 е елементът в By, x1>=y1, а също и x2 >=si то: x1 +x2 >= y1 +si
Значи si може да се пъхне в By, но това не беше възможно по предположение. Значи, ако si>1/3, в момента, когато го обработваме, в първите j торби има по 1 ел. а в оставащите M-j по 2 ел.

Сега да покажем че няма начин всички елементи да се сложат в торби (тогава не би оставал външен <1/3)


За първите j ел. няма начин 2 да се сложат в 1 торба (доказахме че в началото са по 1). Също така никой елемент до si не може да се пъхне в първите торби. Значи j торби са по 1 ел. и елементите с размери
sj+1,s j+2…. S i-1 са в М-j торби.Общият брой ел. в тях е 2(М – j)
Следователно, елемент si>1/3 няма начин да се вкара в първите М торби: той не може да се вкара в първите j торби, защото те съдържат по 1 ел. Не може и в оставащите M-j торби, защото в тях трябва да се появят 2(M-j) +1 елемента. Това означава в някоя торба следва да има по 3 ел (а всеки беше >1/3).Очевидно предвиж-дането в нач. беше грешно и s i <=1/3

Лема 2 Броят ел. поставени в допълнителните торби е най-много М-1
Док:
Приемаме обратното: в допълнителните торби има най-малко М ел. Знаем si <= M Нека Bj е поела общо тегло Wj (1<= j <= M) Нека първите М ел. в допълнителни торби са с размер x1…xM.
Тъй като елементите в първите М торби + елементите в първите М допълнителни са част от всички то:

Това е невъзможно, тъй като тези N ел. са пакетирани в М торби. Следователно допълнителните торби са най-много М-1



Теорема Нека М е оптимал. брой торби за I елемента. First Fit decreasing никога не използва повече от (4М+1)/3 торби.
Имаме М-1 допъл.ел.с макс.размер 1/3.
Значи допълн. торби са най-много (М-1)/3.
Общият бр. торби използвани в метода е :
(4М –1) /3 <= (4М +1)3
First Fit decreasing е добър и бърз подход

33.Разделяй и владей – алг. Анализ на времето на изпълнение

Анализ на времето на изпълнение:

= време за изпълнение на частите + константно време на излъчване крайния резултат: T(N)= 2T(N/2) +O(N).

Теорема:Реш.на уравн.T(N)=аT(N/b)+O(Nk)

а>=1; b >1 (а – броят на зад.; в – частите) е:













Това са и 3 случая на рекурентно разбиване на задача на подзад. Напр. сортировка чрез разделяне и сливане : a=b=2; k=1. Имаме втория случай и отговор: O(NlogN)


Ако имаме 3 проблема и всеки е над половината данни и комбинирането за краен резултат изисква O(N) време, то a=3,b=2, k=1. log 2 3 1.59
Имаме случай 1 и O(N )= O(N ) Ако в горния пример времето за обединяване на резултата беше O(N ² ),то сме във случай 3 и: O(N²)

34.Прoблемът“на-близкостоящи точки”
Имаме Р точки в равнината, p1=(x1,y1)…..
Разстоянието м/ду тях :[(x1 –x2)² + (y1-y2)² ] Търсим най-близкостоящите точки.
Имаме N(N-1)/2 разстояния. Пълен тест: O(N ² ) Друг подход: Нека точките са сортирани по x координатата си. Ако не са, допълнително време O(NlogN):

Разделяме ги по вертикала на 2 равни части P L P R:



dl и dr могат дасе изчислят рекурсивно ( O(NlogN) . Остава да изчислим dc за O(N) време и да постигнем: O(NlogN) +O(N) Нека δ=min(dl,dr). Ще изчисляваме dc само ако подобрява б. Точките в лентата са малко: една по една ( O(N) ):


//points are all in the strip
for(I=0;I< numPoinsInStrip; I++)
for (j=I+1; jif(dist(pi,pj) <б) б = dist(pi,pj);
ако точките в лентата са много (почти всички), горния подход е слаб. Нека т. са сортирани в лентата по у коорд. Тогава ако у коорд на pi и pj се различават с повече от б, можем да преминем към p i+1.

Ускорен вариант:


for(I=0; I for( j=I+1; j< numPointsInStrip; j++)
if (pi and pj ’coordinates differ by more

than б) break; // next pi.


else
if(dist(pi,pj)<б) б = dist(pi,pj);
само p4 и p5 се разглеждат, съобразно горната модификация:

най-много 7 т. могат да се разглеждат в правоъгълната област б *2б:



Времето за това < O(N).


Имаме О(NlogN) от рекурсивните повиквания отляво и отдясно + O(N).
За сортирането по у е нужно още O(NlogN) за всяко рекурсивно повикване или общо O(Nlog ² N). (пълно претърсване: O(N ² ).
Mожем още да ускорим като предварително сортираме и по x и по у и изработим 2 списъка с точки, сортирани съответно. ( O(NlogN) време в началото ). После претърсваме списъка по x и махаме всички точки с коорд. > б. Автоматично остават само тези в линията и то сортирани по у. Това изисква O(N). общо време O(NlogN) +O(N)

35.Теорет. подобрения с аритмет. задачи

* Умножение на цели числа


- За малки ч-ла - линейно време.
- За големи, времето става квадратично.
Нека имаме N р-дни ч-ла X и Y. Знакът определяме лесно. По класически алгоритъм O(N ² ) : всяка цифра на X се умножава по всяка на Y.

Имаме 4 умножения с N/2 цифри:

T(N)= 4T(N/2) + O(N)
според теоремата в началото това е:O(N²) - нямаме подобр.Трд намал броя умнож:

Xl Yr+Xr Yl=(Xl–Xr)(Yr–Yl)+Xl Yl+Xr Yr

Умножение на матрици

Ето стандартен алгоритъм с O(N ³) време.
Matrix operator*( const matrix &a, const matrix &b )
{int n = a.numrows();
matrix c( n, n);
int I; for( I = 0; I < n; i++ )
for( int j = 0; j < n; j++ )
c[ I ][ j ] = 0;
for( I = 0; I < n; i++ )
for( int j = 0; j < n; j++ )
for( int k = 0; k < n; k++ )
c[ I ][ j ] += a[ I ] [ j ] * b[ I ] [ j ];
return c;
}

Strassen подобрява това време. Осн. идея е разбиване на матриците на 4 квадранта:



Ако матр.умнож.се изпълн.в рекурсия:


T(N) = 8T(N/2) +O(N² ) = O(N3 ) =>няма подобрение.Трд се намал.подзад. <8.

Strassen дава divide &conquer алг. с из-ползване на 7рекурсивни повиквания :

M1= (A12-A22)(B21+B22)
M2= (A11+A22)(B11+B22)
M3= (A11-A21)(B11+B12)
M4= (A11+A12)B22
M5= A11(B12-B22)
M6= A22(B21-B11)
M7= A21+A22)B11

Резултатът се получава така:

C11= M1+M2-M4+M6
C12= M4+M5
C21= M6+M7
C22= M2-M3+M5-M7
T(N)=7T(N/2)+O(N)=O( Nlog²7 )=O( N ².81 )

36.Динамично програмиране – табл. вместо рекурсия

Рекурсията не е оптималната техника àв ред случаи рек. алгоритъм следва а се пренапише в нерекусивен вариан със запомняне межд. резултати в таблица.


Една техника за това е “динамичното програмиране”.

3.1 таблици вместо рекурсия. Ето неефективен вариант за изчисляване ч-лата на Фибоначи:


int fib( in n)
{
if( n <= 1 ) return 1;
else return fib( n – 1 ) + fib( n – 2 ); }
T(N) >= T(N-1) +T(N-2)
сложностa e експоненциална. Мд съхраним изчислените вече F n-1; F n-2. :
int fibonacci( int n )
{
if( n <= 1 )
return 1;
int last = 1;
int nextTolast = 1;
int answer = 1;
for( int I = 2; i <= n; i++ )
{ answer = last + nextTo last;
nextTolast = last;
last = answer;
}return answer;}

Имаме O(N). Ако горната модификация не е направена, за изчисление на Fn се вика рекурсивно Fn-1 и Fn-2…..





38. Динамично програмиране. Оптимално бинарно търсене в дърво
Рекурсията не е оптималната техника àв ред случаи рек. алгоритъм следва а се пренапише в нерекусивен вариан със запомняне межд. резултати в таблица. Една техника за това е “динамич.програмиране”.

oптимално бинарно търсене в дърво

Имаме списък думи w1……wn с вероятности на появяване: p1…..pn


Искаме да подредим думите в бинарно дъво, така че общото време за намиране на дума да min. В бинарно д-во за да стигнем до ел. с дълбочина d, правим d+1 сравнения. Така че, ако wi е на дълбочина di, ние искаме да минимизираме









първото използва greedy стратегия. Най-вероятната дума е най-горе. Второто е балансирано search tree (в дясно с по-ниско pi).Третото е оптималното – виж табл





сравнение на 3 дървета с бинарно търсене

При optimal binary search tree данните не са само в листата (Hofman) и следва да удов-летворяваме критерий за binary search tree.


Поставяме сортирани според някакъв критерий думи wleft, wleft+1,….wright-1, wright в бинарно дърво. Нека сме постигнали оптималното бинарно дърво в което имаме корен wi и поддървета за които : Left <= i <- Right. Тогава лявото поддърво съдържа елементите wleft, …w i-1, а дясното – wi+1,……wright ( критерий за binary search tree ).
Поддърветата също правим оптимал. Тога-ва можем да напишем формулата за цената Cleft,right на оптимално binary search tree. Лявото поддърво има цена Cleft,I-1, дясното – Ci+1,right спрямо корена си.

На основата на тази формула се гради алг. за цена на оптималното дърво.Търсим i, така че да се минимизира C Left,Right.

Последователно се поставят за корени am, and, egg, if и се изчислява цена и оттам минималната цена. Например, когато and е корен, лявото поддърво am…am има цена 0,18 (вече определена), дясното – egg-if с цена 0.35 и pam+pand+pegg+pif = 0.68.
Тогава общата цена е 1,21.Времето е O(N ³) защото имаме тройно вложен цикъл

40. Алг. с backtracking: реконструиране
Достига до добри решения , но е непредвидимо бавен, поради връщанията. Пример: подреждане на мебели в къща. спира се на различни етапи и се кара до изчерпване. Проблемът – реконструиране (приложение Физика, мол. Биология..)
Нека имам N точки: p1,p2…pN подредени по оста x.
Дадени разстоянията N(N – 1) / 2. Нека x1 = 0
Ако имахме дадени координатите, лесно можем да изчислим разстоянията. O(N² )
Нека дистанциите с дадени сортирано.
Задачата е: да се реконструират координатите на точките от дистанциите.

дадени: D ={1,2,2,2,3,3,3,4,5,5,5,6,7,8,10}


D e 15, à N=6 нека x1 = 0 очевидно x6 = 10

най-голямата оставаща дист. е 8, следоват или x2=2 или x5=8 откъдето и да тръгнем все ще стигнем (връщанията от неуспех са равновероятни).



Нека x5=8. тогава x6-x5=2; x5-x1 = 8

7 е най-голямото разст. Или x4=7 или x2=3 (за да има разст. = 7 от x2 до x6).


Ако x4 = 7 – проверяваме разст. до x6 и x5 и виждаме че ги има във вектора с разст.
Ако решим x2=3, то 3-x1=3; x5-3=5 - също са във вектора. Значи и това става.

Избираме едното за да продълж. Нека x4=7



Сега макс. разст. е 6, така че или x3=6 или x2=4. Проверяваме x3=6 - не може. Проверяваме x2=4 – не може.Връщане назад.x4=7 отпадна. Сега опитваме x2=3



сега остава да изберем или x4=6 или x3=4. x3=4 е невъзможно. Значи остава x4=6:



остана x3=5, x1 = 0, x2 = 3, x3 = 5 x4 = 6 x5 = 8 x6 = 10 D = {}край!

ето граф на решенията:

*избраното решение води до разст. ,които липсват в D.


** върхът има само неуспяващи деца, следоват. този път да се изостави.
Поради backtracking анализът е вероятностен от… до... Ако няма връщане O(N ²logN),ако има – достигаме до O (N ²),

41. Алгоритми с backtracking: Игри
1.изчерпателен анализ на ходовете
2. стратегии: шах, крави /бикове крави/бикове е лесна за програмиране, защото броят е изчерпаем, известни са слабите ходове (могат да се вкарат в табл). Алг.никога не греши (никога не губи) и ви-наги ще спечели ако му се даде възмож.
Стратегия минимакс
разглеждаме “силата” на позициите: Ако води победа – оценката е +1, ако равенство – 0; ако е позиция с която компютърът губи –1. Такива позиции са терминални.
За останалите à рекурсивно се играе.
Значи стратегияте е:противникът се стреми да минимизира стойността, играчът (комп) – да я максимизира. Пробват се всички възмож.в момента ходове.Избира се този с макс.ст-ст. За ход на противника – същото: прохождат се всички ходове и се избира този с минимална стойност.

Int TicTakToe::

findCompMove( int & bestMove)

{int i, responseValue;


int dc// don’t care:ст-стта не се използ
int value;
if( fullBoard () )value = DRAW;
else
if(immediateCompWin(bestMove))//има return COMP_WIN //възм. за редица
else
{value = COMP_LOSS; bestMove = 1;
for( i = 1; i < 9; i++ )
{ if( isEmpty( i ))
{ place( i, COMP );
responseValue=findHumanMove(dc);
unplace( i );
if( responseValue > value )//търси^

{ //update best move


value = responseValue;
bestMove = i;

}

}



}

} return value; }

играта на човека(ф-иите рекурсивно се ви-кат,оценките за успеш.ход са противопол.
int TicTacToe::

findHumanMove( int & bestMove)


{int i, responseValue;
int value; int dc //don’t care
if( fullBoard()) value = DRAW;
else if( immediateHumanWin( bestMove) )
return COMP_LOSS;
else
{value = COMP_WIN; bestMove = 1;

for( i = 1; i <= 9; i++ ) //изпробва

// всяко квадратче
{if(isEmpty( i ))

{place(i,HUMAN);


responseValue=findCompMove( dc );
unplace( i ); //restore board

if(responseValue
{// update best move
value = responseValue;
bestMove = i;

}}

}} return value;}

Най- много изчисления са нужни когато комп.започва играта(много възм.за провер-ка) Тъй като в момента се счита равенство, избира се позиция 1 (горе,ляво,макар че то-ва е условно).Има 97,162 възмож.позиции.


Ако комп.играе втори – поз.са намалели на 5185, ако е бил избран центърът; 9761 – при избор на ъгъл; 13,233 при друг избор.
Очевидно при шах тази стратегия за прохождане ( до терминален ) е непосилна ( > 10 ^ 100 позиции ). Спира се донякъде, вика се ф-ия, оценяваща стигнатата позиция. (напр. проходимост на фигури, качество на фигури и т.н.) .
Тази ф-ия е основната за шах- програма.
Много е важно колко хода напред могат да се прегледат (дълбочината на рекурсията). За да се увеличат:в таблица се пазят вече анализирани ходове. Когато се срещнат , все едно терминален.

α-β окастряне (pruning)(в минимакс стр.)

Ето game tree за някаква игра – виждат се рекурсивните стъпки:


max 44

min 44 36

max 44 78 40 36

min 27 44 68 78 40 27 36 36


42 27 86 44 ………


Ето същото дърво, но орязано. Стойността в корена е същата.. Как?
Max 44

min 44 40

max 44 68 40 D

min 42 27 68 C 40 27


Каквото и да е D, не е важно. Ето събраната до момента информация, която ще служи за изчисляване на D:

max >=44


min 44 <=40

40 D?
α - Окастряне.


Обратният случай:
min <= 44

max 44 >=68

68 C?
β - Окастряне.

Стратегията е лесна за реализация и силна. Колкото по-нагоре в дървото я приложим , толкова ефектът е по-добър.Ограничава търсенето до О(√N) възли,където N е раз-мера на цялото дърво, което позвол.удвоя-ване броя проходени напред ходове.Играта крави/бикове не е подходящ пр.за ползата ( има много идентични като оценка ходове). Въпреки това прилагането й в началния момент свежда от 97162 до 4493 възлите за разглеждане (само нетерминални възли се разглеждат при тази стратегия).



42. Теория на графите.Общи понятия. Предст. на граф. Топологично сортиране

Краен ориентиран граф се нарича наредената двойка G=(V,E), където:

V={v1,v2,…,vn} е крайно множ.от върхове;

E={e1,e2,…,em} е крайно множ.от ориен-тирани ребра. Всеки елемент (k=1,2,…,m) е наредена двойка (vi,vj), , 1≤i,j≤n.

Ако ребрата на графа са неориентирани, графът се нарича неориентиран.

Ако в допълнение е дадена числова функция f:E→R, съпоставяща на всяко ребро ек тегло f(ek), графът се нарича претеглен. Най-често графът се представя графично с множество от точки, изобразяващи върховете му и свързващи стрелки, които са неговите ребра.



Върхът w е съседен на v тогава и само тогава, когато . В неориентиран граф, ако w е съседен на v, то и v е съседен на w.

Път в граф ще наричаме последователността от върхове v1,v2,v3,…,vn, такава че , 1≤i≤n. Дължина на пътя се нарича броя на ребрата в него. Ще допускаме път от върха, до самия него, като ако няма ребра, дължината му е нула. Ако графът съдържа ребро (v,v), пътят v,v се нарича примка. Ще считаме, че графът по подразбиране няма примки.

Прост път се нарича път, в който всички върхове са различни, с изключение на първия и последния.

Цикъл в ориентиран граф е път с минимална дължина 1, за който v1=vn. Такъв цикъл ще наричаме прост, ако пътят е прост. За ориентирани графи ще изискваме ребрата да са различни. Причина за това е, че пътят u,v,w в неориентиран граф няма да се счита за цикъл, защото (u,v) и (v,u) са едно и също ребро. В ориентиран граф това са различни ребра и ще бъде цикъл. Един ориентиран граф е ацикличен, ако няма цикли.

Един неориентиран граф е свързан, ако има път от всеки връх до всеки друг. Ориентиран граф с това свойство се нарича силно свързан. Ако съществува поне един, от двата възможни пътя, между всеки два върха, ориентираният граф е слабо свързан. Пълен граф е този, в който има ребро между всяка двойка върхове.

Предст. на граф мд се осъществи чрез:

Двумерна матрица на съседство: на всяка дъга (u,v) се съпоставя един елемент от матрицата А[u][v] със стойност 1 или теглото на графа, когато е претеглен. Липсата на дъги се означава с 0 или ∞. Ако съществува път (u,v), но не съществува (v,u) може да се запише (-1) за да се посочи ориентацията на дъгите в матрицата. При този начин на работа е необходима Θ(│V2│) памет за съхранение на матрицата. Това води до разхищение на памет, особено при граф с малко дъги. Нещата са по-добре при неориентиран граф, където матрицата е симетрична относно главния диагонал и може да се съхрани като триъгълна: само под главният диагонал. В този случай разхода на памет е



По ефективно представяне за разреден граф е списъка на съседство. При него за всеки връх се създава списък на съседите му. Необходимата памет тук е O(│E│+│V│). Проверката дали съществува път между два върха е по-сложна тук. Пример:



За неориентиран граф, списъкът на съседство включва две явявания на всяка дъга. При това паметта се удвоява.

Представянето облекчава задачата за намиране на съседни върхове. Тя се извършва с просто сканиране, т.е. времето е линейно. По същият начин стои и задачата за търсене на наследници. Проблем възниква при търсене на предшественици: няма връзка в списъка и трябва да се сканират всички списъци. В този случай е по-добре да се използват двусвързани списъци.

Съхраняването може да бъде и в хеш-таблица, защото всеки връх на графа има уникално име и ще бъде ключа в хеша.

Информацията за всеки връх ще съхраняваме в обект от тип Vertex. Тя задължително включва име на върха, което трябва да бъде уникално. Останалите параметри са опционни, в зависимост от алгоритъма, който решаваме. Всеки от представените по-нататък алгоритми е разработен с псевдокод, за да бъде представен по-ясно и да позволи реализация на различен език за програмиране. При това ще считаме, че графът е прочетен и зареден в паметта.

Топологично сортиране

В ацикличен ориентиран граф можем да номериране върховете така, че за всяко ребро (v,w), v да предшества w. Това се нарича топологично сортиране. За един граф може да имаме няколко топологични подредби. Пример за такава подредба може да бъде пътна карта. Топологично сортиране не съществува, ако в графа има цикли, защото за два върха v и w в един цикъл, v предшества w и w предшества v.

Намирането на топологична подредба може да се сведе до построяване на линеен списък Z от върховете на графа, такъв че за , ако , то v предхожда w в Z. Множеството от всички възможни Z е пълно топологично сортиране. Пример:

Void Graph::topsort()

{ Vertex v,w;

For (int counter=0;

counter

{ v=findNewVertexOfDegreeZero();

if (v==NOT_A_VERTEX)

throw CycleFound();

v.topNum=counter;

for each w adjacent to v w.indegree--;

} }

v1,v2,v5,v4,v3,v7,v6, както и v1,v2,v5,v4,v7,v3,v6 са две топологични подредби. Алгоритъмът първо открива връх без входящи ребра. После го премахва заедно със ребрата от него. Тази операция се повтаря докато не се изчерпи списъка с върховете без входящи ребра.



Псевдокодът показва неговата реализация. Функция findNewVertexOfDegreeZero() сканира масива за връх с indegree=0, на който до момента не е присвоено топологично номериране. NOT_A_VERTEX се получава от функцията, ако няма такъв връх, т.е. налице е цикъл. Ф-ята заема O(│V│) време и след като се изпълява в цикъл за всички върхове, сложността ще бъде O(│V2│).

Подобрение на алгоритъма: при рядък граф са малко върховете, чиито indegree ще се променят след всяка итерация. Затова няма смисъл да обхождаме всички. Можем да запазим всички неизползвани в топологичната подредба до момента върхове с indegree=0 в отделен масив. Тогава ф-ята ще работи само с върхове от този масив. При това когато един връх стане с indegree=0 влиза в масива.



Най-добре вместо масив да се ползва стек или опашка. Всички върхове с indegree=0 се поставят в празната, за начало, опашка enqueue. Докато тя не се изпразни, връх се изнася от нея и за свързаните с него се намалява indegree. Връх се вкарва в опашката dequeue, когато indegree=0. Резултатът от прилагане на алгоритъма се вижда в следната таблица:

Връх

Номер итерация

1

2

3

4

5

6

7

V1

0

0

0

0

0

0

0

V2

1

0

0

0

0

0

0

V3

2

1

1

1

0

0

0

V4

3

2

1

0

0

0

0

V5

1

1

0

0

0

0

0

V6

3

3

3

3

2

1

0

V7

2

2

2

1

0

0

0

Enq

1

2

5

4

3

7





V6

Deq

1

2

5

4

3

7

V6

Void Graph::topsort()

{ Queue q(NUM_VERTICES);

Int counter=0;

Vertex v,w;

q.makeEmpty();

for each vertex v

if (v.indegree==0) q.enqueue(v);

while (!q.isEmpty())

{ v=q.dequeue();

v.topNum= ++counter;

for each w adjacent to v

if (--w.indegree==0) q.enqueue(w);

}

if (counter != NUM_VERTICES)



throw CycleFound(); }

Времето за обработка е O(│E│+│V│) при използ. на списъци на съседство,т.е. лин.



43. Намиране на най-къс път. Алгоритъм на Дейкстра

Ще разгледаме алгоритъм за намиране на най-къс път при безтегловен граф. За зада-ден безтегл. граф G=(V,E) и стартов връх v, търсим най-късия път от v до всички оста-нали върхове в G. Нека разгледаме реш. за графа, показан на фиг. 4 Приемаме за стар-тов връх v3. Тогава пътят до v3 е 0. Търсим съседните на v3.Пътят до тях е 1.Избираме един от тях и отново търсим съседи. Пътят вече е 2 и така до изчерпване на всички върхове. Това стратегия на обхождане се нарича обхождане в ширина на графа и се използва при търсене по нива.



За реализацията на алгоритъма ще поддържаме следната таблица:



V

Known

dv

pv

V1

F



0

V2

F



0

V3

F

0

0

V4

F



0

V5

F



0

V6

F



0

V7

F



0

В нея с v1-v7 са означени върховете на графа, Known е флаг, показващ дали върха е посетен (T) или не (F). dv показва разст. от стартовия връх до текущия като ∞ озна-чава, че върхът не е обработен. pv показва предшественика на текущия връх като 0 означава необработен връх. Алг. следва да попълни табл.и да приключи при Known=T за всеки връх. Ст-стта в колоната dv показ-ва дълж. на най-късия път от стартовия връх до текущия. Освен таблицата, ще под-държаме и опашка Q, която в нач.съдържа всички върхове и след като Known=T, вър-хът отпада от нея. Когато опашката стане празна, алг.трд приключи. Ето как изглеж-да постъпковото изпълн. в нашия пример:

V

Начално съст.

V3 отпада

K

dv

pv

K

dv

pv

V1

F



0

F

1

V3

V2

F



0

F



0

V3

F

0

0

T

0

0

V4

F



0

F



0

V5

F



0

F



0

V6

F



0

F

1

V3

V7

F



0

F



0

Q:

V3

V1,v6

V

V1 отпада

V6 отпада

K

dv

pv

K

dv

pv

V1

T

1

V3

T

1

V3

V2

F

2

V1

F

2

V1

V3

T

0

0

T

0

0

V4

F

2

V1

F

2

V1

V5

F



0

F



0

V6

F

1

V3

T

1

V3

V7

F



0

F



0

Q:

V6,v2,v4

v2,v4










V

V2 отпада

V4 отпада

K

dv

pv

K

dv

pv

V1

T

1

V3

T

1

V3

V2

T

2

V1

T

2

V1

V3

T

0

0

T

0

0

V4

F

2

V1

T

2

V1

V5

F

3

V2

F

3

V2

V6

T

1

V3

T

1

V3

V7

F



0

F

3

V4

Q:

V4,v5

V5,v7

V

V5 отпада

V7 отпада

K

dv

pv

K

dv

pv

V1

T

1

V3

T

1

V3

V2

T

2

V1

T

2

V1

V3

T

0

0

T

0

0

V4

T

2

V1

T

2

V1

V5

T

3

V2

T

3

V2

V6

T

1

V3

T

1

V3

V7

F

3

V4

T

3

V4

Q:

V7

Праз. опашка

Void Graph::unweighted(Vertex s)

{ Vertex v,w;

s.dist=0;

for (int currDist=0;

currDist

for each Vertex v

{ if (!v.known && v.dist==currDist)

{ v.known=True;

for each w adjacent to v

if (w.dist == INFINITY)

{ w.dist=currDist+1;

w.path=v;

}

}

}



}

Времето за обработка е O(│V2│), защо са налице два вложени цикъла един в друг. Неефективността е че външният цикъл продължава до NUM_VERTICES-1, дори всички възли вече да са отбелязани с Т в таблицата. Дори и да направим проверка, нещата няма да се подобрят за всички видове графи. Като пример разгледайте графа, показан на фиг.



За подобряване на ефективността, можем да използваме стратегията с два списъка, която приложихме при топологичното сортиране. Във всеки момент има два типа върхове с Known=F и dv≠∞. Единият тип има dv=currDist, а другия - dv=currDist+1. Разполагаме тези два типа в два отделни списъка и работим само с първия от тях. След изчерпване на елем. му, всички елем. от втория списък се прехвърлят в 1-я и алг.се повтаря. Ето примерна реализация:

Void Graph::unweighted (Vertex s)

{ Queue q(NUM_VERTICES);

Vertex v,w;

q.enqueue(s);

s.dist=0;

while (!q.Empty())

{ v = q.dequeue();

v.known=True;

for each w adjacent to v

if (w.dist==INFINITY)

{ w.dist=v.dist+1;

w.path=v;

q.enqueue(w);

}

}



}

Сложността тук е линейна: O(│E│+│V│).



Алгоритъм на Дейкстра

Ще използваме същата идея и при граф с тегла. Отново всеки връх ще маркираме с Known=T, след като е обходен. Отново ще натрупваме разст. в dv и ще съхраняваме предшественика в pv. Тази идея за I път е реализирана от Дейкстра през 40-те год. Този алг.е обобщение на предходния и носи името алгоритъм на Дейкстра. Това е типичен пример за greedy algorithm Пр. за такава задача е какви монети трд се върнат до опр.ст-ст, за да бъде броят им мин. Про-блем на такива алгоритми е, че не винаги работят. Пример за това са връщането на 15 цента в САЩ, което алгоритъма ще даде като 12+3*1, докато оптималното е 10+5.

Алг.на Дейкстра работи на етапи, като за всеки етап избира връх v с мин.дължина dv, измежду всички, неизползвани до мо-мента и декларира най-късия път от s до v за известен.=> актуализация на ст-стите на dw според теглото на реброто (v,w), т.е. dw = dv + cv,w. Тази актуализация се прави само ако новото разст.е по-късо от същест-вуващото. В противен случай разст.не се променя. Ще разгледаме приложението на алг. за графа, показана на фиг. 6. Отново ще използваме табл.,но този път стартов връх ще бъде v1. Нека проследим отделни-те стъпки. Започваме от стартовия връх v1 и нанасяме разстояние 0 (фиг. 7). Маркираме върха за обходен (Known=T). Определяме неговите съседи. Те са v2 и v4. Попълваме табл.за тях (фиг. 8), след което маркираме v4 за обходен. Отново опреде-ляме съседите на v4: v3, v5, v6 и v7. Попъ-лваме табл.за тях (фиг.9).Сега избираме v2. Неговите съседи са v4 и v5. От тях само v5 има Known=F.Тъй като дълж.на пътя 10+2 =12 е по-голяма от съществуващата (3), не се правят промени по таблицата (фиг. 10).

Следващият връх, който ще обработим е v5. Той има само един съсед, който не е обходен: v7. Отново няма да правим про-мени по таблицата, защото новото разсто-яние 3+6=9 е по-голямо от 5 (съществува-щото) (фиг. 11). Следва избор на v3 и коре-кция на разст.на v6, което става 8 (фиг.12). Сега идва ред на v7. Отново се променя разст.на v6,което става 6(фиг.13).Накрая се обхожда v6, който няма съседи и не води до промяна на разст.(фиг.14),и алг.спира





V

Known

dv

pv

V1

F



0

V2

F



0

V3

F

0

0

V4

F



0

V5

F



0

V6

F



0

V7

F



0



V

Known

dv

pv

V1

F

0

0

V2

F



0

V3

F



0

V4

F



0

V5

F



0

V6

F



0

V7

F



0



V

Known

dv

pv

V1

T

0

0

V2

F

2

V1

V3

F



0

V4

F

1

V1

V5

F



0

V6

F



0

V7

F



0



V

Known

dv

pv

V1

T

0

0

V2

F

2

V1

V3

F

3

V4

V4

T

1

V1

V5

F

3

V4

V6

F

9

V4

V7

F

5

V4



V

Known

dv

pv

V1

T

0

0

V2

T

2

V1

V3

F

3

V4

V4

T

1

V1

V5

F

3

V4

V6

F

9

V4

V7

F

5

V4



V

Known

dv

pv

V1

T

0

0

V2

T

2

V1

V3

F

3

V4

V4

T

1

V1

V5

T

3

V4

V6

F

9

V4

V7

F

5

V4




V

Known

dv

pv

V1

T

0

0

V2

T

2

V1

V3

T

3

V4

V4

T

1

V1

V5

T

3

V4

V6

F

8

V3

V7

F

5

V4



V

Known

dv

pv

V1

T

0

0

V2

T

2

V1

V3

T

3

V4

V4

T

1

V1

V5

T

3

V4

V6

F

6

V7

V7

T

5

V4



V

Known

dv

pv

V1

T

0

0

V2

T

2

V1

V3

T

3

V4

V4

T

1

V1

V5

T

3

V4

V6

T

6

V7

V7

T

5

V4

Ето пр.реализация на алг. Структурата Vertex съдържа допълн.информация за dv (означен с dist), pv (означен с path), known и списъка на съседство adj. Първо трябва да създадем табл.(става в createTable), като с помощта на readGraph, зареждаме графа в паметта. printPath печати най-късите пътища от върха v посредством рекурсия. Dijkstra реализира самия алгоритъм

Struct Vertex

{ list adj;

bool known;

distType dist;

Vertex * path; }

void Graph::createTable(vector& t)

{ readGraph(t);

for (int i=0;i

{ t[i].known=False;

t[i].dist=INFINITY;

t[i].path=NOT_A_VERTEX; }

NUM_VERTICES=t.size;

}

void Graph::printGraph(Vertex v)



{ if (v.path!=NOT_A_VERTEX)

{ printfPath(v.path);

cout<<” to “;

}

cout<

}

void Graph::dijkstra(Vertex s)

{ Vertex v,w;

s.dist=0;

for (; ;)

{v=smallest_unknown_distance_vertex();

if (v==NOT_A_VERTEX) break;

v.known=True;

for each w adjacent to v

if (!w.known)

if(v.dist+cvw

{ decrease(w.dist,v.dist+cvw);

w.path=v; }

}

}



Алг.няма да работи при отрицателни тегла.

Времето за обработка зависи от реда на об-хождане на върховете. Времето, за скани-ране на върховете, за определяне на мин. разст.за всеки елемент е O(│V│) и => вре-мето за попълване на табл.е O(│V│2). Вре-мето за актуализация на разст. е константа и е O(│E│).Оттук =>, че общото време е O(│V│2). Ако графът е плътен, то │E│ = O(│V│2) и алг. е оптимален. Ако графът е разреден с │E│ = O(│V│), алг. е бавен. В този случай за повиш. на бързодействието разст.трд се съхранява в приоритетна опа-шка. Използвайки проритетна опашка, вре-мето за намир. на мин.разст.е O(log│V│). Тогава общото време за изпълнение на алг. е O(│E│log│V│+│V│log│V│) = O(│E│log│V│). Същото време ще се полу-чи, ако всеки път добав. в опашката връх w с нова ст-ст за dw. В този сл.,при търсене на мин.разст.трд се проверява дали Known =T и да се изтриват върховете от опашката.

Времето е добро,защото алг. за обхождане на всички възможни пътища, нараства експоненциално на степен N

44. Алг.на Дейкстра при ацикл.графи

Ако знаем че графът е ацикличен можем да подобрим алг.на Дейкстра, като определим еднозначно последователността на избор на връх за обхождане. Това е последова-телността, съотв.на топологичната подред-ба. Алг.базиран на подреден топологично граф, се обработва за един пас. Това се дъ-лжи на факта, че пътят до избран според топологичната подредба връх не може вече да се намали, защото към него няма входя-щи ребра от необходени върхове. По този начин отпада необх.от приоритетна опашка и оценката на алг. е O(│E│+│V│).

Мд се посочат различни пр. от практиката: как да достигнем макс. бързо до дадена точка като се движим само в една посока. Друг възможен пример е моделиране на химич. реакция, в която се отделя енергия, т.е. движението е само в една посока от по-високо към по-ниско енергийно ниво. Най-важен пример за нас е оценката на дейнос-ти и анализ на критичния път.Посредством разглеждане на граф на дейностите необх. за завършване на софтуерен проект. Мд отговорим на следните въпроси:

- Кое е мин време за завърш на проекта;

- Колко мд закъсняват отделните дейности, без това да се отрази на крайния срок.

В графът на дейностите всеки връх пред-ставя дейност, която трд се изпълни като е посочено и времето, което заема тя.Ребрата показват реда на изпълн. на дейностите. Графът е ацикличен и освен това допуска работа в паралелизъм за независещи една от друга дейности.За да решим поставената зад.трд преобразуваме графа на дейностите в граф на събитията.При това всяко съби-тие отговаря на завършване на дейност и всички зависещи от нея дейности. За да се деф.еднозначно зависимостите м/у отдел-ните дейности, добавяме фиктивни(празни) възли, когато една дейност зависи от завършването на няколко други.



Търсим най-дългият път до края за да определим EC (earliest completion time) най-краткото време за завършване на проект. При това ще адаптираме алг. за намиране на най-къс път. Ако ECi е най-късото време за изпълнение на върха I, то изчисл.става посредством:



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



Мд определим и времето LCi (latest completion for node i), до което мд забавим даден етап, без да отлагаме крайния срок:



След резултатите от това изчисление:



Тези ст-сти могат да се изчислят за лин. време за всеки връх като се използва топо-логично сорт.за ECi и обратно топологично сорт.за LCi. Мд изчислим и луфта (slack) във време, с който разполагаме. Той показ-ва макс.закъснение за всеки връх, без да се просрочи крайния срок:

Ето пример като горната подертана цифра показва ECw, а долната – LCw. Означени-ята по ребрата са: дейност/продължител-ност/луфт. Както се вижда, някои дейности нямат закъсн.Те са критични.Път,който съ-държа такива дейности се наричакритичен.


1   2   3   4   5


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница