El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Algoritmes de Flux Màxim

Següent ►
►

Els algoritmes de flux màxim són fonamentals en la teoria de grafs i tenen aplicacions en una àmplia varietat de camps, com ara la logística, les xarxes de comunicació, la planificació de projectes i molts altres. En aquesta secció, explorarem els conceptes bàsics del flux màxim, els algoritmes més utilitzats per trobar el flux màxim en un graf i alguns exemples pràctics.

Conceptes Bàsics

Abans d'entrar en els algoritmes, és important entendre alguns conceptes clau relacionats amb el flux màxim:

  1. Graf Dirigit: Un graf on les arestes tenen una direcció associada.
  2. Capacitat: Cada aresta del graf té una capacitat que indica el màxim flux que pot transportar.
  3. Font (s): El node d'on surt el flux.
  4. Destí (t): El node on arriba el flux.
  5. Flux: La quantitat de "càrrega" que es mou des de la font fins al destí a través de les arestes del graf.
  6. Camí Augmentant: Un camí des de la font fins al destí on es pot augmentar el flux.

Algoritmes Principals

Algoritme de Ford-Fulkerson

L'algoritme de Ford-Fulkerson és un dels més coneguts per trobar el flux màxim en un graf. Funciona de la següent manera:

  1. Inicialització: Comença amb un flux inicial de 0.
  2. Cerca de Camins Augmentants: Busca un camí augmentant des de la font fins al destí.
  3. Augment del Flux: Augmenta el flux al llarg del camí augmentant trobat.
  4. Repetició: Repeteix els passos 2 i 3 fins que no es puguin trobar més camins augmentants.

Exemple de Codi

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.ROW = vertices

    def add_edge(self, u, v, w):
        self.graph[u].append((v, w))

    def bfs(self, s, t, parent):
        visited = [False] * self.ROW
        queue = []
        queue.append(s)
        visited[s] = True

        while queue:
            u = queue.pop(0)

            for ind, val in enumerate(self.graph[u]):
                v, w = val
                if visited[v] == False and w > 0:
                    queue.append(v)
                    visited[v] = True
                    parent[v] = u

        return True if visited[t] else False

    def ford_fulkerson(self, source, sink):
        parent = [-1] * self.ROW
        max_flow = 0

        while self.bfs(source, sink, parent):
            path_flow = float("Inf")
            s = sink

            while s != source:
                for v, w in self.graph[parent[s]]:
                    if v == s:
                        path_flow = min(path_flow, w)
                s = parent[s]

            max_flow += path_flow

            v = sink
            while v != source:
                u = parent[v]
                for i, (vertex, weight) in enumerate(self.graph[u]):
                    if vertex == v:
                        self.graph[u][i] = (vertex, weight - path_flow)
                for i, (vertex, weight) in enumerate(self.graph[v]):
                    if vertex == u:
                        self.graph[v][i] = (vertex, weight + path_flow)
                v = parent[v]

        return max_flow

# Exemple d'ús
g = Graph(6)
g.add_edge(0, 1, 16)
g.add_edge(0, 2, 13)
g.add_edge(1, 2, 10)
g.add_edge(1, 3, 12)
g.add_edge(2, 1, 4)
g.add_edge(2, 4, 14)
g.add_edge(3, 2, 9)
g.add_edge(3, 5, 20)
g.add_edge(4, 3, 7)
g.add_edge(4, 5, 4)

source = 0
sink = 5

print("El flux màxim és %d" % g.ford_fulkerson(source, sink))

Algoritme d'Edmonds-Karp

L'algoritme d'Edmonds-Karp és una implementació específica de l'algoritme de Ford-Fulkerson que utilitza una cerca en amplada (BFS) per trobar camins augmentants. Això garanteix una complexitat temporal de \(O(VE^2)\), on \(V\) és el nombre de vèrtexs i \(E\) és el nombre d'arestes.

Algoritme de Push-Relabel

Aquest algoritme és una alternativa als anteriors i es basa en la idea de "empenyiment" (push) i "relabeling" (relabel). Funciona de la següent manera:

  1. Inicialització: Assigna un excés de flux a cada node.
  2. Empenyiment: Mou el flux des d'un node amb excés a un node adjacent.
  3. Relabel: Augmenta l'altura d'un node per permetre més moviments de flux.

