Exercise 3.2 (1+1+1 marks)Consider a search problem on a square grid of size 2n + 1 (for n ∈ N). An agent is initially locatedin state sI in the grid cell with coordinates (n + 1, n + 1) and has the goal to reach state sG locatedin the grid cell with coordinates (n + 1, 1). The agent has the possibilities to move north, east,south, and west in the grid if there is a grid cell in the corresponding direction (otherwise, thecorresponding action is not applicable). We assume that the agent uses breadth-first search tocompute a solution.1 . . . n n+11 sG. . .nn+1 sI(a) What is the minimum number of search nodes that are inserted into the open list until theagent finds a solution using tree search (BFS-Tree)? Give an answer as a function of n andjustify your answer.(b) How does that answer differ when using graph search (BFS-Graph)?(c) Compare the number of search nodes that are inserted into the open list in the last searchlayer that are created completely for grids with n = 10 and n = 20 for tree search and graphsearch and discuss the results.
Question
Exercise 3.2 (1+1+1 marks)Consider a search problem on a square grid of size 2n + 1 (for n ∈ N). An agent is initially locatedin state sI in the grid cell with coordinates (n + 1, n + 1) and has the goal to reach state sG locatedin the grid cell with coordinates (n + 1, 1). The agent has the possibilities to move north, east,south, and west in the grid if there is a grid cell in the corresponding direction (otherwise, thecorresponding action is not applicable). We assume that the agent uses breadth-first search tocompute a solution.1 . . . n n+11 sG. . .nn+1 sI(a) What is the minimum number of search nodes that are inserted into the open list until theagent finds a solution using tree search (BFS-Tree)? Give an answer as a function of n andjustify your answer.(b) How does that answer differ when using graph search (BFS-Graph)?(c) Compare the number of search nodes that are inserted into the open list in the last searchlayer that are created completely for grids with n = 10 and n = 20 for tree search and graphsearch and discuss the results.
Solution
(a) The minimum number of search nodes that are inserted into the open list until the agent finds a solution using tree search (BFS-Tree) is (n+1)^2. This is because in a breadth-first search, the algorithm explores all the neighbors of a node before moving on to the next level. In this case, the agent starts at the center of the grid and needs to reach the top. The agent will explore all the cells in its current row, then all the cells in the row above, and so on, until it reaches the top. Since the grid is a square of size 2n+1, there are (n+1)^2 cells to explore.
(b) The answer differs when using graph search (BFS-Graph) because this algorithm avoids visiting the same node more than once. In this case, the agent will still start at the center of the grid and explore all the cells in its current row. However, when it moves to the row above, it will not need to explore the cells it has already visited. Therefore, the number of search nodes inserted into the open list will be less than (n+1)^2.
(c) For tree search, the number of search nodes inserted into the open list in the last search layer that are created completely for grids with n = 10 and n = 20 would be 121 and 441 respectively. This is because the number of nodes in the last layer of a tree search is equal to the square of (n+1). For graph search, the number of nodes would be less than this, because the algorithm avoids visiting the same node more than once. The exact number would depend on the specific layout of the grid and the path taken by the agent.
Similar Questions
Exercise 5.1 (1+1 marks)Execute(a) greedy best-first search (f (n) = h(n.state)) and(b) A∗ (f (n) = g(n) + h(n.state))without reopening in the state space depicted below. As heuristic, use the perfect heuristic h∗.sIs1s2 s3sg515121Describe the execution of both search algorithms with the following schema:1. expanding s10: open = ⟨s11(f = 5), s12(f = 6)⟩, closed = {s10(g = 0)}2. expanding s11: open = ⟨s13(f = 4), s12(f = 6), s16(f = 10)⟩, closed = {s10(g = 0), s11(g = 3)}. . .i. expanding si: found goal with cost xNote: This schema uses fictitious states and numbers that don’t correspond to the given state space
Exercise 5.1 (1+1 marks)Execute(a) greedy best-first search (f (n) = h(n.state)) and(b) A∗ (f (n) = g(n) + h(n.state))without reopening in the state space depicted below. As heuristic, use the perfect heuristic h∗.sIs1s2 s3sg515121Describe the execution of both search algorithms with the following schema:1. expanding s10: open = ⟨s11(f = 5), s12(f = 6)⟩, closed = {s10(g = 0)}2. expanding s11: open = ⟨s13(f = 4), s12(f = 6), s16(f = 10)⟩, closed = {s10(g = 0), s11(g = 3)}. . .i. expanding si: found goal with cost xNote: This schema uses fictitious states and numbers that don’t correspond to the given state space.E
You are given four integers sx, sy, fx, fy, and a non-negative integer t.In an infinite 2D grid, you start at the cell (sx, sy). Each second, you must move to any of its adjacent cells.Return true if you can reach cell (fx, fy) after exactly t seconds, or false otherwise.A cell's adjacent cells are the 8 cells around it that share at least one corner with it. You can visit the same cell several times.
ere are five separate sets of grid squares.Let S be the set of finite sets of grid squares which form connected shapes. We do not count squares touchingdiagonally just at a vertex as being connected. The sets a, b, c and e on the above picture are elements of S. Set dis not an element of S.Let ∼ be a binary relation on S. Say that s ∼ t if and only if t can be obtained from s by moving the whole setby some sequence of any finite number (including none) of the following moves: move horizontally left one square,move horizontally right one square, move up one square, move down one square, rotate ninety degrees clockwise(about any square).So b ∼ c in the diagram above.Show that ∼ is an equivalence relation
A problem in a search space is defined by one of this state.
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.