computer science//algorithms

An algorithm is a finite, step-by-step procedure that turns an input into an output, and the part of computer science that studies algorithms asks two things of each one: whether its answer is right, and what it costs in time and memory as the input grows. For an engineer the second question usually decides. A planner, a task dispatcher or a tracker runs inside a loop with a period, and an answer that arrives after the period has passed belongs to a world that no longer exists.

An algorithm is a finite, step-by-step procedure that turns an input into an output, and the part of computer science that studies algorithms asks two things of each one: whether its answer is right, and what it costs in time and memory as the input grows. For an engineer the second question usually decides. A planner, a task dispatcher or a tracker runs inside a loop with a period, and an answer that arrives after the period has passed belongs to a world that no longer exists.

The family gathered here is the one a machine uses at decision time: finding a route, choosing who does what, picking the next move. Its members differ in the guarantee they give and the price of that guarantee. Graph search finds least-cost paths through a graph of states, either blind and exhaustive (Dijkstra's algorithm) or guided by an estimate of the remaining cost (A* search). A heuristic is a rule that answers fast without promising the best, and the greedy algorithm is the commonest one, taking the best-looking option at each step. Local search improves an existing solution by small changes, Monte Carlo tree search explores the future by sampling it, and an anytime algorithm (several of the above can be run as one) always holds a valid answer and improves it while it is given time.

A good answer on time beats an optimal answer late.

The cost that matters in a loop is the worst case within the period, so a method with a bounded, predictable run time and a decent answer often wins over an exact one whose run time explodes on the rare hard input.

Worst-case and typical cost are different numbers. Complexity theory classifies problems by the worst case, and an NP-hard problem has no known algorithm that guarantees the optimum in polynomial time; yet solvers find exact answers to many real instances of such problems in seconds. What decides is the size of the instance and the time budget.

When the choice is among discrete options whose number explodes, the problem belongs to combinatorial optimization, which supplies the exact methods (assignment solvers, branch and bound, integer programming) that these fast methods are measured against.

The honest way to choose is the flyswatter rule: implement the simple rule, measure in simulation how far it falls from the optimum, and pay for a heavier algorithm only if that gap matters.