# 03 - A* algorithm

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

reversal of Dijkstra's algorithm

graph traversal

binary tree creation

hash table traversal

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

moon based automobile

virtual prototype of a portable television

air-based drone camera

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```

Option 2

Neither Option bears any resemblance to the truth

Both Options are correct

Option 1

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

uninformed search algorithm, or a depth first search

informed search algorithm, or a best-first search

informed search algorithm, or an automated sort

uninformed search algorithm, or a worst-case search

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

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

which of its nodes to delete

which of its paths to extend

which of its paths to backtrack upon

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 estimates the cost of the cheapest path from n to the goal

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

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

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

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? 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

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

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

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 multiple paths and therefore too many options eligible to be extended

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

cost or weighted edge

stack data structure

priority queue

tree or graph based data structure

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

equivalent to (e.g. ==)

highest

top-most

lowest

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

until the current node is equal to the last node

until the queue is full again

until the queue is empty

until a f value exceeds the current node's cost

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

TRUE

FALSE

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.```

Neither Option bears any resemblance to the truth

Option 1

Option 2

Both Options are correct

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

Green heuristic

Manhattan heuristic

PI heuristic

Right angle heuristic

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

calculate the hypotenuse distance using Pythagoras

calculate the square of the hypotenuse distance using alebtraic formulas

calculate the square root of the value of PI

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 1

Statement 3

Statement 2

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

f = g + h

g = f + h

f = (g / 2) + h

g = h/2 + f

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 worse path

it is likely to be a better path

it is likely to be a dead end

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