Appendix B Greedy Algorithm and its Applications
Ali Kaveh · 2006
Greedy Algorithm and its ApplicationsIn this appendix, the Greedy Algorithm developed by Edmonds [41] for selecting an optimal base of a matroid is described.This is a powerful method for most combinatorial optimisation problems, and has found many applications in structural optimisation.Some applications of this algorithm in structural mechanics are briefly discussed. B.1 AXIOM SYSTEMS FOR A MATROIDA matroid may be defined in different interrelated forms, several of which were described in Whitney's original paper [230].Here the definitions in terms of the concepts of independence, bases and circuits are presented. DEFINITION IN TERMS OF INDEPENDENCEA matroid M is a set of elements S = {s 1 , s 2 , ..., s m } and a collection F of subsets of S (called independent sets) such that 7(I1) ∅ ∈ F , where ∅ is the empty set.Here, | X | and | Y | denote the cardinalities of the sets X and Y, respectively.