Wikiszótár

Cuthill-McKee-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈt͡suthilmt͡skɛɛɒlɡoritmuʃ]

Főnév

Cuthill-McKee-algoritmus

  1. (matematika)

Cuthill-McKee-algoritmus

A Cuthill-McKee-algoritmus egy gráf-alapú rendezési algoritmus, amelyet ritka mátrixok szerkezeti sávszélességének minimalizálására használnak. Az algoritmus célja a mátrix sorainak és oszlopainak újrarendezése oly módon, hogy a nem nulla elemek a mátrix átlójához közelebb kerüljenek, ezáltal csökkentve a mátrix sávszélességét.


Alkalmazások

  • Ritka mátrixok feldolgozása: Hálózatok, gráfok, és numerikus módszerek területén.
  • Iteratív megoldók optimalizálása: Az algoritmus a számítási költségek csökkentésére használható.


Definíciók

  1. Gráf:
    • Egy gráf a ritka mátrix nem nulla elemeinek elhelyezkedését modellezi.
    • A csúcsok megfelelnek a mátrix sorainak/oszlopainak, az élek pedig a nem nulla elemeket jelölik.
  2. Sávszélesség:
    • A mátrix sávszélessége a nem nulla elemek legnagyobb távolsága az átlótól: [ = (|i - j|), A[i][j] . ]
  3. Cél:
    • A sávszélesség minimalizálása.


Algoritmus lépései

  1. Kiindulási pont kiválasztása:
    • Kezdd egy véletlenszerűen választott csúccsal, vagy válaszd azt, amelyiknek a fokszáma a legkisebb.
  2. Szomszédos csúcsok rendezése:
    • Minden csúcs szomszédját rendezd a fokszámuk szerint növekvő sorrendbe.
  3. Iteráció:
    • Látogass meg minden csúcsot a rendezett listából, és ismételd meg az eljárást a még nem látogatott csúcsokkal.
  4. Rendezési lista előállítása:
    • Az algoritmus egy új sorszámozást generál, amely alapján a mátrix újrarendezhető.


Pszeudokód

CuthillMcKee(G):
    kezdet = válassz egy csúcsot minimális fokszámmal
    queue = üres sor
    látogatott = üres halmaz
    rendezés = []

    queue.push(kezdet)
    látogatott.add(kezdet)

    amíg queue nem üres:
        u = queue.pop()
        rendezés.append(u)
        
        szomszédok = G[u] szomszédai
        szomszédok.sort(fokszám szerint növekvő sorrendben)
        
        minden v szomszéd in szomszédok:
            ha v nincs látogatottban:
                látogatott.add(v)
                queue.push(v)

    térj vissza rendezés

Python implementáció

from collections import deque, defaultdict

def cuthill_mckee(graph):
    # Kezdeti csúcs választása minimális fokszám alapján
    start = min(graph.keys(), key=lambda x: len(graph[x]))
    
    # Kezdjük az algoritmust
    visited = set()
    queue = deque([start])
    ordering = []

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            ordering.append(node)

            # Szomszédok rendezése fokszám szerint növekvő sorrendben
            neighbors = sorted(graph[node], key=lambda x: len(graph[x]))
            for neighbor in neighbors:
                if neighbor not in visited:
                    queue.append(neighbor)

    return ordering

# Példa gráf reprezentáció
graph = {
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1, 3],
    3: [1, 2, 4],
    4: [3]
}

ordering = cuthill_mckee(graph)
print("Cuthill-McKee rendezés:", ordering)

Kimenet: 

Cuthill-McKee rendezés: [0, 1, 2, 3, 4]

C++ implementáció

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

using namespace std;

vector<int> cuthill_mckee(const unordered_map<int, vector<int>>& graph) {
    // Kezdeti csúcs választása minimális fokszám alapján
    int start = -1;
    int min_degree = INT_MAX;

    for (const auto& [node, neighbors] : graph) {
        if (neighbors.size() < min_degree) {
            min_degree = neighbors.size();
            start = node;
        }
    }

    // Algoritmus inicializálása
    unordered_set<int> visited;
    queue<int> q;
    vector<int> ordering;

    q.push(start);
    visited.insert(start);

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        ordering.push_back(node);

        vector<int> neighbors = graph.at(node);
        sort(neighbors.begin(), neighbors.end(), [&](int a, int b) {
            return graph.at(a).size() < graph.at(b).size();
        });

        for (int neighbor : neighbors) {
            if (visited.find(neighbor) == visited.end()) {
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }

    return ordering;
}

int main() {
    unordered_map<int, vector<int>> graph = {
        {0, {1, 2}},
        {1, {0, 2, 3}},
        {2, {0, 1, 3}},
        {3, {1, 2, 4}},
        {4, {3}}
    };

    vector<int> ordering = cuthill_mckee(graph);

    cout << "Cuthill-McKee rendezés: ";
    for (int node : ordering) {
        cout << node << " ";
    }
    cout << endl;

    return 0;
}

Kimenet: 

Cuthill-McKee rendezés: 0 1 2 3 4

Fordított Cuthill-McKee (RCM)

A Cuthill-McKee algoritmus eredményének megfordítása (azaz a sorrend visszafelé történő bejárása) gyakran tovább csökkenti a sávszélességet. Ehhez az algoritmus végén egyszerűen megfordítjuk az eredményt: 

ordering.reverse()
print("Fordított Cuthill-McKee rendezés:", ordering)

Összegzés

Előnyök:

  1. Egyszerű: Könnyen implementálható.
  2. Hatékony: A sávszélesség csökkentésében hatékony módszer.

Hátrányok:

  1. Nem optimális: Nem garantálja a minimális sávszélességet.
  2. Gráf reprezentáció: Nagy gráfoknál memóriaigényes lehet.

A Cuthill-McKee-algoritmus egyszerűsége és hatékonysága miatt népszerű numerikus matematikai alkalmazásokban, különösen ritka mátrixok optimalizálásában.

További információk

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