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:
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.
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 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.
Dodano: 24 kwietnia 2020 13:50, ostatnia edycja: 24 kwietnia 2020 18:28.
Przeszukiwanie wszerz (ang. breadth-first search, w skrócie BFS) – jeden z dwóch podstawowych algorytmów przeszukiwania grafu. Polega na przeglądaniu wierzchołków grafu według ich odległości od wierzchołka źródłowego (wyrażanej w liczbie krawędzi).
Problem komiwojażera (ang. travelling salesman problem, w skrócie TSP) – problem obliczeniowy polegający na poszukiwaniu w grafie takiego cyklu, który zawiera wszystkie wierzchołki (każdy dokładnie raz) i ma jak najmniejszy koszt. Bardziej formalnie, problem komiwojażera polega na poszukiwaniu w grafie cyklu Hammiltona o najmniejszej wadze.
Problem ma liczne zastosowania w życiu codziennym. Najlepszym przykładem jest praca kuriera, który musi wyjechać z magazynu, zawieźć przesyłki w różne miejsca i wrócić do magazynu.
Nie jest znany efektywny (tj. działający w czasie co najwyżej wielomianowym) algorytm dający gwarancję znalezienia optymalnego rozwiązania problemu komiwojażera. Problem ten jest bowiem zaliczany do klasy problemów NP-trudnych. W wersji decyzyjnej (czy istnieje cykl o długości mniejszej od x) problem jest zaliczany do klasy problemów NP-zupełnych. W grafie pełnym mającym n wierzchołków liczba możliwych cykli Hammiltona wynosi aż (n-1)!/2. W praktyce sprawdzenie wszystkich możliwości jest zatem wykonalne tylko dla niewielkiej liczby wierzchołków.
Zanieczyszczenie Giniego (ang. Gini Impurity) – miara niejednorodności danego zbioru wyrażająca się wzorem:
$$G = ∑↙{n} p_n (1-p_n),$$gdzie pn jest prawdopodobieństwem przynależności elementu do klasy n, czyli liczbą elementów danej klasy podzieloną przez liczbę elementów całego zbioru. Jeśli wszystkie elementy zbioru należą do tej samej klasy, zanieczyszczenie Giniego jest równe 0.
Zanieczyszczenia Giniego nie należy mylić ze współczynnikiem Giniego. Są to miary służące do wyrażania zupełnie innych rzeczy. Współczynnik Giniego określa nierównomierność rozkładu i jest wykorzystywany między innymi do liczbowego wyrażania nierówności w dochodach danego społeczeństwa.