4 questions AI

CSBP 301: Artificial Intelligence
Group Assignment
1. Number the nodes according to the order of exploring. In case of a tie, choose the
leftmost node to explore. (0.5 points)
DFS
BFS
UCS
1
1
1
2
5
3
2
2
3
1
1
2. Use Manhattan distance as heuristics in the below Greedy search. (2 points)
1. Calculate the heuristics at each node.
2. Number the nodes according to the order of exploration.
3. In case of a tie, choose the leftmost.
4. List the nodes in the fringe at every step.
5. Draw a search tree -ark the explored ones.
6. Write down the chosen path.
Greedy – Manhattan
A
S
C
B
1
I
D
2
K
F
L
M
3
1
G
4
3. A* Search algorithm with Manhattan distance as a heuristic. Diagonal movement is not
allowed, in case of a tie, choose the leftmost node. (2 points)
a. Find a real cost of arcs and heuristic cost for each node. Mark the nodes that are
explored.
b. Draw a search tree. Write g, h, and f next to each node.
c. Number the nodes according to the exploration.
d. List the nodes in the fringe at every step.
e. Write down the chosen path.
A* – Manhattan
C
A
D
S
L
I
K
G
B
1
F
M
2
4. Determine if the state space graph is
a. Admissible, explain why. (0.25 points)
b. Consistency of heuristic, explain why. (0.25 points)
h=2
A
G
1
1
1
h=1.3
h=2
S
0.5
0.5
C
0.5
1.2
B h=2
D h=1

Purchase answer to see full
attachment