NPTEL Artificial Intelligence : Search Methods For Problem solving Week 3 Assignment Answers 2024
1. In the map, start node S is the first node inspected, list the next 6 nodes (from node 2 to 7) inspected by the Breadth First Search (BFS) algorithm. List the nodes in the order they were inspected. If the algorithm terminates early then list the nodes inspected up until termination.
Enter a comma separated list of node labels.
Answer :- For Answers Click Here
2. Which node has the largest heuristic value? What is its heuristic value? Remember to use the Manhattan distance. When multiple nodes qualify then choose any one node.
Enter the node label and a heuristic value as a comma separated list.
Answer :- For Answers Click Here
3. In the map, start node S is the first node inspected, list the next 4 nodes (from node 2 to 5) inspected by the Best First Search algorithm.
Note: during inspection if multiple candidate nodes have the same estimated cost then use node labels to break the tie.
List the nodes inspected in the order they were inspected. If the algorithm terminates early then list the nodes inspected up until termination.
Enter a comma separated list of node labels.
Answer :- For Answers Click Here
4. In the map, start node S is the first node inspected, list the next 4 nodes (from node 2 to 5) inspected by Hill Climbing algorithm.
Note: during inspection if multiple nodes have the same cost then use node labels to break the tie.
List the nodes in the order they were inspected. If the algorithm terminates early then list the nodes inspected up until termination.
Enter a comma separated list of node labels.
Answer :-
5. For the given map, which of the algorithms find a path from node S to node G ?
- Depth First Search
- Breadth First Search
- Hill Climbing
- Best First Search
Answer :-
6. For the given map, try and find a TSP tour using ONLY the edges in the map. Choose the correct options.
- I could not find a tour
- No one can find a tour
- I found one tour
- There is definitely more than one tour
Answer :- Click Here
7. For the given city map, starting from S and using ONLY the given edges and using Euclidean distance as the edge cost, construct a TSP tour using the Nearest Neighbour algorithm. Use node labels to break ties.
- Nearest Neighbour algorithm fails to find a tour
- Nearest Neighbour algorithm finds a tour
- Nearest Neighbour algorithm finds an optimal tour
Answer :-
8. Consider the SAT problem with 5 variables.
F(a,b,c,d,e) = (¬a ∨ ¬c) ∧ (¬b ∨ ¬d) ∧ (b ∨ ¬e) ∧ (¬c ∨ d) ∧ (c ∨ e) ∧ (d ∨ ¬e)
Let S=”10101” be the start node, then A=”00101”, B=”11101”, C=”10001”, D=”10111” and E=”10100” are the neighbours generated by the change-one-bit MoveGen function. Use the number of clauses satisfied as the heuristic function.
Compute the heuristic values for S, A, B, C, D, E.
Enter the three heuristic values of S, B, and E, respectively, as a comma separated list.
Answer :-
9. Use the Beam Search algorithm with width=2 to solve the SAT problem. Candidate “10101” is the start node at level 1. List the two nodes in level 2 that will be placed in the beam.
Note: when multiple nodes have the same cost then use node labels to break the tie.
Enter node labels (5 bit strings) as a comma separated list in SORTED ORDER.
Answer :-
10. Continue from the previous question. Determine the two nodes in level 3 that will be placed in the beam. Enter the heuristic values of the two nodes in level 3.
When multiple nodes have the same cost then use node labels to break the tie.
Enter the heuristic values as a comma separated list in ascending order
Answer :-
11. What is the variable assignment that makes the SAT formula true? Enter the assignment (5-bit string) in the text box. If multiple assignments exist, simply pick one.
Enter a 5-bit string.
Answer :- Click Here
12. When Blind Search (DFS, BFS, DFID) looks at a node in the state space ___________ . (Mark all correct answers)
- it is interested in who the neighbours of the node are
- it is interested in whether the node is a goal node
- it is interested in knowing how close to the goal the node appears to be
- none of the above
Answer :-
13. When Heuristic Search (Best First Search, Hill Climbing) looks at a node in the state space __ . (Mark all correct answers)
- it is interested in who the neighbours of the node are
- it is interested in whether the node is a goal node
- it is interested in knowing how close to the goal the node appears to be
- none of the above
Answer :-
14. The heuristic function h(N) for the node N ______________ . (Mark all correct answers)
- is an estimate of how close N is to the start node
- is an accurate measure of how close N is to the start node
- is an estimate of how close N is to a goal node
- is an accurate measure of how close N is to a goal node
- none of the above
Answer :-
15. When a goal exists in the state space, the algorithm Hill Climbing ____________ . (Mark all correct answers)
- always finds a path to a goal for finite graphs
- always finds a path to a goal for finite graphs when the goal is in the same connected component as the start node
- always finds a path to a goal for infinite graphs
- always finds a path to a goal for infinite graphs when the goal is in the same connected component as the start node
- none of the above
Answer :- click here
16. What are the key differences between solution space search and state space search? (Mark all correct answers)
- State space search always has a start state specified. In solution space search the start state can be chosen randomly.
- Best first can be used in state space search but not in solution space search.
- Path reconstruction may be needed in state space search but is never required in solution space search.
- The SAT problem can only be solved in solution space search but not in state space search.
Answer :-
17. In which of the following search algorithms the next node visited is always better than the current node? (Mark all correct answers)
- Hill Climbing
- Iterated Hill Climbing
- Best First Search
- Tabu Search
- Simulated Annealing
Answer :-
18. Iterated Hill climbing is suitable ______________ . (Mark all correct answers)
- for planning problems
- for configuration problems
- for problems where the start node must be specified by the user
- for problems where the start node can be random
Answer :-
19. Simulated Annealing _____________ .
- begins with exploration and ends with exploration
- begins with exploitation and ends with exploration
- begins with exploration and ends with exploitation
- begins with exploitation and ends with exploitation
Answer :-
20. The Variable Neighbourhood Descent _____________. (Mark all correct answers)
- is an extension of Hill Climbing
- attempts to escape from local optima by using a different heuristic function
- attempts to escape from a local optima by using a different MoveGen function which is more dense
- sometimes allows moves against the heuristic function
Answer :- For Answers Click Here
