teach-ict.com logo

THE education site for computer science and ICT

1. Introduction

An important class of algorithms in computer science deals with this question:

If there are a several ways to arrive at a goal, and there are choices to be made along the way, what are the best set of choices and how do we find that optimal solution?

This is called a path-finding problem and it happens in many fields. For example:

  • Navigation. What is the best path to get from A to B along a transport network
  • The internet. What is the most efficient route to get a packet of data to its destination
  • Speech recognition - a computer needs to parse a spoken command with many possibilities
  • Image recognition - being able to classify/recognise an image from a huge set of possibilities
  • Artificial Intelligence - training neural nets to work out an optimal strategy e.g playing chess
  • Robotics 2D - controlling their path from A to B
  • Robotics 3D - finding the optimal path for a robotic arm to move in 3D space
  • Gaming - path finding and NPC control in game worlds
  • Finance - help make optimal investment choices
  • Military - unmanned drones can use it to plan a route without external commands
  • Social network analysis - friendship networks, influencers, meme propagation

For this syllabus, two popular algorithms will be covered namely the Dijkstra's algorithm and the A* algorithm