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

📚Quizzes
Revision NotesModel AnswersQuizzesFlashcardsExam Questions
The A* Algorithm
Sign up to keep practising.Create a free account to play more quizzes and track your progress.

Practise the questions

12 questions from this quiz

Show

What does the A* algorithm find between a source and target node?

The shortest path

In A*, what does the formula f(n)=g(n)+h(n)f(n) = g(n) + h(n) represent?

The total estimated cost

What does g(n)g(n) represent in the A* algorithm?

Cost from start to current node

What does h(n)h(n) represent in the A* algorithm?

Heuristic estimate to target

Which node does A* select from the open set to evaluate next?

Node with lowest f(n)f(n)

When is Manhattan Distance used as a heuristic in A*?

For horizontal and vertical only

What is the formula for Euclidean Distance in A*?

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

What does it mean for a heuristic to be admissible?

It never overestimates cost

In the example, what is the total cost of the shortest path A → B → D → E?

8

What two algorithms does A* combine aspects of?

Dijkstra's and Greedy Best-First

What problem can occur if a non-admissible heuristic is used?

May miss the shortest path

What is the purpose of the cameFrom map in A*?

Reconstruct the path

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 Flashcards 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 Quizzes with us.

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