Hopcroft-Karp-algoritmus

Üdvözlöm, Ön a Hopcroft-Karp-algoritmus szó jelentését keresi. A DICTIOUS-ban nem csak a Hopcroft-Karp-algoritmus szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a Hopcroft-Karp-algoritmus szót egyes és többes számban mondani. Minden, amit a Hopcroft-Karp-algoritmus szóról tudni kell, itt található. A Hopcroft-Karp-algoritmus szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. AHopcroft-Karp-algoritmus és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.

Kiejtés

  • IPA:

Főnév

Hopcroft-Karp-algoritmus

  1. (matematika)

Hopcroft–Karp algoritmus

A Hopcroft–Karp algoritmus egy hatékony módszer a kétszeresen összefüggő gráfok (bipartite graphs) maximális párosításának meghatározására. Az algoritmus a Ford-Fulkerson-algoritmus speciális változata, amely optimalizált lépések révén javítja a futási időt.



Alapfogalmak

  1. Kétszeresen összefüggő gráf:
    • Egy gráf ( G = (V, E) ), amely két diszjunkt halmazból áll: ( U ) és ( V ). Az élek csak ( U )-ból ( V )-be vezethetnek (és fordítva).
  2. Párosítás (Matching):
    • A gráf egy éleinek olyan részhalmaza, amelyben egyetlen csúcs sem szerepel egynél többször.
  3. Maximális párosítás:
    • Egy párosítás, amely a lehető legtöbb élből áll.
  4. Növelő út (Augmenting Path):
    • Olyan út, amely felváltva tartalmaz párosításban szereplő és nem szereplő éleket, és az út két végpontja nem tartozik a párosításhoz.



Algoritmus működése

A Hopcroft–Karp algoritmus iteratív módon működik:

  1. Szélességi keresés (BFS):
    • Találd meg az összes legrövidebb növelő utat a párosítás bővítéséhez.
  2. Mélységi keresés (DFS):
    • Az összes lehetséges növelő utat dolgozd fel párhuzamosan.
  3. Párosítás bővítése:
    • A növelő utak segítségével frissítsd a párosítást.

Az algoritmus addig ismétli ezeket a lépéseket, amíg nem talál növelő utat.



Időbonyolultság

A Hopcroft–Karp algoritmus futási ideje , ahol: - ( E ): az élek száma, - ( V ): a csúcsok száma.

Ez gyorsabb, mint az alap Ford-Fulkerson-alapú megközelítések, amelyek ( O(VE) )-s futási időt biztosítanak.



Algoritmus Pszeudokód

HopcroftKarp(G):
    M = üres párosítás
    while True:
        növelő_út_hossz = BFS(G, M)
        if növelő_út_hossz == ∞:
            break
        while True:
            növelő_út = DFS(G, M, növelő_út_hossz)
            if növelő_út == None:
                break
            Bővítsd a párosítást M-t a növelő út szerint
    return M

Példa Pythonban

from collections import deque, defaultdict

def hopcroft_karp(graph, U, V):
    pair_u = {u: None for u in U}
    pair_v = {v: None for v in V}
    dist = {}

    def bfs():
        queue = deque()
        for u in U:
            if pair_u is None:
                dist = 0
                queue.append(u)
            else:
                dist = float('inf')
        dist = float('inf')

        while queue:
            u = queue.popleft()
            if dist < dist:
                for v in graph:
                    if dist] == float('inf'):
                        dist] = dist + 1
                        queue.append(pair_v)
        return dist != float('inf')

    def dfs(u):
        if u is not None:
            for v in graph:
                if dist] == dist + 1:
                    if dfs(pair_v):
                        pair_v = u
                        pair_u = v
                        return True
            dist = float('inf')
            return False
        return True

    matching = 0
    while bfs():
        for u in U:
            if pair_u is None:
                if dfs(u):
                    matching += 1

    return matching, pair_u, pair_v

# Példa gráf
graph = {
    'A': ,
    'B': ,
    'C': ,
    'D': ,
    'E': 
}
U = 
V = 

matching, pair_u, pair_v = hopcroft_karp(graph, U, V)
print(f"Maximális párosítás mérete: {matching}")
print(f"Párosítás: {pair_u}")

Példa C++-ban

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <algorithm>

using namespace std;

const int INF = numeric_limits<int>::max();

bool bfs(vector<vector<int>>& graph, vector<int>& pair_u, vector<int>& pair_v, vector<int>& dist, int U) {
    queue<int> q;
    for (int u = 0; u < U; ++u) {
        if (pair_u == -1) {
            dist = 0;
            q.push(u);
        } else {
            dist = INF;
        }
    }
    dist = INF;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (dist < dist) {
            for (int v : graph) {
                if (dist] == INF) {
                    dist] = dist + 1;
                    q.push(pair_v);
                }
            }
        }
    }
    return dist != INF;
}

bool dfs(vector<vector<int>>& graph, vector<int>& pair_u, vector<int>& pair_v, vector<int>& dist, int u) {
    if (u != -1) {
        for (int v : graph) {
            if (dist] == dist + 1) {
                if (dfs(graph, pair_u, pair_v, dist, pair_v)) {
                    pair_v = u;
                    pair_u = v;
                    return true;
                }
            }
        }
        dist = INF;
        return false;
    }
    return true;
}

int hopcroft_karp(vector<vector<int>>& graph, int U, int V) {
    vector<int> pair_u(U, -1), pair_v(V, -1);
    vector<int> dist(U + 1);
    int matching = 0;

    while (bfs(graph, pair_u, pair_v, dist, U)) {
        for (int u = 0; u < U; ++u) {
            if (pair_u == -1) {
                if (dfs(graph, pair_u, pair_v, dist, u)) {
                    ++matching;
                }
            }
        }
    }
    return matching;
}

int main() {
    int U = 5, V = 3;
    vector<vector<int>> graph = {
        {0, 1},  // A -> 1, 2
        {0},     // B -> 1
        {1, 2},  // C -> 2, 3
        {2},     // D -> 3
        {2}      // E -> 3
    };

    int result = hopcroft_karp(graph, U, V);
    cout << "Maximális párosítás mérete: " << result << endl;

    return 0;
}

Előnyök

  1. Hatékony futási idő:
    • (O(E )), ami gyorsabb, mint az alapvető párosítási algoritmusok.
  2. Könnyen implementálható:
    • Bár komplexebb, a BFS és DFS kombinációja jól érthető.



Hátrányok

  1. Speciális gráfok:
    • Kizárólag kétszeresen összefüggő gráfokra alkalmazható.
  2. Memóriaköltség:
    • Nagy gráfok esetén a memóriahasználat megnövekedhet.



Alkalmazások

  1. Munkaerő-kiosztás:
    • Feladatok és munkavállalók hatékony párosítása.
  2. Házassági probléma:
    • Stabil párosítások keresése.
  3. Hálózatok:
    • Adatátvitel és útvonal-optimalizáció kétszeresen összefüggő gráfokban.



Összegzés

A Hopcroft–Karp algoritmus az egyik leghatékonyabb módszer a maximális párosítás megtalálására kétszeresen összefüggő gráfokban. Kiváló teljesítménye miatt széles körben alkalmazzák optimalizációs és hálózati problémákban.