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

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

[email protected] 

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 6 - Week 3

Course outline

How does an NPTEL online

Assignment 3
course work? The due date for submitting this assignment has passed. Due on 2020-10-07, 23:59 IST.
As per our records you have not submitted this assignment.
Pre-requisite Assignment

Week 0 The figure shows a map with several locations on a grid where each tile is 10km x 10km in size. In this map, S is the start node and G is the goal node, the
locations are connected by two way edges (or roads). The MoveGen returns nodes in alphabetical order. Assume that RemoveSeen procedure removes
Week 1 children already in OPEN or CLOSED list. Use Manhattan distance when needed.

Week 2

Week 3

Heuristic Search (unit?

unit=19&lesson=134)

Heuristic Functions and the

Search Landscape (unit?
unit=19&lesson=135)

Solution Space Search (unit?

unit=19&lesson=136)

The Traveling Salesman

Problem (unit?
unit=19&lesson=137)

Escaping Local Optima (unit?

unit=19&lesson=138)

Stochastic Local Search

(unit?unit=19&lesson=139)

Week 3- Feedback : Artificial

Intelligence Search Methods
for problem Solving (unit?
unit=19&lesson=23)

Lecture Materials (unit?

unit=19&lesson=174)

Quiz : Assignment 3
(assessment?name=194)
1) In the map, starting with node S, list the first 7 nodes inspected (or expanded) by Depth First Search (DFS) algorithm. List the nodes in the order they
Week 4 were inspected. If the algorithm terminates early then list all the nodes seen.

Week 5 Enter a comma separated list of node labels. Do not enter spaces, periods or other characters in the textbox

Week 6
No, the answer is incorrect.
Week 7 Score: 0
Accepted Answers:
Week 8 (Type: String) S,L,D,A,K,F,C

2 points
Week 9
2) In the map, starting with node S, what is the 15th node inspected (or expanded) by Depth First Search (DFS) algorithm? If the algorithm terminates early
Week 10 then name the last node inspected.

Week 11 Enter a node label in the textbox

Week 12
No, the answer is incorrect.
DOWNLOAD VIDEOS Score: 0
Accepted Answers:

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

(Type: String) Z1

2 points

3) In the map, starting with node S, list the first 7 nodes inspected (or expanded) by the Breadth First Search (BFS) algorithm. List the nodes in the order
they were inspected. If the algorithm terminates early then list all the nodes seen.

Enter a comma separated list of node labels. Do not enter spaces, periods or other characters in the textbox.

No, the answer is incorrect.

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

2 points

4) In the map, starting with node S, what is the 15th node inspected (or expanded) by Breadth First Search (BFS) algorithm? If the algorithm terminates
early then name the last node inspected.

Enter a node label in the textbox.

No, the answer is incorrect.

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

2 points

5) What is the heuristic value of node E?

Enter an integer in the textbox.

No, the answer is incorrect.

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

1 point

6) What is the heuristic value of node W?

Enter an integer in the textbox

No, the answer is incorrect.

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

1 point

7) Which node has the largest heuristic value? What is its heuristic value?

Enter the node label and the heuristic value as a comma separated list. For example: A,170

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: String) P1,270

1 point

8) Which node has the smallest heuristic value? What is its heuristic value?

Enter the node label and the heuristic value as a comma separated list. For example: A,170

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: String) G,0

1 point

9) In the map, starting with node S, list the first 7 nodes inspected (or expanded) by the Best First Search algorithm. If the algorithm terminates early then
list the nodes inspected including the goal node. List the nodes in the order they were inspected.

Enter a comma separated list of node labels. Do not enter spaces, periods or other characters in the textbox.

No, the answer is incorrect.

Score: 0
Accepted Answers:

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

(Type: String) S,O,Q,M,E,B,G

2 points

10) In the map, starting with node S, what is the 15th node inspected (or expanded) by Best First Search algorithm? If the algorithm terminates early then list
the last node inspected.

Enter a node label in the textbox.

No, the answer is incorrect.

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

1 point

