A friend of yours gave you a map of UK, but encoded as a json file: UK_cities.json. The file encodes all the roads between major cities of the UK with their length of the road (in km). After numerous arguments, you both decided to go from London to Aberdeen. Although you would like to go there while visiting as many cities as possible, neither you nor your friend can afford the time! You are then trying to reach Aberdeen from London taking the shortest path (the total driving distance).

Part (a) Following the UCS algorithm, manually execute it for three iterations for this problem. As a reminder, the pseudo-code of the UCS is provided in Figure 1, which matches Figure 3.13 in the textbook (3rd edition).

• By iteration, we are referring to the outer "loop". So, in your trace, at least three nodes should be selected for expansion.
• In particular, you should provide (only) the content of the following variables, with the following specific data structure:
(i) the "frontier ": a queue of "nodes" ordered by their path-cost
(ii) the "explored": a set of "states"
• You should represent each "node" in the frontier as a tuple of the following information: ("state", "path-cost", "best-path-to-reach-that-state"). Note: the "state" in our problem is just the name of the city you are at! The "path-cost" is just a positive real number; and the "best-path-to-reach-that-state" is a list of states starting from the initial state to that node's state.
• For the trace, you should provide only one value per each line. Write doom only the new value each time any of the above two variables change. The order definitely matters.
• If you encounter any tie-breaking situation in the executing, e.g. in adding the nodes to the frontier, go with the alphabetical (lexicographical) order based on the name of the city.
• No explanation or comments are necessary. For instance, you don't even need to tell which line /part of the pseudo-code was responsible for an update. We only check whether the trace is correct (including the order of updates).

Part (b) Implement the UCS for this problem. Run it with the provided data. You don't need to include the code in your report (you submit it separately). Instead:
(b-1) Provide the optimal path found by the algorithm (both the path and its length); (b-2) Make the code print the trace (in the same format as requested in part (a) but only provide the last two iterations (of the outer loop) in your report.

Part (c) Suppose both you and your friend are environmentally aware. So you would like to find the path that has the lowest overall cost, which is the sum of the overall driving time plus the overall cost of the air pollution due to your driving.

Here are the details:

• You are free to choose your driving speed on each road of the path (but assume that you don't change your speed on a given road). So e.g. if you choose to drive at 40 km/h on the road between London to Birmingham, you maintain that speed on this road. But you are free to choose a different speed on the next road, etc.).

• If you drive at speed v km/h (on any road), you are responsible for an air pollution cost of (0.00001v²) units per hour.

Using your answer to the previous part, provide the best path in this scenario (both the optimal cost and the path). Again, you don't need to provide the code in your report, but you need to briefly explain your approach.

Part (d) ((bonus)) Now, for a bonus 10 points!, suppose you have rented a super-car with the maximum speed of 300 km/h with the rental fee of 100 units per hour. Suppose you have no regard for the environment! Moreover:

• As in the previous part, you can choose your driving speed per each road.

• However: suppose each road now has a speed-limit. For simplicity, assume that the speed limit of a road is the same as the value provided for the length of that road in the json file.

• On each road, you can even choose to go over the speed limit! However, there is a likelihood that you get caught on a speed-camera and get a fine of 1000 units. In particular, if you drive on a road with speed limit of v_lim at speed v, then the likelihood (i.e., probability) of getting the fine is as follows:

1-e^-(v-v_lim),                        if v > v_lim      

0,                               if v ≤ v_lim

• You may only be fined at most once on a given road, but fines on different roads accumulate.

Using your UCS code, find the best path in this problem, assuming the overall cost is the sum of the car rental fee plus the total (likely) fines.

Attachment:- work problem.rar