Fa20 BCS 083

Name:
Tajamal Hayat
Reg.No:
FA20-BCS-083
Submitted To:
Sir Tahir Rasheed
Question.No.#1
Maze Solver with BFS
Code:
from collections import deque
# Maze represented as a 2D grid (0 for open path, 1 for wall)
maze = [
[0, 1, 0, 0, 0, 0, 0],
[0, 1, 0, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 0, 1],
[0, 0, 0, 0, 0, 0, 0],
# Define start and end points
start = (0, 0)
end = (len(maze) - 1, len(maze[0]) - 1)
# Function to perform BFS and find the path in the maze
def bfs(maze, start, end):
queue = deque([(start, [])])
visited = set()
while queue:
(x, y), path = queue.popleft()
if (x, y) == end:
return path + [(x, y)]
if 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 0 and (x, y) not in visited:
visited.add((x, y))
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
queue.append(((x + dx, y + dy), path + [(x, y)])
return []
# Find the path using BFS

path = bfs(maze, start, end)
# Print the path
if path:
print("Path found using BFS:")
for x, y in path:
maze[x][y] = "X" # Marking the path with "X"
print("(", x, ",", y, ")")
else:
print("No path found using BFS.")
# Print the updated maze with the path
for row in maze:
print(" ".join(map(str, row)))
Question.No.#2
Directory Tree Search using DFS
Code:
import os
def dfs_directory_tree_search(root_directory):
stack = [root_directory]
while stack:
current_directory = stack.pop()
try:
entries = os.listdir(current_directory)
except Exception as e:
print(f"Error accessing {current_directory}: {e}")
continue
for entry in entries:
full_path = os.path.join(current_directory, entry)
if os.path.isdir(full_path):
print(f"Directory: {full_path}")
stack.append(full_path)
else:
print(f"File: {full_path}")
# Specify the starting directory for the DFS search
starting_directory = "/path/to/your/directory"
if os.path.exists(starting_directory) and os.path.isdir(starting_directory):
print(f"Starting DFS search from: {starting_directory}")
dfs_directory_tree_search(starting_directory)
else:
print("Invalid starting directory. Please provide a valid path.")
Question.No#3
A* Pathfinding Algorithm
Code:
import heapq
# Define a class for nodes in the grid
class Node:
def __init__(self, x, y):
self.x = x
self.y = y
self.g = 0 # Cost from the start node
self.h = 0 # Heuristic (estimated cost to the goal)
self.parent = None
def __lt__(self, other):
return (self.g + self.h) < (other.g + other.h)
# A* pathfinding function
def astar(grid, start, end):
open_list = []
closed_set = set()
heapq.heappush(open_list, start)
while open_list:
current = heapq.heappop(open_list)
if current == end:
path = []
while current:
path.append((current.x, current.y))
current = current.parent
return path[::-1]
# Reverse the path to start from the beginning
closed_set.add(current)
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
new_x, new_y = current.x + dx, current.y + dy
if 0 <= new_x < len(grid) and 0 <= new_y < len(grid[0]) and grid[new_x][new_y] == 0:
neighbor = Node(new_x, new_y)
if neighbor in closed_set:
continue
tentative_g = current.g + 1
if neighbor not in open_list or tentative_g < neighbor.g:
neighbor.g = tentative_g
neighbor.h = abs(neighbor.x - end.x) + abs(neighbor.y - end.y)
neighbor.parent = current
if neighbor not in open_list:
heapq.heappush(open_list, neighbor)
return None # No path found
# Define the grid (0 for open, 1 for obstacles)
grid = [
[0, 0, 0, 0, 0],
[0, 1, 1, 0, 0],
[0, 0, 0, 1, 0],
[0, 0, 0, 1, 0],
[0, 0, 0, 0, 0]
# Define the start and end points
start = Node(0, 0)
end = Node(4, 4)
# Find the path using A* algorithm
path = astar(grid, start, end)
# Print the path
if path:
print("A* Pathfinding Algorithm:")
for x, y in path:
print("(", x, ",", y, ")")
else:
print("No path found using A* algorithm.")
Question.No.4
Heuristic values to find the optimal path
Code:
from queue import PriorityQueue
# Define a graph as an adjacency list with heuristic values
graph = {
'A': {'B': 5, 'C': 2},
'B': {'D': 7, 'E': 4},
'C': {'F': 1},

'D': {'G': 3},
'E': {'H': 6},
'F': {'I': 2},
'G': {},
'H': {'J': 1},
'I': {'K': 3},
'J': {'L': 4},
'K': {},
'L': {}
# Best First Search (BFS) algorithm
def best_first_search(graph, start, goal):
frontier = PriorityQueue()
frontier.put((0, start))
came_from = {}
cost_so_far = {start: 0}
while not frontier.empty():
_, current = frontier.get()
if current == goal:
break
for neighbor, cost in graph[current].items():
new_cost = cost_so_far[current] + cost
if neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]:
cost_so_far[neighbor] = new_cost
priority = new_cost # Heuristic value
frontier.put((priority, neighbor))
came_from[neighbor] = current
path = reconstruct_path(came_from, start, goal)
return path
# Function to reconstruct the path from the start to the goal
def reconstruct_path(came_from, start, goal):
current = goal
path = [current]
while current != start:
current = came_from[current]
path.append(current)
path.reverse()
return path
# Define the start and goal nodes
start_node = 'A'
goal_node = 'L'
# Find the best path using Best First Search
path = best_first_search(graph, start_node, goal_node)
# Print the path
if path:
print("Best First Search (BFS) Algorithm:")
print("Path:", " -> ".join(path))
print("Total Cost:", sum(graph[path[i]][path[i+1]] for i in range(len(path)-1))
else:
print("No path found using Best First Search.")

Fa20 BCS 083

Uploaded by

Copyright:

Available Formats

Fa20 BCS 083

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Fa20 BCS 083

Uploaded by

Copyright:

Available Formats

Name:

# Maze represented as a 2D grid (0 for open path, 1 for wall)

# Define start and end points

end = (len(maze) - 1, len(maze[0]) - 1)

# Function to perform BFS and find the path in the maze

def bfs(maze, start, end):

queue = deque([(start, [])])

(x, y), path = queue.popleft()

return path + [(x, y)]

queue.append(((x + dx, y + dy), path + [(x, y)])

# Find the path using BFS

# Print the path

print("Path found using BFS:")

maze[x][y] = "X" # Marking the path with "X"

print("(", x, ",", y, ")")

print("No path found using BFS.")

# Print the updated maze with the path

for row in maze:

print(" ".join(map(str, row)))

print(f"Error accessing {current_directory}: {e}")

for entry in entries:

full_path = os.path.join(current_directory, entry)

# Specify the starting directory for the DFS search

if os.path.exists(starting_directory) and os.path.isdir(starting_directory):

print(f"Starting DFS search from: {starting_directory}")

print("Invalid starting directory. Please provide a valid path.")

# Define a class for nodes in the grid

def __init__(self, x, y):

self.g = 0 # Cost from the start node

self.h = 0 # Heuristic (estimated cost to the goal)

def __lt__(self, other):

return (self.g + self.h) < (other.g + other.h)

def astar(grid, start, end):

# Reverse the path to start from the beginning

new_x, new_y = current.x + dx, current.y + dy

neighbor = Node(new_x, new_y)

if neighbor not in open_list or tentative_g < neighbor.g:

neighbor.h = abs(neighbor.x - end.x) + abs(neighbor.y - end.y)

if neighbor not in open_list:

return None # No path found

# Define the grid (0 for open, 1 for obstacles)

# Define the start and end points

# Find the path using A* algorithm

path = astar(grid, start, end)

# Print the path

print("A* Pathfinding Algorithm:")

print("(", x, ",", y, ")")

print("No path found using A* algorithm.")

# Define a graph as an adjacency list with heuristic values

'A': {'B': 5, 'C': 2},

'B': {'D': 7, 'E': 4},

'C': {'F': 1},

'E': {'H': 6},

'F': {'I': 2},

'H': {'J': 1},

'I': {'K': 3},

'J': {'L': 4},

# Best First Search (BFS) algorithm

def best_first_search(graph, start, goal):

def init(self, x, y):

def lt(self, other):