How deeply does Grokking Algorithms, Second Edition cover optimal solution?

Explains exhaustive enumeration, local-versus-global choices, and unused capacity, but stops short of detailing the complete exact algorithm.

Optimal solution

As explained in Grokking Algorithms, Second Edition

An optimal solution is a feasible solution that achieves the best possible objective value for an optimization problem.

Imagine filling a 35-pound knapsack. An optimal solution is a feasible choice of items that produces the highest possible value. Choosing the most expensive item first may look sensible, but the stereo earns $3,000 while the laptop and guitar together earn $3,500. section 10.2

The difference is between a merely good or approximate result and the best possible result. Trying every possible set can find the optimum, but the number of sets doubles with each added item, making this approach impractical for large inputs. section 11.2

When a local choice is globally optimal

For classroom scheduling, repeatedly choosing the class that ends soonest produces three compatible classes. Here, each locally optimal choice leads to the globally optimal schedule. section 10.1

Use these questions to distinguish optimal solutions from attractive shortcuts:

Does the solution maximize the objective, or is it only close to the maximum? section 10.2 section 11.2
Must the container be filled completely? No: a valuable diamond can leave unused capacity and still belong to the optimal set. section 11.13

How Grokking Algorithms, Second Edition covers it

Cover of Grokking Algorithms, Second Edition

liveBook manning.com

Read Grokking Algorithms, Second Edition on liveBook Get the book at manning.com

Also explained in

liveBook manning.com

Grokking AI Algorithms, Second EditionAn optimal solution is a solution that performs best according to the criterion used to evaluate solutions to a problem.
liveBook manning.com

Statistics Every Programmer NeedsAn optimal solution is a feasible assignment of decision variables that gives the best objective value under the problem's optimization direction.

Compare how 3 books explain optimal solution →

Related concepts

optimizationproduced by · Optimization is the systematic selection or adjustment of values, actions, or system designs to improve a specified objective, often subject to constraints.
particle swarm optimizationproduced by · Particle swarm optimization is a population-based optimization method in which candidate solutions adjust their positions using individual and collective search information.
stagnationused by · Stagnation is a search condition in which successive iterations or generations produce little or no meaningful improvement toward a better solution.
greedy algorithmcontrasts with · A greedy algorithm builds a solution incrementally by choosing the locally best available option at each step, without generally accounting for all future consequences or revising prior choices.
feasible solutionkind of · A feasible solution is an assignment of decision-variable values that satisfies all specified constraints and bounds.
backtrackingproduced by · Backtracking is a technique that returns to earlier decisions or states along a path to reconsider choices, explore alternatives, or reconstruct a solution.

This explainer was generated by Manning's knowledge graph from the text of Grokking Algorithms, Second Edition. The section links point to the parts of the book it draws on.