Path Finding Algorithm

Question 1

Where would you use a Path Finding Algorithm

Answer 1

• 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
• 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
• 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

Question 2

What is Dijkstra’s algorithm

Answer 2

An algorithm that finds the shortest path between two nodes in a weighted graph

Question 3

Describe the steps of Dijkstra’s Algorithm

Answer 3

• Starting from the root node, add the distances to all of the immediately neighbouring nodes to a priority queue. With all of the remaining nodes that cannot be reached their distance is denoted by ∞
• Create a table with the headings Node, From, Distance and Total Distance
• The node with the shortest Total distance is highlighted
• Now traverse all of the nodes connected to the new node and highlight the node with the shortest Total Distance
• Repeat until goal node is reached
• This time start from the nodes that have not been include and traverse them
• If the total distance is more than the total distance already recorded can be ruled out
• If the total distance is less the value can be updated to the new total distance
• Now you have the shortest distance path

Question 4

What is the A* Algorithm

Answer 4

• An alogirthm which is an improvement of Dijkstra’s algorithm and has two cost functions
• The first cost function is the actual cost between two nodes
• The second cost function is an approximate cost from node x to the final node. This is called a heuristic, and aims to make the shortest path finding process more efficient
• The approximate cost might be an estimate of the length between x and the final node, calculated using trigonometry.

Question 5

Describe the steps of the A* Algorithm

Answer 5

• Create a Table with the headings Node, From, Distance Heuristic and Total distance
• Here the heuristic cost is added onto the distance to calculate the total distance
• The route with the lowest total distance is selected to traverse further
  *