A friend of yours gave you a map of UK, but encoded as a jsor. file: UK_cities. jso:. The file encodes all the roads between major cities of the UK with their length of the road

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Question 1: Let’s Travel! (Uniform Cost Search)

A friend of yours gave you a map of UK, but encoded as a jsor. file: UK_cities. jso:.

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 arc then trying to reach Aberdeen from London

taking the shortest path (the total driving distance).

(a) (15 points) Following the UCS algorithm, nianually execute it for three iterations for

this problem. As a reminder, the pseudo-code of the UCS is provided in Figure [

which matches Figure 3.13 in the textbook (3rd edition).

function UNIIORM-COST-SEARCI*prvbkm) returns a solution, or tailure

node — a mdc with STATE = pmblem.INITIAL-STATI. PATH-COST —0

frontier-y a pñority queue ordered by PATtI-CosT, with viaJe as the only element

explored .— an empty set

loop do

if IiMPTY?(frnntwr) then return failure

n ode P0P( frontier) 1 chooses the lowest-cost node in fronhierl

if pro bkrn GOAL-TEST( ,IOdi-.STATE) then return S0LUTI0N( viaJe)

add node STATE lo i-xplor#d

fOr each action in pn,&lcin.AcTIONSC r,odc.STATE) do

child — CHILI)-NODEt pwbkm. ,iode. action)

if ChSId,STATE is n in explored or frvnitwr then

frontier — 1551 RT(chdd,fronlwr)

eke If child.STATE is in frontier with higher PATtI-COST then

replace that fwnlwr node with child

Figure 1: Pseudo-code for the USC (Uniform-Cost Search) algorithm on a graph. This is bor

rowed from II, Fig. 3.131.

. By iteration, we arc 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 folIos’ing 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 infor

mation: (“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 pos

itive 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 down only
  
  

the new value each time any of the above two variables change. The order defi

nitely matters.

. 11 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).

. An example few first steps of the trace with the above description would be as

follows:

