A greedy algorithm aims to solve optimization problems by making the best local choice at each step. While this often leads to an optimal global solution, it’s not guaranteed in all cases. These algorithms are generally easier to implement and faster than other methods like Dynamic Programming but may not always yield the most accurate solution.

Key Features

1. Greedy-Choice Property: Each step aims for a local optimum with the expectation that this will lead to a global optimum.
2. Irreversibility: Once made, choices are not revisited.
3. Efficiency: Greedy algorithms are usually faster, particularly for problems that don’t require a globally optimal solution.

Example Algorithms

Fractional Knapsack Problem

Here, the goal is to maximize the value of items in a knapsack with a fixed capacity. The greedy strategy chooses items based on their value-to-weight ratio.

def fractional_knapsack(items, capacity):
    items.sort(key=lambda x: x[1]/x[0], reverse=True)
    max_value = 0
    knapsack = []
    for item in items:
        if item[0] <= capacity:
            knapsack.append(item)
            capacity -= item[0]
            max_value += item[1]
        else:
            fraction = capacity / item[0]
            knapsack.append((item[0] * fraction, item[1] * fraction))
            max_value += item[1] * fraction
            break
    return max_value, knapsack

items = [(10, 60), (20, 100), (30, 120)]
capacity = 50
print(fractional_knapsack(items, capacity))

Dijkstra’s Shortest Path

This algorithm finds the shortest path in a graph by selecting the vertex with the minimum distance at each step.

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)
        if current_distance > distances[current_node]:
            continue
        for neighbour, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbour]:
                distances[neighbour] = distance
                heapq.heappush(priority_queue, (distance, neighbour))
    return distances

graph = {'A': {'B': 1, 'C': 4},'B': {'A': 1, 'C': 2, 'D': 5},'C': {'A': 4, 'B': 2, 'D': 1},'D': {'B': 5, 'C': 1}}
print(dijkstra(graph, 'A'))

In summary, greedy algorithms offer a fast and intuitive approach to optimization problems, although they may sacrifice optimal solutions for speed.