artificial intelligence, detail solution needed
Task 6 Max: (4308: 10 Points EC, 5360: 10 Points) 6 | 10 | - || | | , 10 23 | 11 | 12 | 13 14 | 16 | 17 | 18 | 19 | 20 Figure 4. An example of a start state (left) and the goal state (right) for the 24-puzzle. The 24-puzzle is an extension of the 8-puzzle, where there are 24 pieces, labeled with the numbers from 1 to 24, placed on a 5x5 grid. At each move, a tile can move up, down, left, or right, but only if the destination location is currently empty. For example, in the start state shown above, there are three legal moves: the 12 can move down, the 22 can move left, or the 19 can move right. The goal is to achieve the goal state shown above. The cost of a solution is the number of moves it takes to achieve that solution. For some initial states, the shortest solution is longer than 100 moves. For all initial states, the shortest solution is at most 208 moves. An additional constraint is that, in any implementation, storing a search node takes IKB of memory. Consider general tree search using the stategies of breadth-first search, depth-first search, iterative deepening search and uniform cost search. (a): Which (if any), among those methods, can guarantee that you will never need more than 100KB of memory to store search nodes? Briefly justify your answer. (b): Which (if any), among those methods, can guarantee that you will never need more than 1000KB of memory to store search nodes? Briefly justify your answer. Hint: Consider the upper and lower bounds of the amount of memory required Task 6 Max: (4308: 10 Points EC, 5360: 10 Points) 6 | 10 | - || | | , 10 23 | 11 | 12 | 13 14 | 16 | 17 | 18 | 19 | 20 Figure 4. An example of a start state (left) and the goal state (right) for the 24-puzzle. The 24-puzzle is an extension of the 8-puzzle, where there are 24 pieces, labeled with the numbers from 1 to 24, placed on a 5x5 grid. At each move, a tile can move up, down, left, or right, but only if the destination location is currently empty. For example, in the start state shown above, there are three legal moves: the 12 can move down, the 22 can move left, or the 19 can move right. The goal is to achieve the goal state shown above. The cost of a solution is the number of moves it takes to achieve that solution. For some initial states, the shortest solution is longer than 100 moves. For all initial states, the shortest solution is at most 208 moves. An additional constraint is that, in any implementation, storing a search node takes IKB of memory. Consider general tree search using the stategies of breadth-first search, depth-first search, iterative deepening search and uniform cost search. (a): Which (if any), among those methods, can guarantee that you will never need more than 100KB of memory to store search nodes? Briefly justify your answer. (b): Which (if any), among those methods, can guarantee that you will never need more than 1000KB of memory to store search nodes? Briefly justify your answer. Hint: Consider the upper and lower bounds of the amount of memory required
