Mis on ahne algoritm ja millistel juhtudel seda…

Greedy algorithm is an approach to solving optimization problems that at each step chooses the best local solution (the most advantageous option at the current moment) in the hope that this sequence of optimal local solutions will lead to a globally optimal solution. It does not consider the possible consequences of the current choice on future steps.

Characteristics:

Simplicity: Usually easier to implement than dynamic programming or other optimization methods.
Speed: Often has lower computational complexity.
Optimality guarantee: Does not always guarantee finding a globally optimal solution. The guarantee applies only to certain classes of problems.

It is used in problems where it has been proven that a locally optimal choice at each step leads to a globally optimal solution. Examples:

Activity selection problem: Choosing the maximum number of non-overlapping activities in time.
Knapsack problem (when items can be divided): When items can be split. If not, it is a dynamic programming problem.
Prim and Kruskal algorithms: For finding the minimum spanning tree in a graph.
Dijkstra's algorithm: For finding the shortest path in a graph with non-negative edge weights.
Huffman coding: For constructing an optimal prefix code.

Example pseudocode for an activity selection algorithm:

Function SelectActivities(activities):
  Sort activities by finish time
  selected_activities = empty list
  last_finish_time = 0

  For each activity in activities:
    If activity.start_time >= last_finish_time:
      Add activity to selected_activities
      last_finish_time = activity.finish_time

  Return selected_activities

It is important to verify whether the greedy algorithm is applicable to the specific problem, as otherwise it may lead to a suboptimal solution.

# Simple example of a problem where the greedy algorithm is not optimal
# Coin change problem: to give the minimum number of coins
# Available coins: [1, 5, 10, 25] USD
# To give: for example, 30 cents

# Greedy algorithm:
# Take the largest coin <= 30 (25) -> remainder 5
# Take the largest coin <= 5 (5) -> remainder 0
# Result: 2 coins (25 + 5). This is optimal.

# Available coins: [1, 6, 10]
# To give: 12 cents

# Greedy algorithm:
# Take the largest coin <= 12 (10) -> remainder 2
# Take the largest coin <= 2 (1) -> remainder 1
# Take the largest coin <= 1 (1) -> remainder 0
# Result: 3 coins (10 + 1 + 1)
# Optimal solution: 2 coins (6 + 6)

# This example shows that the greedy algorithm does not always lead to a global optimum,
# if the problem's properties do not match its applicability (for example,
# standard currency denominations often allow greedy algorithms,
# but arbitrary denominations — no).

Mis on ahne algoritm ja millistel juhtudel seda kasutatakse?