1/23/2021 Artificial Intelligence Search Methods For Problem Solving - - Unit 9 - Week 6

(https://swayam.gov.in) (https://swayam.gov.in/nc_details/NPTEL)

reviewer6@nptel.iitm.ac.in 

NPTEL (https://swayam.gov.in/explorer?ncCode=NPTEL) » Artificial Intelligence Search Methods For Problem Solving (course)

Announcements (announcements) About the Course (preview) Ask a Question (forum) Progress (student/home) Mentor (student/mentor)

Unit 9 - Week 6

Course outline

How does an NPTEL online

Assignemnt 6
course work? The due date for submitting this assignment has passed. Due on 2020-10-28, 23:59 IST.
As per our records you have not submitted this assignment.
Pre-requisite Assignment
The figure shows a map (repeated from Week 5) with several locations on a grid where each tile is 10km x 10 km in size. In this map, S is the start node
Week 0 and G is the goal node, the locations are connected by two-way edges (roads). Each edge has a cost and the cost is the same in both directions

Week 1

Week 2

Week 3

Week 4

Week 5

Week 6

B&B - A* - wA* - Best First

(unit?unit=34&lesson=154)

A*: Leaner Admissible

Variations (unit?
unit=34&lesson=155)

The Monotone Condition

(unit?unit=34&lesson=156)

DNA Sequence Alignment

(unit?unit=34&lesson=157) For this map, MoveGen returns nodes in alphabetical order.

Divide & Conquer Frontier When several nodes have the same cost, use alphabetical order to break ties.
Search. (unit?
unit=34&lesson=158)
When the same node occurs multiple times with the same cost then use the open-sequence-number to break ties, i.e., pick up the node occurrence that is
Variations on A*: The story oldest (was placed earliest in time) in the OPEN list.
so far (unit?
unit=34&lesson=159) Where needed, use Manhattan distance as the heuristic function.
Smart Memory Graph Search
(unit?unit=34&lesson=160) Simulate WA* with w=2, Breadth First Heuristic Search with U=312, Sparse-Memory Graph Search, and Beam Search with w=2 on the above map and
answer the following questions
Breadth First Heuristic
Search (unit?
unit=34&lesson=161)
BEGIN GROUP
Beam Stack Search (unit?
unit=34&lesson=162)
1) For w=2, in f = g + w*h, simulate WA* algorithm on the given map. List the 3rd, 6th and 9th nodes inspected by the algorithm.
Week 6 - Feedback : Artificial
Intelligence Search Methods Enter node labels as a comma separated list. DO NOT enter extraneous characters like spaces, dots, brackets, extra commas, etc.
for problem Solving (unit?
unit=34&lesson=38)

Lecture Materials (unit? No, the answer is incorrect.

unit=34&lesson=177) Score: 0
Accepted Answers:
Quiz : Assignemnt 6
(Type: String) L,T,J
(assessment?name=197)
(Type: String) L, T, J
Week 7
1 point

Week 8 2) What are the f-values of the 3rd, 6th and 9th nodes listed in the previous question?

Enter the costs as a comma separated list of natural numbers. DO NOT enter extraneous characters like spaces, dots, brackets, extra commas, etc

https://onlinecourses.nptel.ac.in/noc20_cs81/unit?unit=34&assessment=197 1/5
 1/23/2021 Artificial Intelligence Search Methods For Problem Solving - - Unit 9 - Week 6

Week 9
No, the answer is incorrect.
Week 10 Score: 0
Accepted Answers:
Week 11 (Type: String) 345,345,335
(Type: String) 345, 345, 335
Week 12 1 point

DOWNLOAD VIDEOS 3) For WA* with w=2, what is the path found by the algorithm?

Enter the path (starting from S and ending in G) as a comma separated list of node labels. DO NOT enter extraneous characters like spaces, dots,
brackets, extra commas, etc

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: String) S,V,W,T,Z,J,G
(Type: String) S, V, W, T, Z, J, G

1 point

4) What is the cost of the path found by WA* algorithm?

Enter a natural number

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: Numeric) 300

1 point

END GROUP

BEGIN GROUP

Simulate the Breadth First Heuristic Search (BFHS) with U=312 on the given map. Remember that the MoveGen function generates nodes in alphabetic
order and that the algorithm does not add nodes that are in OPEN or CLOSED to OPEN.

Assume f = g + h, where g is the actual-cost of the path generated by BFHS (not by A*), and h is the heuristic value. Prune the new nodes if f-value is
greater than or equal to U. Prune the nodes before placing them in OPEN list.

5) List the 5th, 8th, 11th and 14th nodes visited by BFHS.

Enter the node labels as a comma separated list. DO NOT enter extraneous characters like spaces, dots, brackets, extra commas, etc.

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: String) V,Q,V1,Z1
(Type: String) V, Q, V1, Z1

1 point

6) What are the costs of the 5th, 8th, 11th and 14th nodes listed in the previous question?

Enter the costs as a comma separated list of natural numbers. DO NOT enter extraneous characters like spaces, dots, brackets, extra commas, etc

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: String) 205,290,250,275
(Type: String) 205, 290, 250, 275

1 point

END GROUP

BEGIN GROUP

