B8 · Computational Thinking and the AI Project Cycle

Optimisation: Finding the Best Solution

Optimisation means finding the best possible solution to a problem from all the possible ones, according to a clear goal and within limits. The goal might be the shortest time, the lowest cost or the fewest mistakes; the limits, called constraints, are rules the solution must obey.

8 min Beginner Jump to the activity

What you need: Nothing. This page starts from the beginning, with no programming and no formulas.

Definition

A delivery rider has ten parcels to drop across the city. There are more than three million possible orders to visit them in. Which one is fastest?

Optimisation means finding the best possible solution to a problem from all the possible ones, according to a clear goal and within limits. The goal might be the shortest time, the lowest cost or the fewest mistakes; the limits, called constraints, are rules the solution must obey.

In simple words

Packing a school bag is optimisation. You want everything you need for the day (the goal), the bag can only hold so much and must not be too heavy (the constraints), so you choose the best combination of books, tiffin and water bottle.

Why it matters

Optimisation is everywhere: routes, timetables, factory schedules, electricity grids and train networks. It is also how AI learns: training a model means searching for the settings that make the fewest mistakes.

Key terms

Optimisation
Finding the best solution according to a goal and within limits.
Objective
What you are trying to make as small or as large as possible, such as travel time or profit.
Constraint
A rule the solution must obey, such as a budget or a deadline.
Trade-off
Giving up some of one thing to get more of another, such as speed for cost.
Greedy approach
Taking the best-looking choice at each step, which is fast but not always best overall.
Good-enough solution
A solution that is close to the best and can be found quickly, when the perfect one would take too long.

Explained in detail

Goal, constraints and options

Every optimisation problem has three parts. The options are all the possible solutions: every order the rider could visit the parcels in. The objective is the measure of how good an option is: total travel time. The constraints are the rules: a parcel promised by 11 a.m. must arrive before then, and the bike has room for only six parcels at once. The best solution is the option that scores best on the objective while obeying every constraint.

Why trying everything does not work

With 3 parcels there are only 6 possible orders, easy to check by hand. With 10 there are over 3.6 million. With 20 there are more than two billion billion, and even the fastest computer could not check them all in a lifetime. This explosion is why clever methods are needed. Some cut out options that clearly cannot be best; others build a good solution step by step; others start with any solution and keep making small improvements.

The greedy approach

A simple method is to always go to the nearest parcel next. This greedy approach is fast and usually gives a reasonable route, but not always the best one: going to the nearest place first can leave you with a long trip back at the end. Greedy methods are useful when a good-enough answer is needed quickly, such as for a delivery app planning thousands of routes every minute.

Trade-offs

SituationWhat you gainWhat you give up
Taking the toll highwayTimeMoney
Buying in bulkLower price per itemStorage space and cash now
A bigger AI modelAccuracySpeed, cost and energy
A stricter spam filterLess spamMore real emails wrongly blocked

Optimisation inside AI

Training a machine learning model is an optimisation problem. The options are all the possible settings of the model; the objective is to make as few mistakes as possible on the training examples. The usual method is like walking down a hill in thick fog: you cannot see the bottom, but you can feel which way slopes downward under your feet, take a small step that way, and repeat. Step by step, the mistakes get smaller. This method is called gradient descent, and you will learn more about it in later levels.

How it works

  1. State the objective: what should be as small or as large as possible?
  2. List the constraints the solution must obey.
  3. List or describe the possible options.
  4. If there are few, compare them all; if many, use a method such as greedy or step-by-step improvement.
  5. Check the trade-offs and whether a good-enough answer will do.

Try it yourself

Greedy is not always best

Ravi delivers three parcels, starting and ending at the shop. Places are on one straight road: A is 1 km left, B is 2 km right, C is 6 km right.

Pack the best picnic basket

Your basket holds 5 kg. Each item has a weight and a fun score.

  1. Items: water 2 kg (score 9), sandwiches 1 kg (8), cricket set 3 kg (10), fruit 1 kg (6), board game 2 kg (5).
  2. Find a combination that stays within 5 kg.
  3. Add up its fun score.
  4. Try at least three combinations and keep the best.

Think about it

  • What was the objective, and what was the constraint?
  • Did choosing the highest-score item first always give the best basket?

Common mistakes

  • Not stating the goal clearly before searching for the best answer.
  • Ignoring constraints, so the "best" answer is impossible.
  • Assuming the first or greedy answer must be the best.

Check yourself

Question 1

1. What is a constraint?

Question 2

2. Why can't a computer check every route for 20 delivery stops?

Question 3

3. How is training an AI model an optimisation problem?

Summary

  • Optimisation finds the best option for a goal within constraints.
  • When options explode, use smart methods and accept good-enough answers.
  • AI training is optimisation: step by step towards fewer mistakes.

Finished reading?

Sources: Elements of AI (University of Helsinki) · CS Unplugged