Форд-Фулкерсон алгоритам

Из Википедије, слободне енциклопедије

Форд-Фулкерсон метод (назван по Л. Р. Форду, мл. и Д. Р. Фулкерсону је алгоритам који рачуна максимални проток у транспортној мрежи. Објављен је 1956. Име "Форд-Фулкерсон" се често користи и за Едмондс-Карп алгоритам, који је специјализација Форд-Фулкерсона.

Основна идеја је једноставна. Докле год постоји путања од извора (почетни чвор) до понора (крајњи чвор), са доступним капацитетима на свим гранама путање, слаћемо проток дуж једне од ових путања. Тада проналазимо нову путању итд. Путања се доступним капацитетом се назива појачавајућа путања.

Алгоритам[уреди]

Нека је G(V,E) граф и нека за сваку грану од u до v c(u,v) представља капацитет, а f(u,v) проток дуж гране. Ми желимо да пронађемо максималан проток од извора s до понора t. Након сваког корака у алгоритму, следећа тврђења су тачна:

Ограничења капацитета: \forall (u, v) \in E \ f(u,v) \le c(u,v) Проток кроз грану не може премашити њен капацитет.
Коса симетрија: \forall (u, v) \in E \ f(u,v) = - f(v,u) Укупан проток од u до v мора бити супротан од протока од v до u (видети пример).
Очување протока: \forall u \in V: u \neq s \text{ and } u \neq t \Rightarrow \sum_{w \in V} f(u,w) = 0 Под условом да u није s или t. Укупан проток ка неком чвору је нула, осим ако чвор није извор, који "ствара" проток, или понор, који "троши" проток.

Ово значи да је проток кроз мрежу дозвољени проток након сваког понављања у алгоритму. Дефинишемо резидуалну мрежу G_f(V,E_f) као мрежу капацитета c_f(u,v) = c(u,v) - f(u,v) и без протока. Обратите пажњу да може да се деси да проток од v до u буде дозвољен у резидуалној мрежи, иако недозвољен у почетној мрежи: ако f(u,v)>0 и c(v,u)=0 тада c_f(v,u)=c(v,u)-f(v,u)=f(u,v)>0.

Алгоритам Форд-Фулкерсон

Улаз Граф G са капацитетима c, извором s и понором t
Излаз Проток f од s до t који је максималан
  1. f(u,v) \leftarrow 0 за све гране (u,v)
  2. Док постоји путања p од s до t у G_f, таква да је c_f(u,v) > 0 за све гране (u,v) \in p:
    1. Пронађи c_f(p) = \min\{c_f(u,v) : (u,v) \in p\}
    2. За сваку грану(u,v) \in p
      1. f(u,v) \leftarrow f(u,v) + c_f(p) (Пошаљи проток дуж путање)
      2. f(v,u) \leftarrow f(v,u) - c_f(p) (Проток се може "вратити" касније)

Путања из корака 2 се може пронаћи уз помоћ претраге у ширину или претраге у дубину у графу G_f(V,E_f). Уколико користите претрагу у ширину, онда се зове Едмондс-Карп алгоритам.

Када се више ниједна путања не може пронаћи, тада се из s не може доћи до t у резидуалној мрежи. Ако је S скуп чворова до којих се може доћи у резидуалној мрежи из s, онда је укупан капацитет почетне мреже грана од S до V са једне стране једнак укупном протоку који смо пронашли од s до t, а са друге стране служи као горња граница за све такве протоке. То доказује да је проток који смо пронашли максималан.

Сложеност[уреди]

Додајући појачавајуће путање протоку који је већ утврђен у графу доћи ћемо до максималног протока када више не будемо могли да пронађемо нове појачавајуће путање. Међутим, не постоји сигурност да ће се до ове ситуације икад доћи, тако да је једино сигурно да уколико се алгоритам заустави да ће одговор бити тачан. У случају да алгоритам ради бесконачно, може се десити да проток уопште не конвергира ка максималном протоку. Али, ова ситуација се догађа само са ирационалним вредностима протока. Када су капацитети цели бројеви, време извршавања је ограничено са O(E f) (видети велико О), где је E број грана у графу и f максималан проток графа. Ово је зато што се појачавајућа путања може пронаћи у O(E) времена и повећати проток за целобројну вредност која је минимум 1.

Варијација Форд-Фулкерсон алгоритма који гарантује завршетак и временски је независна од максималног протока у графу је Едмондс-Карп алгоритам који раду времену O(VE^2).

Главни пример[уреди]

Следећи пример показује прве кораке Форд-Фулкерсона у проточној мрежи са 4 чвора, извором A и понором D. Овај пример показује понашање алгоритма у најгорем случају. У сваком кораку се корз мрежу шаље проток од 1. Да смо искористили претрагу у ширину, само два корака би била потребна.

Путања Капацитет Резултујућа мрежа
Почетна мрежа Ford-Fulkerson example 0.svg
A,B,C,D \min(c_f(A,B), c_f(B,C), c_f(C,D))=

\min(c(A,B)-f(A,B) ,c(B,C)-f(B,C), c(C,D)-f(C,D))=
\min(1000-0, 1-0, 1000-0)=1

Ford-Fulkerson example 1.svg
A,C,B,D \min(c_f(A,C), c_f(C,B), c_f(B,D))=

\min(C), c(C,B)-f(C,B), c(B,D)-f(B,D))=
\min(1000-0, 0-(-1), 1000-0)=1

