It is only for reviewing, not for learning.
-----------------------------------------------
-----------------------------------------------
Algorithm 1:
DIJKSTRA(G, w, s)
Greedy Algorithm
1: Overlapping subproblems
2: Optimal substructure
3: Greedy-choice property
-----------------------------------------------
-----------------------------------------------
----------------------------------------------
Cost:
---------------------------------------------
Notes:
1) DIJKSTRA is a type of BFS (Breadth-First-Search).
2) If each edge has the same cost, the algorithm can be improved by using FIFO queue instead of heap and get O(V+E).
Nature:
Smaller weights edge always pushed in the queue earlier. Or
v comes after u in Q implies that d[v] = d[u] or d[v] = d[u] + 1.
-----------------------------------------------
-----------------------------------------------
Algorithm 2: DFS
-----------------------------------------------
----------------------------------------------- Recursive Algorithm
DFS(Node) {
Color(Node);
Loop (n in Adjacent Nodes) {
DFS(n);
}
}
Non-Recursive Algorithm (Using LIFO Stack)
list nodes_to_visit = {root};
while( nodes_to_visit isn't empty ) {
currentnode = nodes_to_visit.first(); // nodes_to_visit is a LIFO stack
nodes_to_visit.prepend( currentnode.children );
//do something
}
-----------------------------------------------
-----------------------------------------------
Algorithm 3: BFS
-----------------------------------------------
-----------------------------------------------
Non-Recursive Algorithm (Using FIFO Queue)
list nodes_to_visit = {root};
while( nodes_to_visit isn't empty ) {
currentnode = nodes_to_visit.first(); // nodes_to_visit is a FIFO queue
nodes_to_visit.prepend( currentnode.children );
//do something
}
Recursive Algorithm // surprisingly, it is not that easy as DFS.
BFS(Queue) {
if(Queue is empty) return;
Queue.pop();
//do something
Queue.push(Children);
BFS(Queue);
}
-----------------------------------------------
-----------------------------------------------
Algorithm 4: A* Algorithm
-----------------------------------------------
-----------------------------------------------
1) DIJKSTRA uses local optimal in the greedy algorithm. However, local optimal is not a good enough choice in many many cases.
2) A* Algorithm uses estimated global optimal in the greedy algorithm.
How to estimate? That's the MAGIC.
It uses a knowledge-plus-
heuristic cost function of node
x (usually denoted
f(x)) to determine the order in which the search visits nodes in the tree.
The
h(x) part of the
f(x) function must be an
admissible heuristic; that is, it must not overestimate the distance to the goal.It is a very string requirement, since the true cost is unknown.
But it does exist in many cases. And,
h(x) part of the
f(x) function must be very near to the distance to the goal. Otherwise, it does not help much on the algorithm efficiency.
An example of an A star (A*) algorithm in action where nodes are cities
connected with roads and h(x) is the straight-line distance to target
point.
The contribution of A* Algorithm is that:
A* Algorithm gives a different type of algorithm design methodology, which can be used to make searching more efficient, if localized searching is much worse than optimal.
The
time complexity of A* depends on the heuristic. The big-O time complexity may be the same with DIJKSTRA. But the number of checking nodes can be much smaller.
DIJKSTRA Algorithm Search Space
A* Algorithm Search Space
