Informed Search

Part $1$: Problem representation

In this part, you have to define $\backslash ($represent$\backslash )$ the problem, that is to tell the computer what the problem look like. For example, your representaion should be able to express the location of the nodes, and the travel cost between connected nodes. $\backslash ($Also$,$ don't forget to define the grid world, you may need it for the heuristic.$\backslash )$

# Define the graph

graph $=\{$

$$ # Your code here.

$$ # hint: $\text{'}$A$\text{'}$: $[(\text{'}$B$\text{'},3),(\text{'}$C$\text{'},8),(\text{'}$D$\text{'},5)],...$

$\}$

positions $=\{$

$$ # Your code here.

$$ # hint: $\text{'}$A$\text{'}$: $(4,1),...$

$\}$

Part $2$: Heuristic

In this part, define a admissible heuristic function for this problem.

# Your code here

def heuristic$($node$,$ goal, positions$)$:

$$ # Define a heuristic function that estimates the cost from node to goal

$$ # Your code here.

$$ pass

Part $3$: Greedy Best First Search

In this part, implement a function doing the Greedy best first search to find the solution for the problem. $($To reduce the difficulty, I have given you most code, you only need to fill$-$in a couple of lines to make this function working.$\backslash )$

from queue import PriorityQueue

def greedy$\_$best$\_$first$\_$search$($graph$,$ positions, start, goal$)$:

$$ visited $=$ set$()$

$$ pq $=$ PriorityQueue$()$

$$ pq$.$put$((0,$ start$))$# $($heuristic value, node$)$

$$ parent $=\{\}$# stores the parent node of each visited node

$$ while not pq$.$empty$()$:

$\_,$ current$\_$node $=$ pq$.$get$()$

$$ visited.add$($current$\_$node$)$

$$ if current$\_$node $==$ goal:

$$ break

$$ for neighbor, weight in graph$[$current$\_$node$]$:

$$ if neighbor not in visited:

$$ # Your code here.

$$ pass

# Reconstruct the path from the goal to the start

$$ path $=[]$

$$ node $=$ goal

$$ while node $!=$ start:

$$ path.append$($node$)$

$$ node $=$ parent$[$node$]$

$$ path.append$($start$)$

# Reverse the path to get it from start to goal

$$ path.reverse$()$

$$ return path

Part $4$: A$*$ search

In this part, implement the A$*$ function to solve the problem. $($hint: you can seek inspiration from the greedy best first search implementation$\backslash )$

def astar$\_$search$($graph$,$ positions, start, goal$)$:

$$ # Your code here.

$$ pass

Part $5$: Main function

This part is the main function to run your search functions.

def print$\_$path$($path$)$:

$$ # Print the resulting path

$$ if path:

$$ print$("$Path found:", $\text{'}->\text{'}.$join$($path$))$

$$ else:

$$ print$("$No path found."$)$

def main$()$:

$$ # Run the Greedy Best$-$First Search algorithm

$$ start$\_$node $=\text{'}$A$\text{'}$

$$ goal$\_$node $=\text{'}$I$\text{'}$

$$ path$\_$gbf $=$ greedy$\_$best$\_$first$\_$search$($graph$,$ positions, start$\_$node, goal$\_$node$)$

$$ path$\_$astar $=$ astar$\_$search$($graph$,$ positions, start$\_$node, goal$\_$node$)$

# Print the resulting path

$$ print$("$Greedy Best First Search: $")$

$$ print$\_$path$($path$\_$gbf$)$

print$("$A$*$ Search: $")$

$$ print$\_$path$($path$\_$astar$)$

main$()$

Please help me with this; follow the instructions carefully, please!

Thank you!!