computer science//algorithms//greedy algorithm

A greedy algorithm is a procedure that builds its answer one choice at a time, always taking the option that looks best right now and never revisiting it, and it is the default way real systems assign robots to orders, echoes to tracks or sensors to locations when the answer is needed in milliseconds. It is the commonest heuristic: fast, simple to explain, and blind to what its choices do to the choices that follow (the token-by-token greedy decoding of a language model is the same idea applied to text).

A greedy algorithm is a procedure that builds its answer one choice at a time, always taking the option that looks best right now and never revisiting it, and it is the default way real systems assign robots to orders, echoes to tracks or sensors to locations when the answer is needed in milliseconds. It is the commonest heuristic: fast, simple to explain, and blind to what its choices do to the choices that follow (the token-by-token greedy decoding of a language model is the same idea applied to text).

Its weakness fits in a two-by-two table. Two robots, two orders; robot 1 can serve order A for 1 or order B for 2, robot 2 can serve A for 2 or B for 100. Greedy grabs the cheapest entry first, robot 1 to A for 1, and robot 2 is then forced onto B for 100: total 101. Crossing them costs 2+2=42+2=42+2=4. The first choice condemned the second, and nothing in the method looks for that. Scaled up, the gap between greedy and optimal can be arbitrarily large, and when it stays small it is because the costs happened to be similar.

In tracking the same failure swaps identities. Nearest-neighbour data association lets each track take its closest echo; when two aircraft cross, two tracks claim the same echo and can come out exchanged, which the global assignment problem solved exactly avoids.

Some problems make greedy safe. When the objective has diminishing returns (a submodular function, such as area covered by drones placed one by one), greedy selection is guaranteed at least 63% of the optimum; in weapon-target assignment the greedy marginal-return rule is optimal when all agents are identical.

Greedy is a good start even where it is weak. It gives a valid answer at once, and a local search can then improve it for as long as there is time, which makes the pair an anytime algorithm. Whether to go further is decided by measuring its gap to the optimum on cases small enough to solve exactly (flyswatter rule).