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 квадранта:

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

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( N^log²⁷ )=O( N ²^.81 )

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

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

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

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

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

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

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

На основата на тази формула се гради алг. за цена на оптималното дърво.Търсим 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 ³) защото имаме тройно вложен цикъл

38. Алг. с 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}

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

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

Избираме едното за да продълж. Нека 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.

Int TicTakToe::

findCompMove( int & bestMove)

{int i, responseValue;

{ //update best move

}

}

} return value; }

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

findHumanMove( int & bestMove)

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

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

{place(i,HUMAN);

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

}}

}} return value;}

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

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

min 44 36

max 44 78 40 36

min 27 44 68 78 40 27 36 36

42 27 86 44 ………

min 44 40

max 44 68 40 D

min 42 27 68 C 40 27

max >=44

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

max 44 >=68

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

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

Краен ориентиран граф се нарича наредената двойка 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 са две топологични подредби. Алгоритъмът първо открива връх без входящи ребра. После го премахва заедно със ребрата от него. Тази операция се повтаря докато не се изчерпи списъка с върховете без входящи ребра.

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

{ 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)

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

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

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

{ 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),и алг.спира

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)

{ 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

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

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

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

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

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

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

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

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

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

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

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