Preview

03 - A* algorithm

 1. In computer science, A* (pronounced "A star") is a computer algorithm that is widely used in pathfinding and ______________________

  binary tree creation

  graph traversal

  hash table traversal

  reversal of Dijkstra's algorithm

 2. A* was created as part of the Shakey project, which had the aim of building a ___________________ that could plan its own actions
shakey1.jpg

  moon based automobile

  virtual prototype of a portable television

  air-based drone camera

  mobile robot

 3. The A* search algorithm enjoys widespread use and popularity due to its performance and accuracy.

  TRUE

  FALSE

 4. Which of the following statements is more likely to be accurate?
Option #1
==========
The A* algorithm is entirely different from Dijkstra's algorithm. It uses
heuristics but is incredibly inaccurate as a result. It does not work well
with graph data structures.


Option #2
==========
The A* algorithm can be seen as an extension of Edsger Dijkstra's 1959 algorithm. 
A* achieves better performance by using heuristics to guide its search

  Neither Option bears any resemblance to the truth

  Both Options are correct

  Option 1

  Option 2

 5. A* is an ________________________, meaning that it is formulated in terms of weighted graphs: starting from a specific starting node of a graph, it aims to find a path to the given goal node having the smallest cost

  informed search algorithm, or a best-first search

  uninformed search algorithm, or a worst-case search

  uninformed search algorithm, or a depth first search

  informed search algorithm, or an automated sort

 6. At each iteration of its main loop, A* needs to determine ___________________________

  which of its paths to backtrack upon

   which of its paths to extend

  which of its heuristics to add to the cost of the last node

  which of its nodes to delete

 7. Specifically, A* selects the path that minimizes the following equation, where n is the next node on the path, g(n) is the cost of the path from the start node to n, and h(n) is _________________
f(n)=g(n)+h(n)

  a heuristic function that calculates the cost of the cheapest path with n x 2 accuracy

  a heuristic function that estimates the cost of the cheapest path from n to the goal

  a heuristic function that is randomly generated (numbers between 1 and 10,0000)

  a heuristic function that accurately sums up the costs to derive the total distance

 8. Suppose we were trying to get from the bottom highlighted node to the node highlighted at the top. Why would we be likely to go to the node that has a heuristic of 10 first?
the_use_of_heuristics.png

  Because the process is randomised and the h value is calculated based on the relative square roots of a random number

  Because the A* algorithm will go to any node that is diagnol or above it, as opposed to a node that is below or to the left.

  Because the A* algorithm will use the node that has the lowest heuristc and the other nodes have higher h values than 10

  Actually, it would not go to this node first, but to the node with the h value of 14

 9. A* terminates when the path it chooses to extend is a path from start to goal or if _______________________________

  there are multiple paths and therefore too many options eligible to be extended

  the path it chooses to extend is equal to infinity

  the path it chooses to extend can be solved with Dijkstra's algorithm instead

  there are no paths eligible to be extended.

 10. Typical implementations of A* use a _______________________ to perform the repeated selection of minimum (estimated) cost nodes to expand

  tree or graph based data structure

  stack data structure

  cost or weighted edge

  priority queue

 11. At each step of the algorithm, the node with the ______ f(x) value is removed from the queue, the f and g values of its neighbors are updated accordingly, and these neighbors are added to the queue

  lowest

  equivalent to (e.g. ==)

  highest

  top-most

 12. The algorithm continues until a goal node has a lower f value than any node in the queue (or _______________________).

  until the queue is empty

  until a f value exceeds the current node's cost

  until the current node is equal to the last node

  until the queue is full again

 13. Like breadth-first search, A* is considered 'complete' and will always find a solution if one exists provided

  TRUE

  FALSE

 14. Dijkstra's algorithm is similar to the A* algorithm in that it makes guesses (uses heurisitcs) as to which is the best path to the target

  FALSE

  TRUE

 15. Which of the following statements is more likely to be accurate?
Option #1
==========
A-star follows the Dijkstra algorithm but also includes includes a heuristic h(n) 
that biases the search towards the target. This can lead to an answer/solution that
is derived quicker.


Option #2
==========
A-star follows the Dijkstra algorithm but also includes includes a heuristic h(n) 
that often will lead a search away from target, thus taking a longer time but
arriving at a more accurate solution.

  Both Options are correct

  Neither Option bears any resemblance to the truth

  Option 1

  Option 2

 16. Calulating the horizontal and vertical distance of each of the starting node's neighbour from the final node is sometimes called the _____________________

  Right angle heuristic

  PI heuristic

  Green heuristic

  Manhattan heuristic

 17. Another heurisitic might be to _____________________________, this is sometimes called the Euclidean heuristic

  calculate the square of the hypotenuse distance using alebtraic formulas

  calculate the square root of the value of PI

  calculate the hypotenuse distance using Pythagoras

  calculate the square root of the total diagnol length of each single node

 18. Which of the following statements is more likely to be accurate?
Statment 1
===========
The best case performance of the A* algorithm depends on the 
quality of the graph data structure used. 
A good one will however, never perform better than Dijkstra

Statment 2
===========
The worst case performance of the A* algorithm depends on the 
quality of the heurisitc used. Dijstra's algorithm will always,
in all cases, perform better.

Statment 3
===========
The worst case performance of the A* algorithm depends on the 
quality of the heurisitc used.
A good one will perform better than Dikstra

  Statement 1 and 3 are both accurate

  Statement 2

  Statement 3

  Statement 1

 19. The total cost of getting from the present node to the target is _______________________ where g is the same one as the Dijkstra algorithm

  g = h/2 + f

  f = g + h

  f = (g / 2) + h

  g = f + h

 20. In the following pseudocode, if line is TRUE, it suggests that:
calculate the present_cost of neighbour with f=g+h
	IF present_cost of neighbour < stored_cost of neighbour
		set current as parent of neighbour (# the path is building up)

  it is likely to be a better path

  It is likely to cause the algorithm to go back to the beginning (i.e. to the parent node)

  it is likely to be a worse path

  it is likely to be a dead end