Problem Statement: Implement A star Algorithm for any game search problem.
Objectives:
1. To study various Search Algorithms
2. To study the A* Algorithm
Theory: A* Algorithm is the advanced form of the BFS algorithm (Breadth-first search), which searches forthe shorter path first than, the longer paths. It is a complete as well as an optimal solution for solving path and grid problems. The key feature of the A* algorithm is that it keeps a track of each visited node which helps in ignoring the nodes that are already visited, saving a huge amount of time. It also has a list that holdsall the nodes that are left to be explored and it chooses the most optimal node from this list, thus saving time not exploring unnecessary or less optimal nodes. So we use two lists namely open list and closed list the open list contains all the nodes that are being generated and are not existing in the closed list and each node explored after its neighboring nodes are discovered is put in the closed list and the neighbors are put in the open list this is how thenodes expand. Each node has a pointer to its parent so that at any given point it can retrace the path to the parent. Initially, the open list holds the start (Initial) node. The next node chosen from the open list is based on its f score (f(n)), the node with the least f-score is picked up and explored
f (n) = g (n) + h (n )
Heuristic used in A* Where
g (n) : The actual cost path from the start node to the current node.
h ( n) : The actual cost path from the current node to goal node.
f (n) : The actual cost path from the start node to the goal node
A Star Algorithm (8-Puzzle problem)
// A* Search Algorithm
1. Initialize the open list
2. Initialize the closed list put the starting node on the open list (you can leave its f at zero)
3. while the open list is not empty
a) find the node with the least f on the open list, call it "q"
b) pop q off the open list
c) generate q's 8 successors and set the ir parents to q
d) for each successor
i) if successor is the goal, stop search
ii) else, compute both g and h for successor successor.g = q.g + distance between successor and q successor.h = distance from goal to successor (This can be done using many ways, we will discuss three heuristics-Manhattan, Diagonal and Euclidean Heuristics) successor.f = successor.g + successor.h
iii) if a node with the same position assuccessor is in the OPEN list which has a lower f than successor, skip this successor
iv) if a node with the same position as Successor is in the CLOSED list which has a lower f than successor, skip this successorotherwise, add the node to the open list end (for loop)
e) push q on the closed listend (while loop)
Conclusion: Successfully implemented A* Algorithm for 8-Puzzles Problem
class Node:
def __init__(self, data, level, fval):
self.data = data
self.level = level
self.fval = fval
def generate_child(self):
x, y = self.find(self.data, '_')
val_list = [[x, y-1], [x, y+1], [x-1, y], [x+1, y]]
children = []
for i in val_list:
child = self.shuffle(self.data, x, y, i[0], i[1])
if child is not None:
child_node = Node(child, self.level+1, 0)
children.append(child_node)
return children
def shuffle(self, puz, x1, y1, x2, y2):
if x2 >= 0 and x2 < len(self.data) and y2 >= 0 and y2 < len(self.data):
temp_puz = []
temp_puz = self.copy(puz)
temp = temp_puz[x2][y2]
temp_puz[x2][y2] = temp_puz[x1][y1]
temp_puz[x1][y1] = temp
return temp_puz
else:
return None
def copy(self, root):
temp = []
for i in root:
t = []
for j in i:
t.append(j)
temp.append(t)
return temp
def find(self, puz, x):
for i in range(0, len(self.data)):
for j in range(0, len(self.data)):
if puz[i][j] == x:
return i, j
class Puzzle:
def __init__(self, size):
self.n = size
self.open = []
self.closed = []
def accept(self):
puz = []
for i in range(0, self.n):
temp = input().split(" ")
puz.append(temp)
return puz
def f(self, start, goal):
return self.h(start.data, goal)+start.level
def h(self, start, goal):
""" Calculates the different between the given puzzles """
temp = 0
for i in range(0, self.n):
for j in range(0, self.n):
if start[i][j] != goal[i][j] and start[i][j] != '_':
temp += 1
return temp
def process(self):
""" Accept Start and Goal Puzzle state"""
print("Enter the start state matrix \n")
start = self.accept()
print("Enter the goal state matrix \n")
goal = self.accept()
start = Node(start, 0, 0)
start.fval = self.f(start, goal)
self.open.append(start)
print("\n\n")
while True:
cur = self.open[0]
print("")
print(" | ")
print(" | ")
print(" \\\'/")
print(" V \n")
for i in cur.data:
for j in i:
print(j, end=" ")
print("")
if(self.h(cur.data, goal) == 0):
break
for i in cur.generate_child():
i.fval = self.f(i, goal)
self.open.append(i)
self.closed.append(cur)
del self.open[0]
self.open.sort(key=lambda x: x.fval, reverse=False)
puz = Puzzle(3)
puz.process()
