Ашкөздік оптимизациясында жиын жүйесі

Set system used in greedy optimization

In combinatorics, a greedoid is a type of set system. It arises from the notion of the matroid, which was originally introduced by Whitney in 1935 to study planar graphs and was later used by Edmonds to characterize a class of optimization problems that can be solved by greedy algorithms. Around 1980, Korte and Lovász introduced the greedoid to further generalize this characterization of greedy algorithms; hence the name greedoid. Besides mathematical optimization, greedoids have also been connected to graph theory, language theory, order theory, and other areas of mathematics.

Consider an undirected graph G. Let the ground set be the edges of G and the feasible sets be the edge set of each forest (i. e. subgraph containing no cycle) of G. This set system is called the cycle matroid. A set system is said to be a graphic matroid if it is the cycle matroid of some graph. (Originally cycle matroid was defined on circuits, or minimal dependent sets. Hence the name cycle.) Consider a finite, undirected graph G rooted at the vertex r. Let the ground set be the vertices of G and the feasible sets be the vertex subsets containing r that induce connected subgraphs of G. This is called the vertex search greedoid and is a kind of antimatroid. Consider a finite, directed graph D rooted at r. Let the ground set be the (directed) edges of D and the feasible sets be the edge sets of each directed subtree rooted at r with all edges pointing away from r. This is called the line search greedoid, or directed branching greedoid. It is an interval greedoid, but neither an antimatroid nor a matroid. Consider an m × n matrix M. Let the ground set E be the indices of the columns from 1 to n and the feasible sets be This is called the Gaussian elimination greedoid because this structure underlies the Gaussian elimination algorithm. It is a greedoid, but not an interval greedoid.

In general, a greedy algorithm is just an iterative process in which a locally best choice, usually an input of maximum weight, is chosen each round until all available choices have been exhausted. In order to describe a greedoid based condition in which a greedy algorithm is optimal (i. e., obtains a basis of maximum value), we need some more common terminologies in greedoid theory. Without loss of generality, we consider a greedoid 1=G = (F, E) with E finite. A subset X of E is rank feasible if the largest intersection of X with any feasible set has size equal to the rank of X. In a matroid, every subset of E is rank feasible. But the equality does not hold for greedoids in general. A function is R compatible if is rank feasible for all real numbers c.

An objective function is linear over a set if, for all we have for some weight function Proposition. A greedy algorithm is optimal for every R compatible linear objective function over a greedoid. The intuition behind this proposition is that, during the iterative process, each optimal exchange of minimum weight is made possible by the exchange property, and optimal results are obtainable from the feasible sets in the underlying greedoid. This result guarantees the optimality of many well known algorithms. For example, a minimum spanning tree of a weighted graph may be obtained using Kruskal's algorithm, which is a greedy algorithm for the cycle matroid. Prim's algorithm can be explained by taking the line search greedoid instead.