This is a practical task for:
- AI subject, second semster.
- due to MON|18 May 2020.
find the shortest path as the start node is Arad and the end node is Bucharest.
Best-first search is a search algorithm which explores a graph by expanding the most promising node chosen according to a specified rule. A greedy algorithm is one that chooses the best-looking option at each step. Hence, greedy best-first search algorithm combines the features of both mentioned above. It is known to be moving towards the direction of the target, in each step. (PS: There is no visiting back in path, as it is Greedy)
Heuristic function
Greedy BFS uses heuristics to the pick the "best" node.
A heuristic is an approximate measure of how close you are to the target. In short, h can be any function at all. We will require only that h(n) = 0 if n is a goal. Properties of Heuristic functions
- relatively cheap to compute.
- relatively accurate estimator of the cost to reach a goal.
BFS v/s Greedy BFS
BFS expands the most promising node first(by looking at it's proximity to the source node).Hence, the solution is thorough. It might have to return back in path if a dead end is reached. Whereas, Greedy BFS uses heuristics to prioritize nodes closer to target. Hence, the solution is faster(but not necessarily optimal). There is no returning back in the path.
Often with large data sets, search algorithms could get computationally expensive with thorough approaches. Hence, we resort to approximation algorithms like Greedy BFS.
Greedy BFS Algorithm
Heuristic functions are clearly problem-specific.
Let us understand this better through an example.
Source: Artificial Intelligence A Modern Approach by Stuart J. Russell and Peter Norvig
Given here is the map of Romania with cities and distance between them. We need to find the shortest route from Arad to Bucharest.
The heurestics that we are using here is the straight-line distance from the city to the goal(Here, Bucharest). Note that, this straight line distance is obtained only by knowing the map coordinates of the 2 cities.
Input
Input is taken from the file
input.txt
Each line in the input is of the form
city1 city2 dist
It denotes each element of the adjacency list. That is, dist is the distance between city1 and city2. An undireced graph is drawn depicting the map of Romania. Starting city: Arad Goal city: Bucharest
Heuristics is loaded from the file
heuristics.txt
Each line is of the form
city h
'h' stands for the heuristics value(here, the straight line distnace) from the city 'city' to goal city(here, Bucharest) Working:
Starting from source city, we choose the next city which is the closest to the Goal city amongst all it's neighbours(based on the heuristics function). We terminate, once we've reached the goal city.
Here, Arad is the starting city. The first node to be expanded from Arad will be Sibiu, because it is closer to Bucharest than either Zerind or Timisoara. The next node to be expanded will be Fagaras, because it is closest. Fagaras in turn generates Bucharest, which is the goal.
Here, is the resultant graph. Green coloured node denotes the starting city(Here, Arad). Red coloured node denotes the goal city(Here, Bucharest). Edges marked with black is the route from Arad to Bucharest generated by the greedy bfs algorithm.
Complexity
Time: O(b^m) b - Branching factor, the average number of successors per state m - maximum depth of the search
BFS is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
It uses the opposite strategy as depth-first search, which instead explores the node branch as far as possible before being forced to backtrack and expand other nodes.
Algorithm
/* Breadth first search */
agenda = [initial state];
while agenda not empty do
pick node from front of agenda;
new nodes = apply operations to state;
if goal state in new nodes then
return solution;
else APPEND new nodes to END of agenda
Romanian Map
then,
then,
then,
and the output will look like:
Properties of BFS
- Advantage: guaranteed to reach a solution if one exists.
- Finds the shortest (cheapest) solution in terms of the number of operations applied to reach a solution.
- Disadvantage: time taken to reach solution.
- Let b be branching factor - average number of operations that may be performed from any level.
- If solution occurs at depth d, then we will look at b + b^2 + b^3 + · · · + bd nodes before reaching solution - exponential.
- The memory requirement is b^d
Complexity
Time for BFS assuming a branching factor of 10 and 1 million nodes expanded per second.