Wikiszótár

Fiduccia-Mattheyses-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈfidut͡sːijɒmɒthɛiʃɛʃɒlɡoritmuʃ]

Főnév

Fiduccia-Mattheyses-algoritmus

  1. (matematika)

Fiduccia-Mattheyses (FM) algoritmus

A Fiduccia-Mattheyses-algoritmus egy gyors és hatékony algoritmus gráfok particionálására, amelyet főként az elektronikai tervezésben (VLSI áramkörök optimalizálása) használnak. Az algoritmus célja egy gráf csúcsainak két részre bontása úgy, hogy a két rész közötti élkapcsolatok száma minimális legyen, miközben a particiók egyensúlyban maradnak (azaz hasonló méretűek).


Algoritmus jellemzői

  1. Bemenet:
    • Egy súlyozott gráf ( G(V, E) ), ahol ( V ) a csúcsok, ( E ) az élek halmaza.
    • A csúcsokhoz és élekhez súlyok rendelhetők.
  2. Kimenet:
    • Két partició: ( P_1 ) és ( P_2 ), amelyek egyensúlyban vannak.
    • Az élvágások száma (cut size) minimális.
  3. Alapötlet:
    • Greedy csúcsmozgás: Minden iterációban egy csúcsot mozgatunk az egyik particióból a másikba, amely a legnagyobb javulást hozza az élvágások számában.
    • Gain: Egy csúcs mozgatása által okozott javulás vagy romlás az élvágások számában.
  4. Hatékonyság:
    • Az algoritmus időkomplexitása ( O(|E| + |V| |V|) ), ami gyorsnak számít nagy gráfokra.


Algoritmus lépései

  1. Kezdeti partició:
    • Osszuk két részre a gráf csúcsait valamilyen kezdeti módszerrel (pl. véletlenszerűen).
  2. Gain számítás:
    • Számítsuk ki minden csúcsra a particiók közötti mozgatás által okozott gain értéket: [ (v) = {}(v) - {}(v), ] ahol ( {} ) az élek súlyainak összege a csúcs jelenlegi particiójában, és ( {} ) az élek súlyainak összege a másik particióban.
  3. Csúcs mozgatása:
    • Mozgassuk azt a csúcsot, amely a legnagyobb gain-t eredményezi, miközben fenntartjuk a particiók egyensúlyát.
  4. Locking:
    • Zárjuk le a már mozgatott csúcsokat, hogy ne kerüljenek vissza ugyanabban az iterációban.
  5. Iteráció:
    • Ismételjük addig, amíg nem érünk el lokális optimumot.
  6. Globális optimum keresése:
    • Az algoritmust többször futtathatjuk különböző kezdeti particiókkal, hogy közelebb kerüljünk a globális optimumhoz.


Python Implementáció

Az alábbi Python-kód egyszerűsíti az FM-algoritmus lényegét. 

import random
from collections import defaultdict

def calculate_gain(graph, part1, part2, vertex):
    """Gain kiszámítása a csúcs mozgatásához."""
    E_from = sum(weight for neighbor, weight in graph[vertex] if neighbor in part1)
    E_to = sum(weight for neighbor, weight in graph[vertex] if neighbor in part2)
    return E_to - E_from

def fiduccia_mattheyses(graph, initial_part1):
    """
    Fiduccia-Mattheyses algoritmus implementáció.
    
    :param graph: Gráf (szomszédsági lista súlyokkal)
    :param initial_part1: Az első partició kezdeti csúcsai
    :return: Optimalizált particiók
    """
    vertices = set(graph.keys())
    part1 = set(initial_part1)
    part2 = vertices - part1

    locked = set()
    best_cut_size = float('inf')
    best_part1, best_part2 = None, None

    while len(locked) < len(vertices):
        gains = {}
        for vertex in vertices - locked:
            if vertex in part1:
                gains[vertex] = calculate_gain(graph, part1, part2, vertex)
            else:
                gains[vertex] = calculate_gain(graph, part2, part1, vertex)
        
        # Legnagyobb gain csúcs kiválasztása
        max_gain_vertex = max(gains, key=gains.get)
        max_gain = gains[max_gain_vertex]

        # Csúcs mozgatása
        if max_gain_vertex in part1:
            part1.remove(max_gain_vertex)
            part2.add(max_gain_vertex)
        else:
            part2.remove(max_gain_vertex)
            part1.add(max_gain_vertex)
        
        locked.add(max_gain_vertex)

        # Cut size újraszámítása
        cut_size = sum(weight for v in part1 for neighbor, weight in graph[v] if neighbor in part2)
        if cut_size < best_cut_size:
            best_cut_size = cut_size
            best_part1, best_part2 = set(part1), set(part2)

    return best_part1, best_part2

# Példa gráf
graph = {
    'a': [('b', 1), ('c', 2)],
    'b': [('a', 1), ('d', 1)],
    'c': [('a', 2), ('d', 2)],
    'd': [('b', 1), ('c', 2)],
}

initial_part1 = ['a', 'b']

part1, part2 = fiduccia_mattheyses(graph, initial_part1)
print("Particiók:")
print("Part1:", part1)
print("Part2:", part2)

C++ Implementáció

Az alábbi C++ kód az FM-algoritmus alapjait illusztrálja: 

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;

struct Edge {
    int to, weight;
};

using Graph = unordered_map<int, vector<Edge>>;

int calculateGain(const Graph& graph, const unordered_set<int>& part1, const unordered_set<int>& part2, int vertex) {
    int E_from = 0, E_to = 0;
    for (const auto& edge : graph.at(vertex)) {
        if (part1.count(edge.to)) {
            E_from += edge.weight;
        } else if (part2.count(edge.to)) {
            E_to += edge.weight;
        }
    }
    return E_to - E_from;
}

pair<unordered_set<int>, unordered_set<int>> fiducciaMattheyses(const Graph& graph, unordered_set<int> initialPart1) {
    unordered_set<int> part1 = initialPart1;
    unordered_set<int> part2;
    for (const auto& [vertex, _] : graph) {
        if (!part1.count(vertex)) {
            part2.insert(vertex);
        }
    }

    unordered_set<int> locked;
    int bestCutSize = INT_MAX;
    unordered_set<int> bestPart1 = part1, bestPart2 = part2;

    while (locked.size() < graph.size()) {
        unordered_map<int, int> gains;
        for (int vertex : part1) {
            if (!locked.count(vertex)) {
                gains[vertex] = calculateGain(graph, part1, part2, vertex);
            }
        }
        for (int vertex : part2) {
            if (!locked.count(vertex)) {
                gains[vertex] = calculateGain(graph, part2, part1, vertex);
            }
        }

        int maxGainVertex = max_element(gains.begin(), gains.end(), [](auto& a, auto& b) {
            return a.second < b.second;
        })->first;

        if (part1.count(maxGainVertex)) {
            part1.erase(maxGainVertex);
            part2.insert(maxGainVertex);
        } else {
            part2.erase(maxGainVertex);
            part1.insert(maxGainVertex);
        }

        locked.insert(maxGainVertex);

        int cutSize = 0;
        for (int v : part1) {
            for (const auto& edge : graph.at(v)) {
                if (part2.count(edge.to)) {
                    cutSize += edge.weight;
                }
            }
        }

        if (cutSize < bestCutSize) {
            bestCutSize = cutSize;
            bestPart1 = part1;
            bestPart2 = part2;
        }
    }

    return {bestPart1, bestPart2};
}

int main() {
    Graph graph = {
        {1, {{2, 1}, {3, 2}}},
        {2, {{1, 1}, {4, 1}}},
        {3, {{1, 2}, {4, 2}}},
        {4, {{2, 1}, {3, 2}}}
    };

    unordered_set<int> initialPart1 = {1, 2};

    auto [part1, part2] = fiducciaMattheyses(graph, initialPart1);
    cout << "Part1: ";
    for (int v : part1) cout << v << " ";
    cout << "\nPart2: ";
    for (int v : part2) cout << v << " ";
    cout << endl;

    return 0;
}

Felhasználás

  • Elektronikai áramkörök tervezése: VLSI áramkörök optimalizálása.
  • Hálózatok particionálása: Nagy hálózatok hatékony feldolgozása.
  • Grafikai és térképezési problémák.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Fiduccia-Mattheyses-algoritmus&oldid=3480701”