Objectives:
·
To implement Greedy Best First Search (GBFS
or GFS) algorithm for graphs using python
Hardware/Software Required for the Operation:
Hardware:
Desktop/ Notebook Computer
Software Tool: Python 2.7/ 3.6.2
Introduction:
Click Here: What is GFS.
In
this task we will see one of the informed search strategies i.e., Best First
Search Algorithm. In this algorithm node selected for expansion depends on evaluation
function f(n). This evaluation constructed on cost estimate, hence
the vertex with lowest cost is expanded first. Best first Search also uses a Heuristic
Function h(n).
h(n) = estimated cost
of the cheapest path from the state at node n to a goal
state
Greedy
Best First Search (GBFS) is based on greedy algorithm in which node that is
closest to the goal node is expanded first. GBFS uses heuristic function for
node evaluation. Since at any level, BFS expands a node with the lowest cost so
we need to implement a priority queue to hold the nodes with their costs as
priority.
The pseudocode for the BFS is given below:
The
pseudocode for the BFS is given below:
BFS(Graph
g, sNode, goal, priority = 0, path = [])
Initialize
a Priority Queue ‘PQ’ and insert sNode in it.
while
PQ is not empty
u = PQ.get()
if u.value is the goal
return path
else
foreach neighbor v of u
foreach key
in v
if key not in path
Insert
v in PQ
Append u.value in path
return
path
Tasks:
Before Solving the task read the pseudocode very carefully:
1. Study
‘queue’ and use it to develop priority queues in python and check if it’s
working properly.
2. Implement Best First Search using edge
cost as an evaluation function algorithm in python for following graph 1
3. Implement Best First Search using cost
estimate function and Greedy Best First Search using heuristic values given in
figure 1 in python for graph 2.
4. Write down your opinion based on the
outputs of task3.
Graph 1: Start Node: A, Goal: G
Graph2: Start Node: Arad, Goal: Bucharest
Task 01
Program Code:
from queue import PriorityQueue as P
queue = P()
queue.put((2, 'A'))
queue.put((1, 'J'))
queue.put((3, 'M'))
queue.put((4, 'S'))
queue.put((5, 'H'))
queue.put((6, 'A'))
queue.put((7, 'I'))
queue.put((8, 'D'))
print('Before: Size of Queue: ', queue.qsize())
while not queue.empty():
print(queue.get())
print('After: Size of Queue: ', queue.qsize())
Output:
Task 02:
Program Code:
class Graph:
def __init__(self, graph_dict=None, directed=True):
self.graph_dict = graph_dict or {}
self.directed = directed
if not directed:
self.make_undirected()
def make_undirected(self):
for a in list(self.graph_dict.keys()):
for (b, dist) in self.graph_dict[a].items():
self.graph_dict.setdefault(b, {})[a] = dist
def connect(self, A, B, distance):
self.graph_dict.setdefault(A, {})[B] = distance
if not self.directed:
self.graph_dict.setdefault(B, {})[A] = distance
def get(self, a, b=None):
links = self.graph_dict.setdefault(a, {})
if b is None:
return links
else:
return links.get(b)
def nodes(self):
s1 = set([k for k in self.graph_dict.keys()])
s2 = set([k2 for v in self.graph_dict.values() for k2, v2 in v.items()])
nodes = s1.union(s2)
return list(nodes)
class Node:
def __init__(self, name:str, parent:str):
self.name = name
self.parent = parent
self.g = 0
self.f = 0
def __eq__(self, other):
return self.name == other.name
def __lt__(self, other):
return self.f < other.f
def __repr__(self):
return ('({0},{1})'.format(self.position, self.f))
def best_first_search(graph, start, end):
open = []
closed = []
start_node = Node(start, None)
goal_node = Node(end, None)
open.append(start_node)
while len(open) > 0:
open.sort()
current_node = open.pop(0)
closed.append(current_node)
if current_node == goal_node:
path = []
while current_node != start_node:
path.append(current_node.name + ': ' + str(current_node.g))
current_node = current_node.parent
path.append(start_node.name + ': ' + str(start_node.g))
return path[::-1]
neighbors = graph.get(current_node.name)
for key, value in neighbors.items():
neighbor = Node(key, current_node)
if(neighbor in closed):
continue
neighbor.g = current_node.g + graph.get(current_node.name, neighbor.name)
neighbor.f = neighbor.g
if(add_to_open(open, neighbor) == True):
open.append(neighbor)
return None
def add_to_open(open, neighbor):
for node in open:
if (neighbor == node and neighbor.f >= node.f):
return False
return True
def main():
graph = Graph()
graph.connect('A', 'B', 5)
graph.connect('A', 'D', 3)
graph.connect('B', 'C', 5)
graph.connect('C', 'A', 3)
graph.connect('C', 'D', 2)
graph.connect('C', 'E', 4)
graph.connect('D', 'E', 2)
graph.connect('D', 'F', 6)
graph.connect('E', 'B', 1)
graph.connect('E', 'G', 1)
graph.connect('F', 'G', 9)
path = best_first_search(graph, 'A', 'G')
print(path)
if __name__ == "__main__": main()
Output:
Task 03:
Program Code:
class Graph:
def __init__(self, graph_dict=None, directed=False):
self.graph_dict = graph_dict or {}
self.directed = directed
if not directed:
self.make_undirected()
def make_undirected(self):
for a in list(self.graph_dict.keys()):
for (b, dist) in self.graph_dict[a].items():
self.graph_dict.setdefault(b, {})[a] = dist
def connect(self, A, B, distance):
self.graph_dict.setdefault(A, {})[B] = distance
if not self.directed:
self.graph_dict.setdefault(B, {})[A] = distance
def get(self, a, b=None):
links = self.graph_dict.setdefault(a, {})
if b is None:
return links
else:
return links.get(b)
def nodes(self):
s1 = set([k for k in self.graph_dict.keys()])
s2 = set([k2 for v in self.graph_dict.values() for k2, v2 in v.items()])
nodes = s1.union(s2)
return list(nodes)
class Node:
def __init__(self, name:str, parent:str):
self.name = name
self.parent = parent
self.g = 0
self.h = 0
self.f = 0
def __eq__(self, other):
return self.name == other.name
def __lt__(self, other):
return self.f < other.f
def __repr__(self):
return ('({0},{1})'.format(self.position, self.f))
def best_first_search(graph, heuristics, start, end):
open = []
closed = []
start_node = Node(start, None)
goal_node = Node(end, None)
open.append(start_node)
while len(open) > 0:
open.sort()
current_node = open.pop(0)
closed.append(current_node)
if current_node == goal_node:
path = []
while current_node != start_node:
path.append(current_node.name + ': ' + str(current_node.g))
current_node = current_node.parent
path.append(start_node.name + ': ' + str(start_node.g))
return path[::-1]
neighbors = graph.get(current_node.name)
for key, value in neighbors.items():
neighbor = Node(key, current_node)
if(neighbor in closed):
continue
neighbor.g = current_node.g + graph.get(current_node.name, neighbor.name)
neighbor.h = heuristics.get(neighbor.name)
neighbor.f = neighbor.g
if(add_to_open(open, neighbor) == True):
open.append(neighbor)
return None
def Greedy_best_first_search(graph, heuristics, start, end):
open = []
closed = []
start_node = Node(start, None)
goal_node = Node(end, None)
open.append(start_node)
while len(open) > 0:
open.sort()
current_node = open.pop(0)
closed.append(current_node)
if current_node == goal_node:
path = []
while current_node != start_node:
path.append(current_node.name + ': ' + str(current_node.g))
current_node = current_node.parent
path.append(start_node.name + ': ' + str(start_node.g))
return path[::-1]
neighbors = graph.get(current_node.name)
for key, value in neighbors.items():
neighbor = Node(key, current_node)
if(neighbor in closed):
continue
neighbor.g = current_node.g + graph.get(current_node.name, neighbor.name)
neighbor.h = heuristics.get(neighbor.name)
neighbor.f = neighbor.h
if(add_to_open(open, neighbor) == True):
open.append(neighbor)
return None
def add_to_open(open, neighbor):
for node in open:
if (neighbor == node and neighbor.f >= node.f):
return False
return True
def main():
graph = Graph()
graph.connect('Arad', 'Zerind', 75)
graph.connect('Arad', 'Sibiu', 140)
graph.connect('Arad', 'Timisoara', 118)
graph.connect('Zerind', 'Oradea', 71)
graph.connect('Sibiu', 'Fagaras', 99)
graph.connect('Sibiu', 'Rimnicu Vilcea', 80)
graph.connect('Timisoara', 'Lugoj', 111)
graph.connect('Oradea', 'Sibiu', 151)
graph.connect('Fagaras', 'Bucharest', 211)
graph.connect('Rimnicu Vilcea', 'Pitesti', 101)
graph.connect('Rimnicu Vilcea', 'Craiova', 146)
graph.connect('Lugoj', 'Mehadia', 70)
graph.connect('Bucharest', 'Giurgin', 90)
graph.connect('Bucharest', 'Urziceni', 85)
graph.connect('Pitesti', 'Bucharest', 101)
graph.connect('Pitesti', 'Craiova', 138)
graph.connect('Mehadia', 'Drobeta', 75)
graph.connect('Urziceni', 'Vaslui', 142)
graph.connect('Urziceni', 'Hirsova', 98)
graph.connect('Craiova', 'Drobeta', 120)
graph.connect('Vaslui', 'Iasi', 92)
graph.connect('Hirsova', 'Eforie', 86)
graph.connect('Iasi', 'Neamt', 87)
heuristics = {}
heuristics['Arad'] = 366
heuristics['Bucharest'] = 0
heuristics['Craiova'] = 160
heuristics['Drobeta'] = 242
heuristics['Eforie'] = 161
heuristics['Fagaras'] = 176
heuristics['Giurgiu'] = 77
heuristics['Hirsova'] = 151
heuristics['Iasi'] = 226
heuristics['Lugoj'] = 244
heuristics['Mehadia'] = 241
heuristics['Neamt'] = 234
heuristics['Oradea'] = 380
heuristics['Pitesti'] = 100
heuristics['Rimnicu Vilcea'] = 193
heuristics['Sibiu'] = 253
heuristics['Timisoara'] = 329
heuristics['Urziceni'] = 80
heuristics['Vaslui'] = 199
heuristics['Zerind'] = 374
bfspath = best_first_search(graph, heuristics, 'Arad', 'Bucharest')
print("Path using Best first search cost estimate function:\n", bfspath)
gbfspath = Greedy_best_first_search(graph, heuristics, 'Arad', 'Bucharest')
print("\nPath using Greedy Best first search with heuristic function:\n", gbfspath)
if __name__ == "__main__": main()
Output:
Task 04:
Program Code:
import numpy as np
class Graph:
def __init__(self, graph_dict=None, directed=True):
self.graph_dict = graph_dict or {}
self.directed = directed
if not directed:
self.make_undirected()
def make_undirected(self):
for a in list(self.graph_dict.keys()):
for (b, dist) in self.graph_dict[a].items():
self.graph_dict.setdefault(b, {})[a] = dist
def connect(self, A, B, distance):
self.graph_dict.setdefault(A, {})[B] = distance
if not self.directed:
self.graph_dict.setdefault(B, {})[A] = distance
def get(self, a, b=None):
links = self.graph_dict.setdefault(a, {})
if b is None:
return links
else:
return links.get(b)
def nodes(self):
s1 = set([k for k in self.graph_dict.keys()])
s2 = set([k2 for v in self.graph_dict.values() for k2, v2 in v.items()])
nodes = s1.union(s2)
return list(nodes)
class Node:
def __init__(self, name:str, parent:str):
self.name = name
self.parent = parent
self.g = 0
self.h = 0
self.f = 0
def __eq__(self, other):
return self.name == other.name
def __lt__(self, other):
return self.f < other.f
def __repr__(self):
return ('({0},{1})'.format(self.position, self.f))
def best_first_search(graph, heuristics, start, end):
open = []
closed = []
start_node = Node(start, None)
goal_node = Node(end, None)
open.append(start_node)
while len(open) > 0:
open.sort()
current_node = open.pop(0)
closed.append(current_node)
if current_node == goal_node:
path = []
while current_node != start_node:
path.append(current_node.name + ': ' + str(current_node.g))
current_node = current_node.parent
path.append(start_node.name + ': ' + str(start_node.g))
return path[::-1]
neighbors = graph.get(current_node.name)
for key, value in neighbors.items():
neighbor = Node(key, current_node)
if(neighbor in closed):
continue
neighbor.g = current_node.g + graph.get(current_node.name, neighbor.name)
neighbor.h = heuristics.get(neighbor.name)
neighbor.f = neighbor.h
if(add_to_open(open, neighbor) == True):
open.append(neighbor)
return None
def add_to_open(open, neighbor):
for node in open:
if (neighbor == node and neighbor.f >= node.f):
return False
return True
def Extract_edges(img):
edge = []
edges = []
r = img.shape[0]
c = img.shape[1]
for i in range(0, img.shape[0]):
for j in range(0, img.shape[1]):
if i < r-1 and j < c-1:
edge = (img[i, j], img[i, j+1])
edges.append(edge)
edge = (img[i, j], img[i+1, j])
edges.append(edge)
elif i == r-1 and j != c-1:
edge = (img[i, j], img[i, j+1])
edges.append(edge)
elif i != r-1 and j == c-1:
edge = (img[i, j], img[i+1, j])
edges.append(edge)
return edges
def main():
img = np.array([[150, 2, 5], [80, 145, 45], [74, 102, 165]])
print('Image:\n', img)
edges = np.array(Extract_edges(img))
print('\nEdges of graph: \n', edges)
graph = Graph()
for i in range(0, edges.shape[0]):
graph.connect(str(edges[i][0]), str(edges[i][1]), abs(int(edges[i][0]) - int(edges[i][1])))
graph.make_undirected()
heuristics = {}
for i in range(0, img.shape[0]):
for j in range(0, img.shape[1]):
heuristics[str(img[i][j])] = abs(img[i][j] - img[2][2])
print("\nHeuristic values of every single node\n", heuristics)
path = best_first_search(graph, heuristics, '150', '165')
print("\nPath from Node 150 to node 165\n", path)
if __name__ == "__main__": main()
Output:
No comments:
Post a Comment