Now that we've covered the two most popular uninformed search algorithms (Breadth First (BFS) and Depth First search(DFS)), it's time for one more uninformed graph search algorithm: Uniform Cost Search (UCS). While BFS and DFS depend on nodes' positions for the order of expansion, UCS depends on nodes' cost for the order in which nodes get expanded.
UCS works by maintaining a priority queue of un-visited nodes that uses a cost/distance function g(n) to order the nodes inside the queue in an ascending order. Hence, each node has its own distinct cost/distance value that represents the distance from the source.
Assume a root node n with distance/cost 0, a goal node g, and a priority queue Q with only the root node in it.
From Q, start with the root node. Expand its children, and insert all un-visited child nodes to Q with each child node's distance/cost being the distance/cost of the parent node + the edge distance between the parent node and the child node. If a child node already exists in Q and the calculated distance is smaller than the distance recorded with the child node in Q, update the already existing node in Q with the new distance. Once all children nodes are expanded, from Q, get the node with the lowest distance/cost and repeat the children expansion until goal node g is encountered.
Below is a high level code for uniform cost search:
Uniform Cost Search
And here's the wrapper Node class to store a node's distance and value:
private class Node{
int distance;
int value;
private Node(int v){
this.value = v;
}
}
I have not implemented the getChildren() method but that should be easy to implement by traversing all the links a node has.
UCS works by maintaining a priority queue of un-visited nodes that uses a cost/distance function g(n) to order the nodes inside the queue in an ascending order. Hence, each node has its own distinct cost/distance value that represents the distance from the source.
Assume a root node n with distance/cost 0, a goal node g, and a priority queue Q with only the root node in it.
From Q, start with the root node. Expand its children, and insert all un-visited child nodes to Q with each child node's distance/cost being the distance/cost of the parent node + the edge distance between the parent node and the child node. If a child node already exists in Q and the calculated distance is smaller than the distance recorded with the child node in Q, update the already existing node in Q with the new distance. Once all children nodes are expanded, from Q, get the node with the lowest distance/cost and repeat the children expansion until goal node g is encountered.
Below is a high level code for uniform cost search:
Uniform Cost Search
public Node UniformCostSearch(Node root, Node goal ){
for (Node child: temp.getChildren()){
PriorityQueue<Node> q = new PriorityQueue<Node>();
q.insert(root);
while !q.isEmpty(){
Node temp = q.get(0);
if (temp.equals(goal)) return temp;
if q.contains(child){
if(q.get(child.value).distance > child.distance){
q.get(child.value).distance = child.distance;
}
}
else{
q.insert(child);
}
}
}
}
for (Node child: temp.getChildren()){
PriorityQueue<Node> q = new PriorityQueue<Node>();
q.insert(root);
while !q.isEmpty(){
Node temp = q.get(0);
if (temp.equals(goal)) return temp;
if q.contains(child){
if(q.get(child.value).distance > child.distance){
q.get(child.value).distance = child.distance;
}
}
else{
q.insert(child);
}
}
}
}
And here's the wrapper Node class to store a node's distance and value:
private class Node{
int distance;
int value;
private Node(int v){
this.value = v;
}
}
I have not implemented the getChildren() method but that should be easy to implement by traversing all the links a node has.
