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

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

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

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

Трябва промяна в алг., за да бъде винаги работещ. За целта, за всяко ребро (v,w) с поток f_v,w от графа Gf,добавяме ребро (w,v) с поток f_v,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). За да нама-лим времето, ще избираме винаги пътя с макс поток, при което ще приложим алг.на Дейкстра. Ако cap_max е макс.капацитет на дадено ребро, то O(│E│log cap_max) итера-ции са необх.за получаване на макс.поток. Знаем, че времето за една итерация е O(│E│log│V│) и => общото време ще е O(│E│²log│V│log cap_max). Ако работим с много малки капацитети, едно добро прибл.се дава с времето O(│E│²log│V│).

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

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

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

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

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

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

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

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

Следващият избран връх е v2. Неговият избор не води до промяна на d_v. По-нататък избираме v3. При това се променя d_v на v6, както е показано на фиг. 33. Фиг. 34 показва резултата след избор на v7, при което се променя d_v за 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│²) без използване на 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│).

Каталог: lib
lib -> Преводач Елена Атанасова Коректор Ива Данева Формат 84/108/32 Печатни коли 15 дф „абагар" Велико Търново ик „сова" Варна как да се използва тази книга
lib -> За медитацията ошо въведение
lib -> Поредица ние обичаме животните
lib -> Тайната на скорпион
lib -> Разчупване на оковите Победа над: Отрицателните мисли
lib -> Въведение

Изтегляне 0.84 Mb.

Сподели с приятели: