Back

ⓘ Едмондсов алгоритам




                                     

ⓘ Едмондсов алгоритам

Овај чланак је о алгоритму оптималног гранања. За алгоритам максималног поклапања погледајте Алгоритам максималног упаривања.

У теорији графова, грани математике, Едмондсов алгоритам или Чу-Лиу/Едмондсов алгоритам је алгоритам за проналажење максималног или минималног оптималног гранања. Овај алгоритам је сличан проблему минималног разапињућег стабла, који се тиче неусмерених графова. Ипак, када су чворови повезани усмереним гранама са тежинским коефицијентима, алгоритам минималног разапињућег стабла се не може користити.

Алгоритам оптималног гранања су предложили независно Јенг-јин Чу Yoeng-jin Chu и Ценг-хонг Лиу Tseng-hong Liu 1965. године, а затим и Едмондс 1967. године. За проналазак путање максималне дужине, узима се грана са највећим тежинским коефицијентом и повезују се одговарајућа два чвора, затим се узима следећа грана по тежини, итд. Ако одабрана грана прави петљу, уклања се и бира се наредна грана. Проналазак путање минималне дужине се врши аналогно, одабиром гране са најмањом тежином.

                                     

1. Сложеност алгоритма

Сложеност овог алгоритма је реда O E V {\displaystyle OEV}. Постоји и бржа имплементација, коју је предложио Роберт Тарјан. Сложеност тог алгоритма је реда O E log ⁡ V {\displaystyle OE\log V} за ретки граф, а реда O V 2 {\displaystyle OV^{2}} за збијени граф. Тај алгоритам је брз колико и Примов алгоритам за минимално повезујуће стабло. 1986. године, Габов Gabow, Галил Galil, Спенсер Spencer, и Тарјан Tarjan су направили бржу имплементацију, реда O E + V log ⁡ V {\displaystyle OE+V\log V}.

                                     

2.1. Алгоритам Опис

Алгоритам је рекурзиван. Са f {\displaystyle f} је означена функција која за дати усмерени граф са тежинским коефицијентима D {\displaystyle D} и чвором r {\displaystyle r} који представља корен, враћа повезујуће стабло минималне тежине, са кореном у r {\displaystyle r}.

За дати усмерени граф D {\displaystyle D} са тежинским коефицијентима и корен r {\displaystyle r} заменимо било који скуп паралелних грана између два иста чвора, у истом правцу једном граном са тежином једнаком најмањој тежини у датом скупу грана.

Даље, за сваки чвор v {\displaystyle v} различит од r {\displaystyle r}, обележимо долазећу грану најмање тежине. Означимо други крај те гране са π v {\displaystyle \pi v}. Грана је тако означена са π v, v) {\displaystyle \pi v,v)}, а придружена тежина са w π v, v) {\displaystyle w\pi v,v)}. Ако обележене гране формирају стабло најкраће путање, f D {\displaystyle fD} је то стабло. У супротном, скуп обележених грана формира бар једну петљу. Нека је C {\displaystyle C} једна од ових петљи насумично одабрана. Дефинишемо усмерени граф са тежинским коефицијентима, D ′ {\displaystyle D^{\prime }} и кореном у r ′ {\displaystyle r^{\prime }} према следећем упутству: чворови D ′ {\displaystyle D^{\prime }} су чворови D {\displaystyle D} који се не налазе у C {\displaystyle C} и нови чвор је означен са v C {\displaystyle v_{C}}.

Ако је u, v {\displaystyle u,v} грана у D {\displaystyle D} где је u ∉ C {\displaystyle u\notin C} и v ∈ C {\displaystyle v\in C}, онда треба укључити у D ′ {\displaystyle D^{\prime }} грану e = u, v C {\displaystyle e=u,v_{C}}, и дефинисати w e = w u, v − w π v, v) {\displaystyle we=wu,v-w\pi v,v)}.

Ако је u, v {\displaystyle u,v} грана у D {\displaystyle D} где је u ∈ C {\displaystyle u\in C} и v ∉ C {\displaystyle v\notin C}, онда треба укључити у D ′ {\displaystyle D^{\prime }} грану e = v C, v {\displaystyle e=v_{C},v}, и дефинисати w e = w u, v {\displaystyle we=wu,v}.

Ако је u, v {\displaystyle u,v} грана у D {\displaystyle D} где је u ∉ C {\displaystyle u\notin C} и v ∉ C {\displaystyle v\notin C}, онда треба укључити у D ′ {\displaystyle D^{\prime }} грану e = u, v {\displaystyle e=u,v}, и дефинисати w e = w u, v {\displaystyle we=wu,v}.

У D ′ {\displaystyle D^{\prime }} се не укључује ниједна друга грана.

Корен r ′ {\displaystyle r^{\prime }} стабла D ′ {\displaystyle D^{\prime }} је корен r {\displaystyle r} стабла D {\displaystyle D}.

Позивом функције f D ′ {\displaystyle fD^{\prime }}, налази се стабло најкраће путање за D ′ {\displaystyle D^{\prime }}. Прво, означе се у стаблу D {\displaystyle D} све гране које су и у D ′ {\displaystyle D^{\prime }}, а које су означене у стаблу најкраће путањеСНП за D ′ {\displaystyle D^{\prime }}. Такође, означе се у D {\displaystyle D} све гране из C {\displaystyle C}. Даље, претпоставимо да је у СНП за D ′ {\displaystyle D^{\prime }}, јединствена долазећа грана у v C {\displaystyle v_{C}} u, v C {\displaystyle u,v_{C}}. Та грана долази из неког пара u, v {\displaystyle u,v} где је u ∉ C {\displaystyle u\notin C} и v ∈ C {\displaystyle v\in C}. Треба обрисати π v, v) {\displaystyle \pi v,v)} и означити u, v {\displaystyle u,v}. Такође, за сваку означену v C, v {\displaystyle v_{C},v} у СНП за D ′ {\displaystyle D^{\prime }} која потиче од гране u, v {\displaystyle u,v} у D {\displaystyle D} где је u ∈ C {\displaystyle u\in C} и v ∉ C {\displaystyle v\notin C}, означити грану u, v {\displaystyle u,v}. Сада скуп означених грана формира СНП, што је повратна вредност f D {\displaystyle fD}.

                                     

2.2. Алгоритам Имплементација

Нека је BV скуп чворова и BE скуп грана. Нека је v чвор, а e грана са највећом позитивном тежином која повезује v. C i је петља. G 0 = V 0,E 0 је оригинални дијаграм. u i је заменски чвор за C i.

B V ← B E ← ∅ {\displaystyle BV\leftarrow BE\leftarrow \varnothing } i=0 A: if B V = V i {\displaystyle BV=V_{i}} then goto B for неки чвор v ∉ B V {\displaystyle v\notin BV} and v ∈ V i {\displaystyle v\in V_{i}} { B V ← B V ∪ { v } {\displaystyle BV\leftarrow BV\cup \lbrace v\rbrace } нађи грану e = x, v {\displaystyle e=x,v} тако да we = max{ wy,v|y,v ∈ {\displaystyle \in } E i } if we ≤ 0 then goto A } if B E ∪ { e } {\displaystyle BE\cup \lbrace e\rbrace } садржи петљу { i=i+1 конструиши G i {\displaystyle G_{i}} сажимајући C i {\displaystyle C_{i}} на u i {\displaystyle u_{i}} измени BE, BV и тежинске коефицијенте } B E ← B E ∪ e {\displaystyle BE\leftarrow BE\cup {e}} goto A B: while i ≠ 0 { реконструиши G i − 1 {\displaystyle G_{i-1}} и преименуј неке гране у BE if u i {\displaystyle u_{i}} је био корен излазног стабла BE { B E ← B E ∪ { e | e ∈ C i {\displaystyle BE\leftarrow BE\cup \lbrace e|e\in C_{i}} and e ≠ e 0 i } {\displaystyle e\neq e_{0}^{i}\rbrace } }else{ B E ← B E ∪ { e | e ∈ C i {\displaystyle BE\leftarrow BE\cup \lbrace e|e\in C_{i}} and e ≠ e ~ i } {\displaystyle e\neq {\tilde {e}}_{i}\rbrace } } i=i-1 } Максимална тежина гране = ∑ e ∈ B E w e {\displaystyle \sum _{e\in BE}we}


                                     

3. Спољашње везе

  • Edmondss algorithm edmonds-alg – An open source implementation of Edmondss algorithm written in C++ and licensed under the MIT License. This source is using Tarjans implementation for the dense graph.
  • The Directed Minimum Spanning Tree Problem Description of the algorithm summarized by Shanchieh Jay Yang, May 2000.
                                     
  • 1985. године. Неки од алгоритама који се по њему зову су Едмондсов алгоритам и Едмонд Карп алгоритам Заслужан је и за Алгоритам максималног упаривања.
  • Алгоритам максималног упаривања енгл. Blossom algorithm је алгоритам у теорији графова и користи се за конструисање максималног поклапања на графу. Алгоритам

Users also searched:

...