AI Assignment 2: Greedy Best First Search Algorithm Solution

This assignment solution demonstrates the application of the greedy best first search algorithm to find the shortest path between Malaga and Valladolid among 50 cities in Spain. The solution includes MATLAB code that implements the greedy algorithm, which iteratively selects the next city based on the minimum distance. The output of the code provides the path taken and the total path cost. The document further explains the greedy best first search algorithm, including the f(n) function, and contrasts it with the A* search algorithm, highlighting their differences in path cost evaluation and completeness. The A* algorithm uses both path cost and heuristic estimates, ensuring it finds the optimal solution, unlike the greedy algorithm.

Running head: ASSIGNMENT 2
ASSIGNMENT 2
Name of the Student
Name of the University
Author Note

1ASSIGNMENT 2
Problem introduction:
In this particular assignment the greedy best first search method is applied to find the distance
between the cities MALAGA and VALLADOLID among the 50 cities in Spain. The greedy
algorithm works in the following way. The query starts from MALAGA and the cities that
are adjacent to it is found and their corresponding distances. Then the next city is obtained by
finding the minimum of those distances. This process follows until the goal city is reached.
Now, this algorithm does not always finds a path from source to goal as the minimum
distances not always lead to goal. Hence, the greedy algorithm is incomplete and not optimal.
MATLAB code for greedy best first search:
function [path,pathcost]= greedybfs()
city = readtable('asign2city.txt');
straight = readtable('assign2straight.txt');
dist = table2array(city(:,3)); dist1 = table2array(straight(:,2));
city = string(table2array(city(:,1:2)));
name = string(repmat('valladolid',length(dist1),1));
stcity = [table2array(straight(:,1)) name];
% final citynames and their between distances
citynames = [city; stcity];
distance =[dist;dist1];
val = 'Malaga';

2ASSIGNMENT 2
%%% Greedy best first seacrh algorithm
output1 = min(nonzeros(vlookup(val,citynames(:,1),distance)));
nextcity1 = rmmissing(vlookup(output1,distance,citynames(:,2)));
output2 = min(nonzeros(vlookup(nextcity1,citynames(:,1),distance)));
nextcity2 = rmmissing(vlookup(output2,distance,citynames(:,2)));
path =[val nextcity1 nextcity2]';
pathcost = output1 + output2;
end
%%% lookup function
function output = vlookup(lukupval,lukuparraycol,outputarraycol)
for i= 1:length(lukuparraycol)
if lukuparraycol(i) == lukupval
output(i) = outputarraycol(i);
end
end
end

3ASSIGNMENT 2
Output:
[path,pathcost]= greedybfs()
path =
3×1 string array
"Malaga"
"Sevilla"
"valladolid"
pathcost =
693
Hence, the greedy algorithm reached from Malaga to Valladolid in just two queries and the
path cost is 693.
1. a)
The solution of the problem will return the city names through which the query has been
made and the total path cost after reaching the goal. Here, the starting city is Malaga and the
end city is Valladolid.
b) The equation of f(n) for greedy best first search is given by,
f(n) = total estimated cost from city n to goal city
g(n) = so far cost to reach city n
h(n) = estimated cost from city n to goal
In greedy best first search algorithm f(n) = h(n)

4ASSIGNMENT 2
c) The Astar search algorithm is a least cost search algorithm which finds the minimum
distance from an initial configuration to the final configuration. This is the extended version
of the Dijkstra algorithm. The function of the algorithm is given by,
f(n) = g(n) + h(n)
Here, g(n) is the path-cost function or the distance from starting the to the present node.
h(n) is the estimate of the heuristic from distance to goal.
d) The difference between Astar and greedy algorithm is that the greedy algorithm reaches to
its next node or city based on the f(n) = h(n) that has the lowest value of heuristic and for that
reason it is known as ‘greedy’. Thus the greedy algorithm do not take the cost of the path to
its present state. While, the Astar algorithm visits to the next node based on f(n) = g + h,
where h is same as the best first search algorithm but another component g is added which is
path cost from initial to present node. Hence, the Astar algorithm chooses the lowest value of
heuristic and cost of initial to present state. Hence, Astar algorithm is complete and optimum.