y2 1 10 y5 y4 2 9 y3 3 8 yl 4 7y8 y9 5 6 776 Table 1: Current state of your marina You are working at a popular marina where a number of yachts are parked in berths. Each berth can either be vacant or have exactly one yacht parked in it. Any yacht can be parked in any berth. There is only one vacant berth in the marina. Your marina has 10 berths numbered 1 to 10 and houses 9 yachts labeled y1 to y9. Table 1 shows the current state of the marina in which 9 is the initial vacant berth. The yachts were originally assigned to the berth with the same number, yl to berth 1, y2 to berth 2 etc. Your customers are clearly misbehaving! The marina manager has asked you to put each yacht back to its originally assigned berth. You will only be able to move one boat at a time and you are not allowed to take yachts out of the marina. Also, because of some strange liability issues, you can only move boats from a berth b to a vacant berth by if one is a multiple of the other or if both are prime. Examples of legal moves Yachts from berths 1, 3, 4, 5, 6, 7, 8 and 10 can be moved into berth 2. Yachts from all other berths can be moved into berth 1. Yachts from berths 1, 2 and 5 can be moved into berth 10. Yachts from berths 1, 2, 3 and 5 can be moved into berth 7. Your Problem: You want to find a sequence of yacht-moves such that each yacht is back in its originally assigned berth. 1. [15 points) Represent the marina problem as a search problem. (a) [4 points) How would you represent a node/state? (b) (3 points] What is the goal node? (C) [4 points] What are the arcs? (a) [4 points) How many possible states are there? 2. [8 points] Write out the first two levels (counting the root as the first level) of the search tree. Also write down one subtree at level three. Only label the arcs; labeling the nodes would be too much work. 3. [5 points) What kind of uninformed search strategy would you use for this problem assuming that: all moves have the same cost, you want to minimize your work and your computer does not have much memory? Justify your answer. 4. [4 points] What is the maximum branching factor for this search problem? 5. [8 points] Using your knowledge of the branching factor and assuming that the length of the shortest path to the goal is m, what are the time and space complexity of the search strategy you chose in point 3, as a function of monly? y2 1 10 y5 y4 2 9 y3 3 8 yl 4 7y8 y9 5 6 776 Table 1: Current state of your marina You are working at a popular marina where a number of yachts are parked in berths. Each berth can either be vacant or have exactly one yacht parked in it. Any yacht can be parked in any berth. There is only one vacant berth in the marina. Your marina has 10 berths numbered 1 to 10 and houses 9 yachts labeled y1 to y9. Table 1 shows the current state of the marina in which 9 is the initial vacant berth. The yachts were originally assigned to the berth with the same number, yl to berth 1, y2 to berth 2 etc. Your customers are clearly misbehaving! The marina manager has asked you to put each yacht back to its originally assigned berth. You will only be able to move one boat at a time and you are not allowed to take yachts out of the marina. Also, because of some strange liability issues, you can only move boats from a berth b to a vacant berth by if one is a multiple of the other or if both are prime. Examples of legal moves Yachts from berths 1, 3, 4, 5, 6, 7, 8 and 10 can be moved into berth 2. Yachts from all other berths can be moved into berth 1. Yachts from berths 1, 2 and 5 can be moved into berth 10. Yachts from berths 1, 2, 3 and 5 can be moved into berth 7. Your Problem: You want to find a sequence of yacht-moves such that each yacht is back in its originally assigned berth. 1. [15 points) Represent the marina problem as a search problem. (a) [4 points) How would you represent a node/state? (b) (3 points] What is the goal node? (C) [4 points] What are the arcs? (a) [4 points) How many possible states are there? 2. [8 points] Write out the first two levels (counting the root as the first level) of the search tree. Also write down one subtree at level three. Only label the arcs; labeling the nodes would be too much work. 3. [5 points) What kind of uninformed search strategy would you use for this problem assuming that: all moves have the same cost, you want to minimize your work and your computer does not have much memory? Justify your answer. 4. [4 points] What is the maximum branching factor for this search problem? 5. [8 points] Using your knowledge of the branching factor and assuming that the length of the shortest path to the goal is m, what are the time and space complexity of the search strategy you chose in point 3, as a function of monly