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



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

45.Пропускателна способност на мрежа (network flow problems)


Даден е ориентиран граф с указан капаци-тет на всяко ребро cv,w. Този капацитет мд показва пропускателна способност на тръ-ба,на улица и т.н. Дадени са два върха s и t. Търсим макс.поток,който мд мине от s до t.

Всяко ребро мд поеме поток равен на капа-цитета си. Означенията в макс поток в граф са, както следва: връх а има входен поток 3 ед-ци, които се разпределят към c и d. Връх d също има входен капацитет 3 единици, които получава от a и b и ги предава на t.

За построим макс. поток в граф, работим поетапно. На основа на графа G, строим граф на потоците(flow graph) Gf, съдържащ потоците определени до момента. В нач. всички ребра имат нулев поток.При прик-лючване на алг. Gf ще съдържа макс.поток. При това строим и граф с остатъч. потоци Gr (residual graph), съдържащ неизполз. капацитети по всяко ребро (разликата от капацитета и използ.количество).Търсим път от s към t в Gr. Мин.капацитет на реб-ро по този път е възможния за добавяне в поток. Добавяме го в Gf. Продължаваме по този начин, докато не се изчерпят всички пътища в Gr. Алг.е недетерминиран, защо-то няма стратегия за последователността на избор на възможните пътища.



Избираме един от възможните пътища: s-b-d-t. Мин.поток тук е 2 единици.Когато реб-ровият капацитет се запълни, премахваме ребро от графа Gr.

=>избор на нов път.Той е s-a-c-t с мин. поток 2 единици

=>пътя s-a-d-t с мин.поток 1. Тази единица се добавя към теглата в Gf. Алг.приключва, защото няма повече пътища в Gr.

Накрая сумираме входните капацитети в Gf за върха t и получаваме макс.поток. В случая той е 5 единици. Сега ще покажем недетерминираността на алг. Ако в нач. тръгнем по пътя s-a-d-t, ще допуснем поток от 3 единици. Това е добър резултат, но в Gr не остава път от s към t (фиг. 25). Това е пример как greedy алг.не винаги работят



Трябва промяна в алг., за да бъде винаги работещ. За целта, за всяко ребро (v,w) с поток fv,w от графа Gf,добавяме ребро (w,v) с поток fv,w в графа Gr. Това ще ни позволи връщане назад. Така, избирайки пътя s-a-d-t, получаваме графа, показан на фиг.Това означава, че една или повече единици мд вървят от a към d и до 3 единици мд вървят от d към a (поток undo)



Разсъждавайки по този начин, налице е нов път s-b-d-a-c-t, който има поток 2 единици. Това означава, че щом връщаме от d към a поток, то по тази тръба могат да минат същите единици и в обратна посока, от d към a, стига да има наличен път



Отново макс. поток е 5 единици, но сме елиминирали възможността грешен нач. избор на път да повлияе върху решението. Доказано е, че така модифицирам алг., винаги открива максималния поток. Нещо повече, алг.работи и при цикличен граф.

Накрая ще направим оценка на алг. Ако капацитетите са цели числа, всяка итера-ция увеличава потока поне с една единица. Ако макс.поток е f,то f етапа са достатъчни за намирането му и времето е O(f*│E│). Това е така, защото път мдб намерен за O(│E│) време, при използване на алг. за намиране на най-къс път в безтегловен граф (unweighted shortest path). За да нама-лим времето, ще избираме винаги пътя с макс поток, при което ще приложим алг.на Дейкстра. Ако capmax е макс.капацитет на дадено ребро, то O(│E│log capmax) итера-ции са необх.за получаване на макс.поток. Знаем, че времето за една итерация е O(│E│log│V│) и => общото време ще е O(│E│2log│V│log capmax). Ако работим с много малки капацитети, едно добро прибл.се дава с времето O(│E│2log│V│).

Друг начин за избор на текущ път е пътя с мин.брой ребра. В този случай етапите са O(│E│*│V│) и след като всеки етап изисква O(│E│)време(отново използ.алг.за най-къс път),получаваме O(│E│2│V│) за общото време.За по-нататъшно подобрение на времето, трд се смени структурата данни. Възможно е подобрение на времето и при налагане на някои ограничения,напр. за граф, в който всеки връх има само едно входящо или едно изходящо ребро (без s и t, разбира се) с капацитет 1. В този случай времето е O(│E││V│1/2).


46. Минимално обхващащо дърво. Алг. на Прим. Алг. на Крускал


Ще търсим мин.обхващащо дърво в неори-ентиран граф. Зад.има смисъл и за ориен-тиран граф, но там алг.е по-труден. За да-ден граф G, мин.обхващащо дърво е дърво-то, изградено от дъги на графа, които свър-зват върховете му на мин.цена. Мин.обхва-щащо дърво съществува само,ако графа е свързан. Ще работим при това ограниче-ние. Пр. окабеляване на жилища.

минималното обхващащо дърво има │V│-1 ребра. За всяко мин.обхващащо дърво T, ако ребро (v,w), което не съществува в T се добави, се създава цикъл. Изтриването на всяко ребро от цикъла, възстановява мин. обхващащо дърво. Цената на мин.обхва-щащо дърво е толкова по-ниска, колкото по по-ниска е цената на изграждащите го ребра, следователно при изграждането на мин.обхващащо дърво трябва да добавяме ребро с мин.стойност. Ще разгледаме два алг.,които се различават по избора на ребро с минимална стойност


Алгоритъм на Прим (Prim)


