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.
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.
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}
}
}
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme
