Greedy technique and spanning tree.
GREEDY TECHNIQUE
Definition:
Greedy technique is a general algorithm design strategy, built on following elements:
• configurations: different choices, values to find
• objective function: some configurations to be either maximized or minimized
The method:
• Applicable to optimization problems ONLY
• Constructs a solution through a sequence of steps
• Each step expands a partially constructed solution so far, until a complete solution to the problem is reached.
On each step, the choice made must be
• Feasible: it has to satisfy the problem’s constraints
• Locally optimal: it has to be the best local choice among all feasible choices available on that step
• Irrevocable: Once made, it cannot be changed on subsequent steps of the algorithm
NOTE:
• Greedy method works best when applied to problems with the greedy-choice property
• A globally-optimal solution can always be found by a series of local improvements from a starting configuration.
Greedy method vs. Dynamic programming method:
• LIKE dynamic programming, greedy method solves optimization problems.
• LIKE dynamic programming, greedy method problems exhibit optimal substructure
• UNLIKE dynamic programming, greedy method problems exhibit the greedy choice property -avoids back-tracing.
Applications of the Greedy Strategy:
• Optimal solutions:
Change making
Minimum Spanning Tree (MST)
Single-source shortest paths
Huffman codes
• Approximations:
Traveling Salesman Problem (TSP)
Fractional Knapsack problem
Spanning Tree
Definition:
Spanning tree is a connected acyclic sub-graph (tree) of the given graph (G) that includes all of G’s vertices
Example: Consider the following graph
Minimum Spanning Tree (MST) Definition:
MST of a weighted, connected graph G is defined as: A spanning tree of G with minimum total weight.
Example: Consider the example of spanning tree:
For the given graph there are three possible spanning trees. Among them the spanning tree with the minimum weight 6 is the MST for the given graph
Question: Why can’t we use BRUTE FORCE method in constructing MST ?
Answer: If we use Brute force method-
• Exhaustive search approach has to be applied.
• Two serious obstacles faced:
1. The number of spanning trees grows exponentially with graph size.
2. Generating all spanning trees for the given graph is not easy.
MST Applications:
• Network design.
Telephone, electrical, hydraulic, TV cable, computer, road
• Approximation algorithms for NP-hard problems.
Traveling salesperson problem, Steiner tree
• Cluster analysis.
• Reducing data storage in sequencing amino acids in a protein
• Learning salient features for real-time face verification
• Auto config protocol for Ethernet bridging to avoid cycles in a network, etc
Comments
Post a Comment