Question: I am trying to create a search tree visulisation for the given code in python. I am unable to how do I do it ?
I am trying to create a search tree visulisation for the given code in python. I am unable to how do I do it
import math
import heapq
import matplotlib.pyplot as plt
# Define the Cell class
class Cell:
def initself:
self.parenti # Parent cell's row index
self.parentj # Parent cell's column index
self.f floatinf # Total cost of the cell g h
self.g floatinf # Cost from start to this cell
self.h # Heuristic cost from this cell to destination
# Define the size of the grid
ROW
COL
# Check if a cell is valid within the grid
def isvalidrow col:
return row and row ROW and col and col COL
# Check if a cell is unblocked
def isunblockedgrid row, col:
return gridrowcol
# Check if a cell is the destination
def isdestinationrow col, dest:
return row dest and col dest
# Calculate the heuristic value of a cell Euclidean distance to destination
def calculatehvaluerow col, dest:
return absrow dest abscol dest
# Implement the A search algorithm
def astarsearchgrid src dest:
# Check if the source and destination are valid
if not isvalidsrc src or not isvaliddest dest:
printSource or destination is invalid"
return
# Check if the source and destination are unblocked
if not isunblockedgrid src src or not isunblockedgrid dest dest:
printSource or the destination is blocked"
return
# Initialize the closed list visited cells
closedlist False for in rangeCOL for in rangeROW
# Initialize the details of each cell
celldetails Cell for in rangeCOL for in rangeROW
# Initialize the start cell details
i src
j src
celldetailsijf
celldetailsijg
celldetailsijh
celldetailsijparenti i
celldetailsijparentj j
# Initialize the open list cells to be visited with the start cell
openlist
heapq.heappushopenlist, i j
# Initialize lists to store explored and open cells for plotting
exploredcells
opencells
# Main loop of A search algorithm
while lenopenlist:
# Pop the cell with the smallest f value from the open list
p heapq.heappopopenlist
# Mark the cell as visited
i p
j p
closedlistij True
exploredcells.appendi j
# For visualization, also store open cells
for item in openlist:
opencells.appenditem item
# For each direction, check the successors
directions
for dir in directions:
newi i dir
newj j dir
# If the successor is valid, unblocked, and not visited
if isvalidnewi newj and isunblockedgrid newi newj and not closedlistnewinewj:
# If the successor is the destination
if isdestinationnewi newj dest:
# Set the parent of the destination cell
celldetailsnewinewjparenti i
celldetailsnewinewjparentj j
printThe destination cell is found"
return exploredcells, opencells
else:
# Calculate the new f g and h values
gnew celldetailsijg
hnew calculatehvaluenewi newj dest
fnew gnew hnew
# If the cell is not in the open list or the new f value is smaller
if celldetailsnewinewjf floatinf or celldetailsnewinewjf fnew:
# Add the cell to the open list
heapq.heappushopenlist, fnew, newi newj
# Update the cell details
celldetailsnewinewjf fnew
celldetailsnewinewjg gnew
celldetailsnewinewjh hnew
celldetailsnewinewjparenti i
celldetailsnewinewjparentj j
def plotsearchtreegrid exploredcells, opencells, src dest:
fig, ax pltsubplots
axsetaspectequal 'box'
for i in rangeROW:
for j in rangeCOL:
if i j in exploredcells:
axaddpatchpltRectanglej i color'lightblue'
elif i j in opencells:
axaddpatchpltRectanglej i color'lightgreen'
elif i j tuplesrc:
axaddpatchpltRectanglej i color'red'
elif i j tupledest:
axaddpatchpltRectanglej i color'orange'
elif isunblockedgrid i j:
axaddpatchpltRectanglej i color'white'
else:
axaddpatchpltRectanglej i color'black'
axautoscaleview
axinvertyaxis
pltshow
def main:
# Define the grid for unblocked, for blocked
grid
Step by Step Solution
There are 3 Steps involved in it
1 Expert Approved Answer
Step: 1 Unlock
Question Has Been Solved by an Expert!
Get step-by-step solutions from verified subject matter experts
Step: 2 Unlock
Step: 3 Unlock
Study Help