1 frontier = [(‘london’, 0, l’london’I)l

2 explored U

3 frontier = [1

4 explored = llondon’l

5 frontier = [( birmingham’, 110,1 london’, ‘birmingham 1)J



(b) (10 points) 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 ttw iterations (of the outer loop) in your report.

Note: you don’t have to follow the provided pseudo-code in your implementation

necessarily. However, if the logic of your code deviates significantly from this version,

then you need to provide your pseudo-code as vell.

(c) (10 points) 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 tinte plus the overall cost of the air pollution due to your driving.

I-lore 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 40km/hon the road between London to Birmingham, you maintain that speed

on this road. Hut you are free to choose a different speed on the next road, etc.).

. If you drive at speed r km/h (on any road), you are responsible for an air pollu

tion cost of (0.(X)00 le2) units ¡r 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.

(d) (10 points (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 simplicit assume that

the speed limit of a road is the same as the value provided for the length of that

road in the jso: file.

. On cadi 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 r at speed r’, then the

likelihood (i.e., probability) of getting the fine is as follows:

Ji — “‘“ . if t’ > 1’Iirn

0. if t’  •‘iárn

. 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.

UK_cities.json (File)

 

{

"aberdeen": {

"aberystwyth": {"weight":427},

"edinburgh":  {"weight":115},

"penzance":   {"weight":663},

"portsmouth": {"weight":550},

"sheffield": {"weight":338},

"swansea":     {"weight":502},

"york":         {"weight":299}

},

"aberystwyth": {

"brighton":     {"weight":249} ,

"bristol":      {"weight":121} ,

"carlisle":    {"weight":219} ,

"dover":        {"weight":284} ,

"newcastle": {"weight":254} ,

"nottingham": {"weight":154} ,

"oxford":      {"weight":156} ,

"penzance": {"weight":304} ,

"sheffield":   {"weight":154} ,

"swansea":     {"weight":75} ,

"york":         {"weight":190}

},

"birmingham": {

"brighton":     {"weight":159},

"bristol":       {"weight":86},

"cambridge": {"weight":97},

"cardiff":     {"weight":100},

"carlisle":   {"weight":198},

"portsmouth": {"weight":141},

"sheffield": {"weight":75},

"swansea":     {"weight":125},

"york": {"weight":125},

"london": {"weight":110}

},

"brighton": {

"bristol":      {"weight":136},

"cambridge": {"weight":106},

"cardiff":     {"weight":183},

"carlisle":   {"weight":354},

"dover":         {"weight":81},

"nottingham": {"weight":178},

"oxford":       {"weight":96},

"penzance":   {"weight":277},

"portsmouth":  {"weight":49},

"sheffield": {"weight":216},

"swansea":     {"weight":236},

"york":         {"weight":250},

"london":       {"weight":52}

},

"bristol": {

"cambridge": {"weight":151},

"cardiff":      {"weight":44},

"carlisle":   {"weight":276},

"dover":        {"weight":187},

"edinburgh": {"weight":369},

"exeter":        {"weight":76},

"glasgow":      {"weight":370},

 

"hull":         {"weight":206},

"leeds":        {"weight":195},

"swansea":      {"weight":89},

"york":         {"weight":211},

"london":      {"weight":116}

},

"cambridge":

{

"cardiff":     {"weight":177},

"carlisle":   {"weight":260},

"dover":        {"weight":125},

"exeter":       {"weight":216},

"glasgow":      {"weight":354},

"hull":         {"weight":124},

"portsmouth": {"weight":126},

"sheffield": {"weight":116},

"swansea":     {"weight":216},

"york":         {"weight":149},

"london":       {"weight":54}

},

"cardiff":

{

"carlisle":     {"weight":277},

"dover":        {"weight":232},

"edinburgh": {"weight":370},

"exeter":       {"weight":119},

"glasgow":      {"weight":371},

"hull":         {"weight":227},

"leeds":        {"weight":209},

"sheffield":  {"weight":175},

"swansea":      {"weight":45},

"york":         {"weight":232},

"london":      {"weight":161}

},

"carlisle":{

"dover":        {"weight":373},

"edinburgh": {"weight":93},

"exeter":       {"weight":352},

"glasgow":       {"weight":94},

"hull":         {"weight":149},

"manchester": {"weight":120},

"newcastle": {"weight":58},

"nottingham": {"weight":187},

"york":         {"weight":112},

"london":      {"weight":302}

},

"dover":

{

"exeter":       {"weight":246},

"glasgow":      {"weight":467},

"hull":         {"weight":243},

"leeds":        {"weight":269},

"portsmouth": {"weight":130},

"sheffield": {"weight":235},

"swansea":     {"weight":271},

"york":         {"weight":269},

"london":       {"weight":71}

},

"edinburgh":

{

 

"exeter":       {"weight":445},

"glasgow":       {"weight":44},

"hull":         {"weight":221},

"leeds":        {"weight":195},

"liverpool": {"weight":211},

"manchester": {"weight":213},

"newcastle": {"weight":104},

"nottingham": {"weight":258},

"york":         {"weight":184}

},

"exeter":

{

"glasgow":      {"weight":446},

"hull":         {"weight":282},

"leeds":        {"weight":271},

"liverpool": {"weight":239},

"manchester": {"weight":237},

"newcastle": {"weight":360},

"nottingham": {"weight":217},

"oxford":      {"weight":136},

"london":      {"weight":172}

},

"glasgow":

{

"hull":         {"weight":243},

"leeds":        {"weight":211},

"liverpool": {"weight":212},

"manchester": {"weight":214},

"newcastle": {"weight":148},

"nottingham": {"weight":281},

"oxford":      {"weight":355},

"london":      {"weight":396}

},

"hull":{

"leeds":         {"weight":58},

"liverpool": {"weight":122},

"manchester":  {"weight":90},

"newcastle":  {"weight":117},

"nottingham":  {"weight":90},

"oxford":      {"weight":164},

"london":      {"weight":172}

},

"leeds":

{

"liverpool": {"weight":73},

"manchester": {"weight":41},

"newcastle": {"weight":89},

"nottingham":  {"weight":72},

"swansea":     {"weight":229},

"york":          {"weight":23},

"london":      {"weight":198}

},

"liverpool":

{

"manchester":  {"weight":35},

"newcastle":  {"weight":162},

"nottingham": {"weight":100},

"swansea":     {"weight":166},

"york":          {"weight":96},

"london":      {"weight":198}

 

},

"manchester":

{

"newcastle":  {"weight":130},

"nottingham":  {"weight":71},

"oxford":      {"weight":143},

"penzance": {"weight":344},

"portsmouth": {"weight":221},

"sheffield": {"weight":38},

"swansea":     {"weight":188},

"york":          {"weight":64}

},

"newcastle":

{

"nottingham": {"weight":155},

"oxford":      {"weight":253},

"penzance": {"weight":468},

"portsmouth": {"weight":331},

"sheffield": {"weight":123},

"swansea":     {"weight":318},

"york":          {"weight":80}

},

"nottingham":

{

"oxford":       {"weight":98},

"penzance": {"weight":322},

"portsmouth": {"weight":176},

"sheffield": {"weight":38},

"swansea":     {"weight":173},

"york":          {"weight":80}

},

"oxford":

{

"penzance":   {"weight":250},

"portsmouth":  {"weight":78},

"sheffield": {"weight":136},

"swansea":     {"weight":145},

"york":         {"weight":178},

"london":       {"weight":57}

},

"penzance":

{

"portsmouth": {"weight":242},

"sheffield": {"weight":348},

"swansea":     {"weight":273},

"york":         {"weight":398}

},

"portsmouth":

{

"sheffield": {"weight":214},

"york":         {"weight":256}

},

"sheffield":

{

"swansea":     {"weight":196}

},

"swansea":

{

"york":         {"weight":248}

}

 

}

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of