The A* Algorithm (OCR A-Level Computer Science): Flashcards

📚Flashcards
Revision NotesModel AnswersQuizzesFlashcardsExam Questions
The A* Algorithm
Sign up to keep revising.Create a free account to study more flashcards and track your progress.

Practise the cards

12 cards from this deck

Show

What is the purpose of A*?

Finding shortest path from source to target node

What algorithm does A* enhance?

Dijkstra's algorithm

g(n)g(n) in A*

Cost from start node to current node

h(n)h(n) in A*

Heuristic estimate from current node to target

f(n)f(n) formula in A*

f(n)=g(n)+h(n)f(n) = g(n) + h(n)

Which node does A* select each step?

Node with lowest f(n)f(n) value

Manhattan Distance formula

h(n)=∣x1−x2∣+∣y1−y2∣h(n) = |x_1 - x_2| + |y_1 - y_2|

When to use Manhattan Distance

Grids with horizontal & vertical movement only

Euclidean Distance formula

h(n)=(x1−x2)2+(y1−y2)2h(n) = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}

Admissible heuristic property

Never overestimates the actual cost

Effect of overestimating heuristic

Algorithm may miss the shortest path

Which two algorithms does A* combine?

Dijkstra's & Greedy Best-First Search

Explore OCR A-Level Computer Science Revision Notes by Topics

Algorithms

Algorithms for the Main Data Structures

Explore OCR A-Level Computer Science Model Answers by Topics

Algorithms

Algorithms for the Main Data Structures

Explore OCR A-Level Computer Science Quizzes by Topics

Algorithms

Algorithms for the Main Data Structures

Explore OCR A-Level Computer Science Exam Questions by Topics

Algorithms

Algorithms for the Main Data Structures

Join 100,000+ A-Level students studying Flashcards with us.

Select your subjects, and get access to A+ resources today.