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

image

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

Popular posts from this blog

Data Structure Visualization:Introduction and Value of Data Structure Rendering

Binary Space Partitioning Trees:BSP Tree as a Hierarchy of Regions.

Drawing Trees:HV-Layout