159. OCR A Level (H446) SLR26 – 2.3 A star pathfinding revisited

What is a common misconception about the A* pathfinding algorithm?

• It requires manual input to continue after finding the goal vertex

• It stops as soon as the goal vertex is found

• It only works with negative edge weights

• It cannot find the most optimal route

Answer explanation

The common misconception about the A* pathfinding algorithm is that it stops as soon as the goal vertex is found, which is incorrect.

What must happen for a vertex to be considered 'visited' in the A* pathfinding algorithm?

• It must be the starting vertex

• All connected vertices must be visited first

• All its connected unvisited vertices must be considered

• It must be the goal vertex

Answer explanation

In the A* pathfinding algorithm, a vertex is considered 'visited' when all its connected unvisited vertices are considered for exploration.

How are the F values of vertices calculated in the A* pathfinding algorithm?

• G value + Heuristic

• G value - Heuristic

• Heuristic / G value

• G value * Heuristic

Answer explanation

The F values of vertices in the A* pathfinding algorithm are calculated by adding the G value (cost to reach the current vertex) and the Heuristic value (estimated cost from the current vertex to the goal).

What indicates that the A* pathfinding algorithm has found the most optimal route?

• When the F value of the goal vertex is zero

• When the algorithm runs out of vertices to visit

• When the goal vertex is marked as visited

• When all vertices have been visited

Answer explanation

The A* pathfinding algorithm has found the most optimal route when the goal vertex is marked as visited.

What is the purpose of using heuristics in the A* pathfinding algorithm?

• To randomly select the next vertex to visit

• To decrease the accuracy of the path found

• To increase the computation time

• To estimate the distance to the goal

Answer explanation

Heuristics are used in the A* pathfinding algorithm to estimate the distance to the goal, helping guide the search towards the most promising paths.

How does the A* algorithm differ from Dijkstra's algorithm?

• A* cannot handle negative edge weights

• Dijkstra's algorithm is faster than A*

• A* uses heuristics to be more efficient

• Dijkstra's algorithm does not find the shortest path

Answer explanation

A* uses heuristics to be more efficient

Under what circumstances does the A* pathfinding algorithm terminate?

• When it finds the shortest path to the goal

• When the goal vertex is marked as visited

• When all vertices have been visited

• When the algorithm runs out of memory

Answer explanation

The A* pathfinding algorithm terminates when the goal vertex is marked as visited, indicating that the shortest path to the goal has been found.

What data structure is used to represent a grid in pathfinding algorithms like A*?

• Queue

• Graph

• Tree

• Array

Answer explanation

In pathfinding algorithms like A*, a grid is represented using a Graph data structure to model the nodes and connections between them for efficient traversal and pathfinding.

What is the role of the G value in the A* pathfinding algorithm?

• It represents the heuristic estimate

• It is the distance from the start vertex

• It is the total cost of the path

• It is used to calculate the heuristic

Answer explanation

The G value in the A* pathfinding algorithm represents the distance from the start vertex, making it the correct choice.

What is an admissible heuristic in the context of the A* pathfinding algorithm?

• A heuristic that underestimates the cost to reach the goal

• A heuristic that randomly estimates the cost to reach the goal

• A heuristic that overestimates the cost to reach the goal

• A heuristic that accurately predicts the cost to reach the goal

Answer explanation

An admissible heuristic in the context of the A* pathfinding algorithm is one that underestimates the cost to reach the goal, allowing A* to find the optimal path efficiently.