Greedy Algorithm

A greedy algorithm makes the locally optimal choice at each decision point, selecting the option that appears best at that immediate moment without considering the broader, global problem context. This myopic approach is its defining feature.

• Example: In a shortest-path problem, a greedy approach might always move to the neighboring node with the smallest immediate edge cost, even if that path leads to a dead end or a longer overall route.
• Contrast: This differs from algorithms like Dijkstra's Algorithm, which maintains a global view of the shortest known distance to all nodes, guaranteeing an optimal final solution.

Choices made by a greedy algorithm are final and irrevocable. Once an option is selected, it is never reconsidered or undone, even if later information suggests it was suboptimal. The algorithm proceeds forward-only.

• Consequence: This characteristic makes greedy algorithms simple and fast, as they avoid the backtracking and state-space exploration seen in algorithms like depth-first search.
• Limitation: It also means they can become trapped by a poor early decision, preventing them from finding a globally optimal solution.

A problem must exhibit the greedy-choice property for a greedy algorithm to be optimal. This property states that a globally optimal solution can be assembled by consistently making locally optimal choices. It is a prerequisite for correctness.

• Formal Requirement: The property must be proven for the specific problem. Not all problems that seem amenable to a greedy approach actually satisfy it.
• Example: Huffman coding for data compression has this property; the optimal prefix code can be built by repeatedly merging the two least frequent symbols.

A problem suitable for a greedy solution must have optimal substructure. This means an optimal solution to the overall problem contains within it optimal solutions to its subproblems.

• Mechanism: This property allows the algorithm to build up a final solution incrementally. Solving each subproblem optimally (via the greedy choice) contributes directly to the global optimum.
• Shared Trait: This characteristic is also required for dynamic programming, but greedy algorithms use it in a more restrictive, one-pass manner without storing multiple subproblem solutions.

Greedy algorithms are typically computationally efficient and conceptually simple. They often run in polynomial time, frequently O(n log n) due to an initial sorting step, and have low memory overhead because they don't store multiple candidate solutions.

• Runtime: For the Activity Selection Problem, a greedy algorithm runs in O(n log n) time, dominated by sorting activities by finish time.
• Advantage: This makes them highly practical for real-time or large-scale applications, such as priority-based task scheduling in fleet orchestration, where quick, good-enough solutions are needed.

For NP-hard problems where finding an exact optimum is intractable, greedy algorithms often serve as effective approximation algorithms. They provide a provably near-optimal solution within a certain factor of the true optimum.

• Example: The greedy algorithm for the Set Cover Problem has an approximation ratio of ln n, where n is the size of the universe.
• Application: In Vehicle Routing Problems (VRP), greedy heuristics like "nearest neighbor" are used to quickly generate feasible initial routes that can later be refined by more complex metaheuristics.

Local search is a heuristic optimization method that starts from an initial solution and iteratively moves to a neighboring solution in the search space, aiming to improve an objective function. Unlike greedy algorithms that construct a solution from scratch, local search refines an existing solution. Key concepts include:

• Neighborhood: The set of solutions reachable by a small modification.
• Hill climbing: Moving to a better neighbor until a local optimum is found. It is widely used for NP-hard problems like the traveling salesman problem where greedy solutions serve as excellent starting points.