Ice Roads - Steiner Trees

Sometimes a small, seemingly insignificant, variation in the specification of a problem makes a huge difference in how difficult it is to solve. This activity, like the The Muddy City problem, is about finding short paths through networks. However, this activity allows for the introduction of new points into the network if it will reduce the path length. The result is a far more difficult problem that is not related to the Muddy City, but is algorithmically equivalent to the The Poor Cartographer and Tourist Town.

The resource begins with an introduction and a series of tasks followed by variations and extensions. The resource concludes with further information on Steiner trees and blank worksheets for use in the activities.

This collection of twenty activities from Computer Science Unplugged is designed to aid the teaching and learning of computer science through engaging games and puzzles using cards, string, crayons and lots of running around.

Show health and safety information

Please be aware that resources have been published on the website in the form that they were originally supplied. This means that procedures reflect general practice and standards applicable at the time resources were produced and cannot be assumed to be acceptable today. Website users are fully responsible for ensuring that any activity, including practical work, which they carry out is in accordance with current regulations related to health and safety and that an appropriate risk assessment has been carried out.

Downloads

Published by

Actions

Share this resource

Collections

This resource is part of Computer Science Unplugged

Lists that tag this content

Comments