MauryaHub PYQ Practice

cs3003_2024T1_Q1_NA.pdf

AI: Search Methods for Problem Solving · Quiz 1 · Jan 2024

← Course papers · Start practice / exam

Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.

Question 21 MCQ · 0.0 marks

[[IMAGE:5f00d1b7406c9b78_2_0]]
Source diagram or notation
  1. Printed graph sheets were provided to me.`
  2. Printed graph sheets were not provided to me.
  3. I did not use graph sheets.

A published solution is not available for this question yet.

Question 22 MCQ · 1.0 marks

**STATE SPACE** One needs to count the number of nodes visited in each cycle of DFID __________ .
  1. to compute the complexity of search
  2. to make sure that the path returned is the shortest
  3. to prevent the algorithm from getting into an infinite loop on an INFINITE graph when a goal node exists in the connected component
  4. to prevent the algorithm from getting into an infinite loop on a FINITE graph when the goal node does not exist in the connected component

A published solution is not available for this question yet.

Question 23 MCQ · 1.0 marks

**STATE SPACE** In the Ant Colony Optimisation algorithm for solving the TSP __________ .
  1. all the ants in the colony start from the same start city and then go in different directions
  2. all ants construct the solution using a collaborative filtering approach
  3. each ant constructs a tour independently
  4. each ant constructs a tour using follow the leader principle

A published solution is not available for this question yet.

Question 24 MSQ · 2.0 marks

**STATE SPACE** [[IMAGE:5f00d1b7406c9b78_4_1]]
Source diagram or notation
  1. (13,NIL,2)
  2. (NIL,3,21)
  3. (1,3,2)
  4. (NIL,NIL,123)

A published solution is not available for this question yet.

Question 25 SHORT_TEXT · 1.0 marks

**SEARCH** The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by either two-way edges (shown as undirected edges) or one- way edges (shown with one arrowhead). Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists. Use Manhattan distance when needed. [[IMAGE:5f00d1b7406c9b78_6_2]] When we say a node is inspected/expanded/refined it means: the node is picked up from OPEN, and goal test is called, if goal test fails then MoveGen is called and depending on the algorithm the neighbours are selectively placed in OPEN. Based on the above data, answer the given subquestions.
List the first 4 nodes inspected by Depth First Search. 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. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. **Answer Format: S,X,Y,Z**
Source diagram or notation

    A published solution is not available for this question yet.

    Question 26 SHORT_TEXT · 1.0 marks

    **SEARCH** The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by either two-way edges (shown as undirected edges) or one- way edges (shown with one arrowhead). Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists. Use Manhattan distance when needed. [[IMAGE:5f00d1b7406c9b78_6_2]] When we say a node is inspected/expanded/refined it means: the node is picked up from OPEN, and goal test is called, if goal test fails then MoveGen is called and depending on the algorithm the neighbours are selectively placed in OPEN. Based on the above data, answer the given subquestions.
    What is the path found by Depth First Search? Enter the path as a comma separated list of node labels. Enter NIL if there is no path. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. **Answer Format: S,X,Y,G**
    Source diagram or notation

      A published solution is not available for this question yet.

      Question 27 SHORT_TEXT · 1.0 marks

      **SEARCH** The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by either two-way edges (shown as undirected edges) or one- way edges (shown with one arrowhead). Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists. Use Manhattan distance when needed. [[IMAGE:5f00d1b7406c9b78_6_2]] When we say a node is inspected/expanded/refined it means: the node is picked up from OPEN, and goal test is called, if goal test fails then MoveGen is called and depending on the algorithm the neighbours are selectively placed in OPEN. Based on the above data, answer the given subquestions.
      List the first 4 nodes inspected by Breadth First Search. 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. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. **Answer Format: S,X,Y,Z**
      Source diagram or notation

        A published solution is not available for this question yet.

        Question 28 SHORT_TEXT · 2.0 marks

        **SEARCH** The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by either two-way edges (shown as undirected edges) or one- way edges (shown with one arrowhead). Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists. Use Manhattan distance when needed. [[IMAGE:5f00d1b7406c9b78_6_2]] When we say a node is inspected/expanded/refined it means: the node is picked up from OPEN, and goal test is called, if goal test fails then MoveGen is called and depending on the algorithm the neighbours are selectively placed in OPEN. Based on the above data, answer the given subquestions.
        What is the path found by Breadth First Search? Enter the path as a comma separated list of node labels. Enter NIL if there is no path. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. **Answer Format: S,X,Y,Z,G**
        Source diagram or notation

          A published solution is not available for this question yet.

          Question 29 SHORT_TEXT · 1.0 marks

          **SEARCH** The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by either two-way edges (shown as undirected edges) or one- way edges (shown with one arrowhead). Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists. Use Manhattan distance when needed. [[IMAGE:5f00d1b7406c9b78_6_2]] When we say a node is inspected/expanded/refined it means: the node is picked up from OPEN, and goal test is called, if goal test fails then MoveGen is called and depending on the algorithm the neighbours are selectively placed in OPEN. Based on the above data, answer the given subquestions.
          List the first 4 nodes inspected by Best First Search. 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. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. **Answer Format: S,X,Y,Z**
          Source diagram or notation

            A published solution is not available for this question yet.

            Question 30 SHORT_TEXT · 2.0 marks

            **SEARCH** The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by either two-way edges (shown as undirected edges) or one- way edges (shown with one arrowhead). Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists. Use Manhattan distance when needed. [[IMAGE:5f00d1b7406c9b78_6_2]] When we say a node is inspected/expanded/refined it means: the node is picked up from OPEN, and goal test is called, if goal test fails then MoveGen is called and depending on the algorithm the neighbours are selectively placed in OPEN. Based on the above data, answer the given subquestions.
            What is the path found by Best First Search? Enter the path as a comma separated list of node labels. Enter NIL if there is no path. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. **Answer Format: S,X,Y,Z,G**
            Source diagram or notation

              A published solution is not available for this question yet.

              Question 31 SHORT_TEXT · 1.0 marks

              **SEARCH** The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by either two-way edges (shown as undirected edges) or one- way edges (shown with one arrowhead). Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists. Use Manhattan distance when needed. [[IMAGE:5f00d1b7406c9b78_6_2]] When we say a node is inspected/expanded/refined it means: the node is picked up from OPEN, and goal test is called, if goal test fails then MoveGen is called and depending on the algorithm the neighbours are selectively placed in OPEN. Based on the above data, answer the given subquestions.
              List the first 4 nodes inspected by Hill Climbing. 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. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. **Answer Format: S,X,Y,Z**
              Source diagram or notation

                A published solution is not available for this question yet.

                Question 32 SHORT_TEXT · 1.0 marks

                **SEARCH** The figure shows a map with several locations on a grid where each tile is 1x1 in size. The locations are at grid points and are connected by either two-way edges (shown as undirected edges) or one- way edges (shown with one arrowhead). Take S as the start node and G as the goal node. The MoveGen function returns neighbours in alphabetical order. The RemoveSeen procedure removes neighbours already present in OPEN/CLOSED lists. Use Manhattan distance when needed. [[IMAGE:5f00d1b7406c9b78_6_2]] When we say a node is inspected/expanded/refined it means: the node is picked up from OPEN, and goal test is called, if goal test fails then MoveGen is called and depending on the algorithm the neighbours are selectively placed in OPEN. Based on the above data, answer the given subquestions.
                What is the path found by Hill Climbing? Enter the path as a comma separated list of node labels. Enter NIL if there is no path. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. **Answer Format: S,X,Y,Z,G**
                Source diagram or notation

                  A published solution is not available for this question yet.

                  Question 33 MSQ · 1.0 marks

                  **Genetic Algorithm** A tour of 12 cities is shown below. The edges are bi-directional. Use A,B,...,L as the reference (index) sequence to prepare tour representations. [[IMAGE:5f00d1b7406c9b78_12_3]] Based on the above data, answer the given subquestions.
                  Select the valid path representations of the tour.
                  Source diagram or notation
                  1. F,I,L,E,H,A,C,K,J,D,B,G
                  2. C,K,J,D,B,G,F,I,L,E,H,A
                  3. F,I,L,E,H,A,C,K,J,D,B,G,F
                  4. C,K,J,D,B,G,F,I,L,E,H,A,C

                  A published solution is not available for this question yet.

                  Question 34 MSQ · 1.0 marks

                  **Genetic Algorithm** A tour of 12 cities is shown below. The edges are bi-directional. Use A,B,...,L as the reference (index) sequence to prepare tour representations. [[IMAGE:5f00d1b7406c9b78_12_3]] Based on the above data, answer the given subquestions.
                  Select the valid adjacency representations of the tour.
                  Source diagram or notation
                  1. C,G,K,B,H,I,F,A,L,D,J,E
                  2. H,D,A,J,L,G,B,E,F,K,C,I
                  3. C,G,K,B,J,I,H,A,L,D,F,E
                  4. H,D,A,J,L,K,B,G,F,E,C,I

                  A published solution is not available for this question yet.

                  Question 35 MCQ · 2.0 marks

                  **Genetic Algorithm** A tour of 12 cities is shown below. The edges are bi-directional. Use A,B,...,L as the reference (index) sequence to prepare tour representations. [[IMAGE:5f00d1b7406c9b78_12_3]] Based on the above data, answer the given subquestions.
                  Convert the path representation E,A,D,C,J,L,K,F,G,I,H,B to ordinal representation.
                  Source diagram or notation
                  1. 5,1,3,2,6,7,6,2,2,3,2,1
                  2. 6,8,10,5,6,1,2,5,4,2,1,1
                  3. 5,1,3,2,3,4,3,1,2,3,2,1
                  4. 5,1,3,2,3,4,3,4,2,1,1,1

                  A published solution is not available for this question yet.

                  Question 36 SHORT_TEXT · 2.0 marks

                  **Genetic Algorithm** A tour of 12 cities is shown below. The edges are bi-directional. Use A,B,...,L as the reference (index) sequence to prepare tour representations. [[IMAGE:5f00d1b7406c9b78_12_3]] Based on the above data, answer the given subquestions.
                  [[IMAGE:5f00d1b7406c9b78_14_4]]
                  Source diagram or notationSource diagram or notation

                    A published solution is not available for this question yet.

                    Question 37 SHORT_TEXT · 1.0 marks

                    **TSP** The distance matrix for 6 cities and corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours. [[IMAGE:5f00d1b7406c9b78_15_5]] Based on the above data, answer the given subquestions.
                    Start from city E and construct a tour using Nearest Neighbour Heuristic. Enter the path representation of the tour starting from city E. Enter a comma separated list of city names. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: E,X,Y,Z
                    Source diagram or notation

                      A published solution is not available for this question yet.

                      Question 38 NAT · 1.0 marks

                      **TSP** The distance matrix for 6 cities and corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours. [[IMAGE:5f00d1b7406c9b78_15_5]] Based on the above data, answer the given subquestions.
                      What is the cost of the tour generated by Nearest Neighbour Heuristic? Enter a number. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: 17
                      Source diagram or notation

                        A published solution is not available for this question yet.

                        Question 39 SHORT_TEXT · 1.0 marks

                        **TSP** The distance matrix for 6 cities and corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours. [[IMAGE:5f00d1b7406c9b78_15_5]] Based on the above data, answer the given subquestions.
                        Construct a tour using Greedy Heuristic. Enter the path representation of the tour starting from city E. Enter a comma separated list of city names. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: E,X,Y,Z
                        Source diagram or notation

                          A published solution is not available for this question yet.

                          Question 40 NAT · 1.0 marks

                          **TSP** The distance matrix for 6 cities and corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours. [[IMAGE:5f00d1b7406c9b78_15_5]] Based on the above data, answer the given subquestions.
                          What is the cost of the tour generated by Greedy Heuristic? Enter a number. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: 17
                          Source diagram or notation

                            A published solution is not available for this question yet.

                            Question 41 SHORT_TEXT · 1.0 marks

                            **TSP** The distance matrix for 6 cities and corresponding edge costs (in sorted order) are provided below. Use this information to construct TSP tours. [[IMAGE:5f00d1b7406c9b78_15_5]] Based on the above data, answer the given subquestions.
                            Take E as the fulcrum node and compute the missing values in the savings list given below. Construct the savings tour. Enter the path representation of the tour starting from city E. [[IMAGE:5f00d1b7406c9b78_18_6]] Enter a comma separated list of city names. NO SPACES, TABS, DOTS, BRACKETS, PARENTHESIS OR UNWANTED CHARACTERS. Answer format: E,X,Y,Z
                            Source diagram or notationSource diagram or notation

                              A published solution is not available for this question yet.