11) In the map, starting with node S, list the first 7 nodes inspected (or expanded) by Hill Climbing algorithm. If the algorithm terminates early then list the
nodes inspected. List the nodes in the order they were inspected.

Enter a comma separated list of node labels. Do not enter spaces, periods or other characters in the textbox.

No, the answer is incorrect.

Score: 0
Accepted Answers:
(Type: String) S,O,Q,M

2 points

12) In the map, starting with node S, what is the 15th node inspected (or expanded) by Hill Climbing algorithm? If the algorithm terminates early then list the
last node inspected.

Enter a node label in the textbox

No, the answer is incorrect.

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

1 point

13) For the given map, which of the algorithms finds a path from the start node S to the goal node G? 1 point

Depth First Search

Breadth First Search
Hill Climbing
Best First Search
No, the answer is incorrect.
Score: 0
Accepted Answers:
Depth First Search
Breadth First Search
Best First Search

14) For the city map given above, ignore all nodes with only one edge. Now try and find a TSP tour for the remaining nodes. Note: It is not a 2 points
complete graph and only the given edges are to be considered. Choose the correct options below. For the remaining nodes,

I could not find a tour

No one can find a tour
I found one tour
There appears to be more than one tour
There is definitely more than one tour
No, the answer is incorrect.
Score: 0
Accepted Answers:
I could not find a tour
No one can find a tour

15) For the above problem assume that the edge cost is equal to the Euclidean distance between the two nodes. Then 1 point

the Nearest Neighbour algorithm finds a tour

the Nearest Neighbour algorithm finds an optimal tour
the Greedy algorithm finds an optimal tour
None of the above
No, the answer is incorrect.
Score: 0
Accepted Answers:
None of the above

16) Select the correct statements 1 point

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

Heuristic function gives an estimate of the distance between a node and its nearest goal node
Heuristic function gives the actual distance between a node and its nearest goal node
Heuristic search always finds the optimal solution
Heuristic search is goal directed
No, the answer is incorrect.
Score: 0
Accepted Answers:
Heuristic function gives an estimate of the distance between a node and its nearest goal node
Heuristic search is goal directed

17) Given a finite state space or a finite solution space, which of these algorithms will always find a path/solution if one exists? 1 point

Depth First Search

Breadth First Search
Best First Search
Beam Search
Hill Climbing
Variable Neighbourhood Descent
Tabu Search
No, the answer is incorrect.
Score: 0
Accepted Answers:
Depth First Search
Breadth First Search
Best First Search

18) Working with the 2-City-Exchange or the 2-Edge-Exchange operator means that: 1 point

one is using a Constructive method to solve the TSP

one is searching for the solution in the State Space
one is using a Perturbative method to solve the TSP
one is searching for the solution in the Solution Space
No, the answer is incorrect.
Score: 0
Accepted Answers:
one is using a Perturbative method to solve the TSP
one is searching for the solution in the Solution Space

19) The Iterated Hill Climbing algorithm 1 point

works only for planning problems

works only for configuration problems
can work for both planning and configuration problems
is one of the approaches for State Space Search
is one of the approaches for Solution Space Search
No, the answer is incorrect.
Score: 0
Accepted Answers:
works only for configuration problems
is one of the approaches for Solution Space Search

20) In Week 3 lecture on "The Traveling Salesman Problem" a web resource for TSP (http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/) was 1 point
provided. Which of the following types of problems are supported/discussed in that site?

Hamiltonian cycle problem (HCP)

Symmetric traveling salesman problem (TSP)
Asymmetric traveling salesman problem (ATSP)
Sequential ordering problem (SOP)
Capacitated vehicle routing problem (CVRP)
No, the answer is incorrect.
Score: 0
Accepted Answers:
Hamiltonian cycle problem (HCP)
Symmetric traveling salesman problem (TSP)
Asymmetric traveling salesman problem (ATSP)
Sequential ordering problem (SOP)
Capacitated vehicle routing problem (CVRP)

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

https://onlinecourses.nptel.ac.in/noc20_cs81/unit?unit=19&assessment=194 5/5