Path Finding Algorithm Flashcards
1
Q
Where would you use a Path Finding Algorithm
A
- 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
2
Q
What is Dijkstra’s algorithm
A
An algorithm that finds the shortest path between two nodes in a weighted graph
3
Q
Describe the steps of Dijkstra’s Algorithm
A
- 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
4
Q
What is the A* Algorithm
A
- 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.
5
Q
Describe the steps of the A* Algorithm
A
- 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
*