Aquest algoritme té una complexitat temporal de \(O(V^2E)\).

Exercicis Pràctics

Exercici 1: Implementació de l'Algoritme de Ford-Fulkerson

Implementa l'algoritme de Ford-Fulkerson per trobar el flux màxim en un graf donat. Utilitza el següent graf com a exemple:

Nodes: 0, 1, 2, 3, 4, 5
Arestes: (0, 1, 10), (0, 2, 5), (1, 2, 15), (1, 3, 10), (2, 4, 10), (3, 4, 10), (3, 5, 10), (4, 5, 10)

Solució

# Implementació de l'algoritme de Ford-Fulkerson
g = Graph(6)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 5)
g.add_edge(1, 2, 15)
g.add_edge(1, 3, 10)
g.add_edge(2, 4, 10)
g.add_edge(3, 4, 10)
g.add_edge(3, 5, 10)
g.add_edge(4, 5, 10)

source = 0
sink = 5

print("El flux màxim és %d" % g.ford_fulkerson(source, sink))

Exercici 2: Comparació d'Algoritmes

Implementa tant l'algoritme de Ford-Fulkerson com l'algoritme d'Edmonds-Karp i compara el temps d'execució per a diferents grafs.

Solució

import time

# Implementació de l'algoritme d'Edmonds-Karp
class GraphEdmondsKarp(Graph):
    def bfs(self, s, t, parent):
        visited = [False] * self.ROW
        queue = []
        queue.append(s)
        visited[s] = True

        while queue:
            u = queue.pop(0)

            for ind, val in enumerate(self.graph[u]):
                v, w = val
                if visited[v] == False and w > 0:
                    queue.append(v)
                    visited[v] = True
                    parent[v] = u

        return True if visited[t] else False

    def edmonds_karp(self, source, sink):
        parent = [-1] * self.ROW
        max_flow = 0

        while self.bfs(source, sink, parent):
            path_flow = float("Inf")
            s = sink

            while s != source:
                for v, w in self.graph[parent[s]]:
                    if v == s:
                        path_flow = min(path_flow, w)
                s = parent[s]

            max_flow += path_flow

            v = sink
            while v != source:
                u = parent[v]
                for i, (vertex, weight) in enumerate(self.graph[u]):
                    if vertex == v:
                        self.graph[u][i] = (vertex, weight - path_flow)
                for i, (vertex, weight) in enumerate(self.graph[v]):
                    if vertex == u:
                        self.graph[v][i] = (vertex, weight + path_flow)
                v = parent[v]

        return max_flow

# Comparació de temps d'execució
g = Graph(6)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 5)
g.add_edge(1, 2, 15)
g.add_edge(1, 3, 10)
g.add_edge(2, 4, 10)
g.add_edge(3, 4, 10)
g.add_edge(3, 5, 10)
g.add_edge(4, 5, 10)

source = 0
sink = 5

start_time = time.time()
print("El flux màxim amb Ford-Fulkerson és %d" % g.ford_fulkerson(source, sink))
print("Temps d'execució: %s segons" % (time.time() - start_time))

g_ek = GraphEdmondsKarp(6)
g_ek.add_edge(0, 1, 10)
g_ek.add_edge(0, 2, 5)
g_ek.add_edge(1, 2, 15)
g_ek.add_edge(1, 3, 10)
g_ek.add_edge(2, 4, 10)
g_ek.add_edge(3, 4, 10)
g_ek.add_edge(3, 5, 10)
g_ek.add_edge(4, 5, 10)

start_time = time.time()
print("El flux màxim amb Edmonds-Karp és %d" % g_ek.edmonds_karp(source, sink))
print("Temps d'execució: %s segons" % (time.time() - start_time))

Conclusió

En aquesta secció, hem explorat els conceptes bàsics del flux màxim, així com els algoritmes més utilitzats per trobar el flux màxim en un graf. Hem vist com implementar l'algoritme de Ford-Fulkerson i l'algoritme d'Edmonds-Karp, i hem comparat els seus temps d'execució. Amb aquests coneixements, estàs preparat per abordar problemes complexos de flux en grafs i aplicar aquests algoritmes en situacions reals.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats