Matroid

Własność wymiany (1) Własność wymiany: biorąc dwa zbiory niezależne o różnej liczbie elementów jesteśmy w stanie dodać do mniejszego z nich taki element z większego, że otrzymany zbiór także będzie należał do rodziny zbiorów niezależnych. W tym przypadku zbiorami niezależnymi są lasy rozpinające
Matroid MST (2) Reprezentacja problemu minimalnego drzewa rozpinającego za pomocą matroidu (kliknij ilustrację, aby powiększyć)
Własność wymiany niespełniona (3) Przykład niespełnionej własności wymiany przy próbie przedstawiania problemu komiwojażera za pomocą matroidu. Zbiory 3 i 4 są podzbiorami poprawnych rozwiązań, więc musiałyby być zbiorami niezależnymi. Nie da się jednak do zbioru 3 dodać elementu zbioru 4 w taki sposób, aby uzyskać inny zbiór niezależny

Matroid – struktura matematyczna składająca się z niepustego zbioru elementów E i takiej rodziny jego podzbiorów I, że spełnione są następujące warunki:

  1. Jeśli jakiś zbiór należy do I, to wszystkie jego podzbiory także należą do I.
  2. Jeśli weźmiemy dowolne dwa zbiory należące do I o różnej liczbie elementów, to jesteśmy w stanie dodać do mniejszego z nich taki element z większego (spośród tych, które nie należą do mniejszego), że utworzony w ten sposób zbiór także będzie należał do I.

Drugi warunek, zwany własnością wymiany, formalnie może być zapisany jako:

$$⋀↙{A,B∊I}↙{ |A|>|B| }⋁↙{t∊(A-B)} B∪\{t\} ∈ I$$

Co istotne, rodzina zbiorów I nie musi zawierać wszystkich możliwych podzbiorów zbioru E. Ważne tylko, aby była spełniona własność wymiany. Przykładowo, dla E={a,b,c,d} prawidłową rodziną I, może być zarówno { {a,b}, {b,c}, {a}, {b}, {c}, ∅}, jak i { {a}, {b}, {c}, {d}, ∅}. Trywialnym przypadkiem poprawnego matroidu jest taki, w którym rodzina I zawiera jedynie zbiór pusty.

Wybrane pojęcia

Zbiory należące do I określane są jako zbiory niezależne. Zbiór niezależny o największej liczbie elementów to baza matroidu. Matroid może mieć wiele baz. W pierwszym wspomnianym wcześniej przykładzie bazami są zbiory {a,b} i {b,c}, w drugim zaś zbiory {a}, {b}, {c}, {d}.

Jeśli każdy element zbioru E ma przyporządkowaną dodatnią liczbę (wagę), to taki matroid jest określany jako matroid ważony. Każdemu zbiorowi niezależnemu również można wtedy przyporządkować wagę, będącą sumą wag wszystkich należących do niego elementów. Dla matroidów grafowych (tzn. takich, w których elementy zbioru E są krawędziami grafu), wagą może być długość krawędzi.

Więcej pojęć związanych z matroidami można znaleźć w książce [1].

Matroidy a algorytmy zachłanne

Matroidy ważone mają duże zastosowanie przy ocenie skuteczności algorytmów zachłannych. Udowodniono, że jeśli problem obliczeniowy da się przedstawić za pomocą matroidu ważonego, to algorytm zachłanny zawsze zwróci rozwiązanie optymalne (dowód jest dostępny w książce [2]). W takim przypadku, jeśli do naszego rozwiązania będziemy zawsze dodawać ten spośród dostępnych elementów zbioru E, który ma największą wagę, to otrzymamy bazę matroidu o największej wadze spośród wszystkich baz. Przykładem takiego algorytmu jest algorytm Kruskala.

Bibliografia

  • R.J. Wilson, Wprowadzenie do teorii grafów, Wydawnictwo Naukowe PWN, Warszawa, 2012, ISBN 9788301150662.
  • T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, Warszawa, 2012, ISBN 9788301169114.
Ocena: -1 Tak Nie
Liczba głosów: 1.

Dodano: 24 kwietnia 2020 13:50, ostatnia edycja: 24 kwietnia 2020 18:28.

REKLAMA

Zobacz też

Metoda Otsu – algorytm służący do binaryzacji obrazu, czyli przekształcenia obrazu w odcieniach szarości do obrazu binarnego. Metoda ta realizuje progowanie globalne – dla całego obrazu wyznaczany jest jeden próg jasności, a następnie wszystkim pikselom jaśniejszym od tego progu przypisywana jest jedna wartość, a ciemniejszym druga.

Algorytm jest oparty na analizie histogramu. Przygotowanie histogramu polega na zliczeniu pikseli w każdym możliwym odcieniu (zazwyczaj liczba odcieni wynosi 256, gdyż tyle da się zakodować w jednym bajcie). Następnie należy sprawdzić każdy możliwy próg jasności i wybrać ten, dla którego wariancja międzyklasowa jest największa (lub suma ważona wariancji wewnątrzklasowych jest najmniejsza).

Jeśli obrazem wejściowym jest obraz kolorowy, można go łatwo sprowadzić do odcieni szarości. W przypadku kolorów zakodowanych w RGB najprostszym rozwiązaniem jest uśrednienie dla każdego piksela wartości wszystkich trzech kanałów.

→ Czytaj całość

Rekurencja (inaczej rekursja) – odwołanie się funkcji lub definicji do samej siebie. Mówiąc inaczej, podejście rekurencyjne polega na tym, że rozwiązanie problemu wyraża się za pomocą rozwiązania tego samego problemu dla mniejszych danych wejściowych. Stosowanie rekurencji jest charakterystyczne dla algorytmów projektowanych metodą dziel i zwyciężaj.

Typowym problemem, dla którego można zastosować rekurencję, jest obliczanie silni. Przypomnijmy, że silnia z n jest zdefiniowana jako n!=1×2×…×n. Funkcja ta może być równoważnie zapisana jako:

n!=(n−1)!×n, dla n>0,
n!=1, dla n=0.

W powyższym przykładzie górny wiersz jest ogólnym równaniem rekurencji, zaś dolny wiersz jest wartością brzegową. W języku C++ powyższa funkcja byłaby zapisana w poniższy sposób.

int silnia(int n)
{
    if (n > 0)
    {
        return n * silnia(n-1);
    }
    else
    {
        return 1;
    }
};

Przekształcenie postaci rekurencyjnej funkcji do postaci zwartej (tzn. takiej, która nie zawiera odwołania do samej siebie) jest określane jako rozwiązanie rekurencji. Metody rozwiązywania rekurencji są dostępne między innymi w książkach podanych w bibliografii.

Algorytmy stosujące rekurencję są zazwyczaj proste w implementacji. Jednocześnie wiążą się one z pewnymi problemami. Przy podejściu rekurencyjnym ta sama funkcja jest wywoływana wielokrotnie, co zużywa pamięć operacyjną (w skrajnych przypadkach może to spowodować przepełnienie stosu).

→ Czytaj całość

Algorytm Johnsona – algorytm służący do wyznaczania najkrótszych ścieżek pomiędzy każdą parą wierzchołków w grafie. Algorytm wykorzystuje algorytm Dijkstry i algorytm Bellmana-Forda. Dopuszcza krawędzie o ujemnych wagach, o ile nie tworzą ujemnych cykli.

Złożoność czasowa algorytmu (jeśli algorytm Dijkstry zostanie zaimplementowany z wykorzystaniem kopca Fibonacciego) to O(n2log n + en), gdzie n jest liczbą wierzchołków, a e jest liczbą krawędzi. Dla grafów rzadkich (ze stosunkowo małą liczbą krawędzi) jest to złożoność lepsza, niż złożoność algorytmu Floyda-Warshalla.

→ Czytaj całość
Polityka prywatnościKontakt