Ford-Fulkerson example 2.svg
Након још 1998 корака…
Коначни изглед мреже. Ford-Fulkerson example final.svg

Приметите како се проток "гура назад" од C до B када се тражи путања A,C,B,D.

Незавршавајући пример[уреди]

Ford-Fulkerson forever.svg

Размотрите мрежу дату десно, са извором s, понором t и капацитетима грана e_1, e_2 и e_3 1, r=(\sqrt{5}-1)/2 и 1, респективно, а капацитет свих других грана је неко M \ge 2. Константа r је одабрана, јер r^2 = 1 - r. Користимо појачавајуће путање у складу са датом табелом, где је p_1 = \{ s, v_4, v_3, v_2, v_1, t \}, p_2 = \{ s, v_2, v_3, v_4, t \} и p_3 = \{ s, v_1, v_2, v_3, t \}.

Корак Појачавајућа путања Послат проток Преостали проток
e_1 e_2 e_3
0 r^0=1 r 1
1 \{ s, v_2, v_3, t \} 1 r^0 r^1 0
2 p_1 r^1 r^2 0 r^1
3 p_2 r^1 r^2 r^1 0
4 p_1 r^2 0 r^3 r^2
5 p_3 r^2 r^2 r^3 0

Обратите пажњу на то да након корака 1, као и након корака 5, преостали капацитет грана e_1, e_2 и e_3 су у облику r^n, r^{n+1} and 0, за неко n \in \mathbb{N}. Ово значи да можемо користити појачавајуће путање p_1, p_2, p_1 и p_3 бесконачно много пута и преостали капацитет ових грана ће увек имати исти облик. Укупан проток у мрежи након корака 5 је 1 + 2(r^1 + r^2). Ако наставимо да користимо ове појачавајуће путање, укупан проток тежи ка \textstyle 1 + 2\sum_{i=1}^\infty r^i = 3 + 2r, док је максималан проток 2M + 1. У овом случају се алгоритам никад не завршава, а проток ни не тежи ка максималном протоку.[1]

Имплементација у програмском језику Пајтон[уреди]

class Edge(object):
    def __init__(self, u, v, w):
        self.source = u
        self.sink = v
        self.capacity = w
    def __repr__(self):
        return "%s->%s:%s" % (self.source, self.sink, self.capacity)
 
class FlowNetwork(object):
    def __init__(self):
        self.adj = {}
        self.flow = {}
 
    def add_vertex(self, vertex):
        self.adj[vertex] = []
 
    def get_edges(self, v):
        return self.adj[v]
 
    def add_edge(self, u, v, w=0):
        if u == v:
            raise ValueError("u == v")
        edge = Edge(u,v,w)
        redge = Edge(v,u,0)
        edge.redge = redge
        redge.redge = edge
        self.adj[u].append(edge)
        self.adj[v].append(redge)
        self.flow[edge] = 0
        self.flow[redge] = 0
 
    def find_path(self, source, sink, path):
        if source == sink:
            return path
        for edge in self.get_edges(source):
            residual = edge.capacity - self.flow[edge]
            if residual > 0 and not (edge,residual) in path:
                result = self.find_path(edge.sink, sink, path + [(edge,residual)] ) 
                if result != None:
                    return result
 
    def max_flow(self, source, sink):
        path = self.find_path(source, sink, [])
        while path != None:
            flow = min(res for edge,res in path)
            for edge,res in path:
                self.flow[edge] += flow
                self.flow[edge.redge] -= flow
            path = self.find_path(source, sink, [])
        return sum(self.flow[edge] for edge in self.get_edges(source))

Пример употребе[уреди]

За проблем из Проблем максималног тока радимо следеће:

g=FlowNetwork()
map(g.add_vertex, ['s','o','p','q','r','t'])
g.add_edge('s','o',3)
g.add_edge('s','p',3)
g.add_edge('o','p',2)
g.add_edge('o','q',3)
g.add_edge('p','r',2)
g.add_edge('r','t',3)
g.add_edge('q','r',4)
g.add_edge('q','t',2)
print g.max_flow('s','t')

Output: 5

Референце[уреди]

  1. ^ Zwick, Uri (21. 8. 1995.). „The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate“. Theoretical Computer Science 148 (1): 165–170. DOI:10.1016/0304-3975(95)00022-O. 

Литература[уреди]

Спољашње везе[уреди]