Dijkstra and A*

Question 1

Dijkstra purpose

Answer 1

Finds the shortest path from one node to all others

Question 2

Dijkstra characteristics

Answer 2

Works with non negative weights

Needs graph, initial node, colection with visited nodes, collection of nodes to visit

Question 3

Dijkstra node info

Answer 3

costSoFar -> minimum cost from initial node to current node

bestParent -> node from wich we get the costSoFar

Question 4

Does dijkstra use an heuristic?

Answer 4

No

Question 5

Dijkstra performance

Answer 5

O(N*b)
b -> average number of connections per node

Version of algo to target
O(b^(1+(C/£))
C/£ -> expected depth of the solution

Question 6

A* evaluation function

Answer 6

F(n) = g(n) + h(n)
g(n) -> cost of the given solution so far
h(n) -> heuristic function - estimated best cost from n to the solution

Question 7

A* node info

Answer 7

costSoFar -> minimum cost from initial node to current node
bestParent -> node from wich we get the costSoFar
heuristic(targetNode) -> prediction of the cost from the node to the target node

Question 8

How does A* solve ties?

Answer 8

Depends on how we organize the open list

Question 9

How do we garantee that A* always finds the optimal path?

Answer 9

We can achieve that as long as the heuristic gives lower values that the true value

Question 10

What is a consistent heuristic? Does A* need to always use consistent heuristics to find the optimal path?

Answer 10

It defends that its always better to go straight to a node thatn to go around
No

Question 11

What is an admissible heuristic? Does A* need to always use admissible heuristics?

Answer 11

Heuristics that never overestimate the real remaining cost to reach the goal
No

Question 12

What is the main difference between Dijkstra and A*?

Answer 12

In A* we use an heuristic to predict the cost from the current node to the goal node

Question 13

Is there other algorithm that can expand fewer nodes and still ensure optimality than A*?

Answer 13

No

Question 14

When is it ok to use non-admissible heuristics?

Answer 14

When the heuristic error is low

Question 15

Why shold’t we use complex heuristic calculations?

Answer 15

Because it can easily dominate the pathfinding algorithm

Question 16

What is purpose of the partial path in A*?

Answer 16

To give an early current best path so that we can start moving earlier
We can resume the A* later if we sabe the current Open and Closed data structures