For the following questions assume that the Sparse-Memory Graph Search (SMGS) has enough memory to only hold 4 nodes in Kernel. We will not count
S to be part of the Kernel (because it is never deleted).

In this group, enter ALL node-lists in ALPHABETIC order.

https://onlinecourses.nptel.ac.in/noc20_cs81/unit?unit=34&assessment=197 2/5
1/23/2021 Artificial Intelligence Search Methods For Problem Solving - - Unit 9 - Week 6

7) List the nodes in OPEN after SMGS has inspected 4 nodes starting with S, where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a comma separated list in ALPHABETIC order. DO NOT enter extraneous
characters like spaces, dots, brackets, extra commas, etc

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: String) D,H,Q,U,U1,V1,W
(Type: String) D, H, Q, U, U1, V1, W

1 point

8) List the nodes in the BOUNDARY after SMGS has inspected 4 nodes starting with S, where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a comma separated list in ALPHABETIC order. DO NOT enter extraneous
characters like spaces, dots, brackets, extra commas, etc

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: String) L,O,S,V
(Type: String) L, O, S, V

1 point

9) List the nodes in the KERNEL after SMGS has inspected 4 nodes starting with S, where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a comma separated list in ALPHABETIC order. DO NOT enter extraneous
characters like spaces, dots, brackets, extra commas, etc.

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: String) NIL

1 point

10) List the nodes in OPEN after SMGS has inspected 8 nodes starting with S, where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a comma separated list in ALPHABETIC order. DO NOT enter extraneous
characters like spaces, dots, brackets, extra commas, etc.

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: String) D,H,M,P,Q,R,U1,U2,Z,Z1
(Type: String) D, H, M, P, Q, R, U1, U2, Z, Z1

1 point

11) List the nodes in the BOUNDARY after SMGS has inspected 8 nodes starting with S, where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a comma separated list in ALPHABETIC order. DO NOT enter extraneous
characters like spaces, dots, brackets, extra commas, etc

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: String) L,O,T,U,V,V1
(Type: String) L, O, T, U, V, V1

1 point

12) List the nodes in the KERNEL after SMGS has inspected 8 nodes starting with S, where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a comma separated list in ALPHABETIC order. DO NOT enter extraneous
characters like spaces, dots, brackets, extra commas, etc

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: String) W

1 point

13) List the nodes in OPEN after SMGS has inspected 12 nodes starting with S, where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a comma separated list in ALPHABETIC order. DO NOT enter extraneous
characters like spaces, dots, brackets, extra commas, etc

https://onlinecourses.nptel.ac.in/noc20_cs81/unit?unit=34&assessment=197 3/5
1/23/2021 Artificial Intelligence Search Methods For Problem Solving - - Unit 9 - Week 6

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: String) D,E,H,J,P,Q,R,U2,X,Z2
(Type: String) D, E, H, J, P, Q, R, U2, X, Z2

1 point

14) List the nodes in the BOUNDARY after SMGS has inspected 12 nodes starting with S, where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a comma separated list in ALPHABETIC order. DO NOT enter extraneous
characters like spaces, dots, brackets, extra commas, etc

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: String) L,M,O,U,U1,V1,Z,Z1
(Type: String) L, M, O, U, U1, V1, Z, Z1

1 point

15) List the nodes in the KERNEL after SMGS has inspected 12 nodes starting with S, where S is the first node.

If there are no nodes then enter NIL, otherwise enter the node labels as a comma separated list in ALPHABETIC order. DO NOT enter extraneous
characters like spaces, dots, brackets, extra commas, etc

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: String) T,V,W
(Type: String) T, V, W

1 point

END GROUP

BEGIN GROUP

Simulate the Beam Search (with f-values) with beam width w=2. This means the best two nodes are retained at each level irrespective of whether they are
better than their parents or not.

16) What is the path found by Beam Search?

Enter the path (starting from S and ending in G) as a comma separated list of node labels. DO NOT enter extraneous characters like spaces, dots,
brackets, extra commas, etc

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: String) S,L,H,E,B,G
(Type: String) S, L, H, E, B, G

1 point

17) What is the cost of the path found in the previous question?

Enter a natural number.

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: Numeric) 325

1 point

18) What is the other node in the beam (apart from G) at the point when the algorithm terminates?

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: String) Z

1 point

19) What is the cost of the node found in the previous question?

Enter a natural number.

https://onlinecourses.nptel.ac.in/noc20_cs81/unit?unit=34&assessment=197 4/5
1/23/2021 Artificial Intelligence Search Methods For Problem Solving - - Unit 9 - Week 6

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: Numeric) 485

1 point

END GROUP

20) When the Monotone Condition is satisfied we sometimes force the search to “never leak” back because 1 point

we want to prune the CLOSED list to reduce space complexity

we want to prune the CLOSED list to reduce time complexity
we want to reduce space complexity even at the expense of increasing time complexity
we want to reduce time complexity even at the expense of increasing space complexity
we have already found the optimal path to nodes in CLOSED
we want to put each node in OPEN only once
No, the answer is incorrect.
Score: 0
Accepted Answers:
we want to prune the CLOSED list to reduce space complexity
we want to reduce space complexity even at the expense of increasing time complexity
we have already found the optimal path to nodes in CLOSED

https://onlinecourses.nptel.ac.in/noc20_cs81/unit?unit=34&assessment=197 5/5