Работим на етапи. На всеки етап взимаме един връх v от дървото за корен, добавяме друг w от невключените до момента и асо-циираме ребро в дървото. Измежду всички ребра (v,w), за които v е от дървото, а w не е, избираме това, което има мин.цена. На фиг.е показано как работи алг.с начало v1. В нач.момент v1 е дървото и на всеки етап добавяме по един връх и едно ребро

Алг.е подобен на този на Дейкстра.Както и преди ще поддържаме dv, pv и Known. dv е мин.тегло на реброто (v,w), където w е пре-дшественика на v с Known=T. pv съдържа последния връх w,който е променил dv.Ос-таналата част от алг.е същата. Единствено се променя актуализацията на dv: след избор на връх v, за всички съседи w с Known=F на v, dw=min(dw,cv,w).

Нач.на алг. е показано на фиг. 30.На фиг. 31 е избран върха v1, а за v2, v3 и v4 са актуализирани dv и pv. Следващият избран връх е v4. Всички останали върхове са му съседи. V1 се изключва от разглеждането, защото има Known=T, информацията за v2 не се променя, защото dv =2, а стойността на реброто (v4, v2) е 3. Всички останали върхове се актуализират (фиг. 32).



Следващият избран връх е v2. Неговият избор не води до промяна на dv. По-нататък избираме v3. При това се променя dv на v6, както е показано на фиг. 33. Фиг. 34 показва резултата след избор на v7, при което се променя dv за v6 и v5. След избор на v6 и v5, алг.приключва своята работа. Крайният резултат е показан на фиг. 35. Ребрата на мин. обхващащо дърво се получават от таблицата и са както следва: (v2, v1), (v3, v4), (v4, v1), (v5, v7), (v6, v7), (v7, v4). Общата цена е 16

V

Фиг.30

Фиг.31

K

dv

pv

K

dv

pv

V1

F

0

0

F

0

0

V2

F



0

F



0

V3

F



0

F



0

V4

F



0

F



0

V5

F



0

F



0

V6

F



0

F



0

V7

F



0

F



0

V

Фиг.32

Фиг.33

K

dv

pv

K

dv

pv

V1

T

0

0

T

0

0

V2

F

2

V1

T

2

V1

V3

F

2

V4

T

2

V4

V4

T

1

V1

T

1

V1

V5

F

7

V4

F

7

V4

V6

F

8

V4

F

5

V3

V7

F

4

V4

F

4

V4

V

Фиг.34

Фиг.35

K

dv

pv

K

dv

pv

V1

T

0

0

T

0

0

V2

T

2

V1

T

2

V1

V3

T

2

V4

T

2

V4

V4

T

1

V1

T

1

V1

V5

F

6

V7

T

6

V7

V6

F

1

V7

T

1

V7

V7

T

4

V4

T

4

V4

Реализацията на този алг.е идентична на Дейкстра. Аналогично е и положението с анализа. Трябва да се внимава при реали-зацията на алг.при неоринтирани графи. Тогава всяко ребро трябва да участва два пъти в списъка на съседите. Времето е O(│V│2) без използване на heap, което е оптимал.за плътни графи и O(│E│log│V│) при използване на двоичен heap – добро решение за разредени графи.

Алгоритъм на Крускал (Kruskal)


Стратегията тук е да се избере ребро с най-малко тегло и да се одобри, ако не форми-ра цикъл. За графа от предходния пример действията са показани на фиг. 36. При това се попълва таблица, в която за всяко ребро се записва неговото тегло и флаг, който показва дали върха е отхвърлен или не. Табл. за графа от предходния пример е показана на фиг. 37.



Ребро

Тегло

Флаг

(v1,v4)

1

Включено

(v6,v7)

1

Включено

(v1,v2)

2

Включено

(v3,v4)

2

Включено

(v2,v4)

3

Отхвърлено

(v1,v3)

4

Отхвърлено

(v4,v7)

4

Включено

(v3,v6)

5

Отхвърлено

(v5,v7)

6

Включено

Погледнато формално алг. на Крускал работи с множество дървета. В нач. това са │V│ броя дървета, състоящи се от по един връх. Добавяйки ребро,сливаме 2 дървета в едно. Алг.приключва когато са включени необх.брой ребра. При това е налице само едно дърво и то е търсеното. При добавяне-то на ребро се използва следното правило: ако v и w са два върха в едно дърво, ребро-то, което ги свързва, не се избира за разгле-ждане,защото формира цикъл.В противен случай реброто се включва и двете дървета (включващи v и w) се сливат. Вижда се, че множествата са инвариантни (върховете в тях стоят постоянно) и към тях само мд се добавят нови чрез сливане на дървета. Реб-рата могат да се сортират за ускоряване на търсенето, но изграждането на heap е по-добра идея за ускоряване.

Void Graph::kruskal()

{ int edgeAccepted;

DisjSet s(NUM_VERTICES);

PriorityQueue h(NUM_EDGES);

Vertex u,v;

SetType uset, vset;

Edge e;


h = readGraphIntoHeapArray();

h.buildHeap();

edgeAccepted=0;

while (edgeAccepted

{ h.deleteMin(e);

uset = s.find(u);

vset = s.find(v);

if (uset!=vset)

{ edgesAccepted++;

s.unionSets(uset,vset);



}

}

}



Оценката на алг. е O(│E│log│Е│) в най-лошия случай, което се определя от heap операциите. Отбележете, че тъй като │E│ = O(│V│2), то времето за изпълнение ще бъде O(│E│log│V│).
1   2   3   4   5


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

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