User Account

All Pages

Provide the optimal path found by the algorithm

Assignment Help JAVA Programming
Reference no: EM132469892

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.00001v2) 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 vlim at speed v, then the likelihood (i.e., probability) of getting the fine is as follows:

1-e-(v-vlim),                        if v > vlim      

0,                               if v ≤ vlim

• 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

Reference no: EM132469892

Questions Cloud

Evidence to maintain your ahpra registration : Identity 1 mandatory standards that you will need to evidence to maintain your AHPRA registration and provide an assessment of your knowledge
Explain financial ratios would be applicable to company : Explain which financial ratios would be applicable to the company."Users of financial statements use several ratios to evaluate a company's performance.
Determine dividend will be paid to the common stockholders : Determine How much of the 2018 dividend will be paid to the common stockholders assuming the preferred stock is noncumulative?
How much dividend paid to preferred stockholders : Determine How much of the 2016 dividend will be paid to the preferred stockholders assuming the preferred stock is noncumulative?
Provide the optimal path found by the algorithm : Provide the optimal path found by the algorithm - Make the code print the trace (in the same format as requested in part (a) but only provide
Identify a research project as being an evidence : How would you identify a research project as being an evidence based intervention project versus the creation of knowledge in a nursing research project?
Determine how much loss on the retirement of the bonds : Determine How much was the gain or loss on the retirement of the bonds? On March 31, 2014, Bundy Corporation retired $10,000,000 of bonds
Determine possible nursing diagnoses : How does knowing the patient's medical diagnoses help you determine possible nursing diagnoses?
Determine possible nursing diagnoses : How does knowing the patient's medical diagnoses help you determine possible nursing diagnoses?

Reviews

Write a Review

JAVA Programming Questions & Answers

  Java servlet uses doget to return markup document

Write down Java servlet which uses doGet to return markup document which provides your name, e-mail address, and mailing address along with a brief autobiography.

  Create a dictionary based on the lower ascii characters

Create a Dictionary based on the lower ASCII characters 32 (Blank) through 128 (Euro). This will create a binary tree with 96 nodes

  Create a flowchart to represent the push and pop operations

Create a flowchart to represent the Push and Pop operations for a Stack based on a linked list data structure.

  Develop a java application

Your task is to develop a Java Application that allows the user to read travel booking data from a text file, save data in a file, display data in a text area, sort data by booking name and search data by booking name.

  Convert a binarystring into a decimal number

Write the bin2Dec(String binaryString)method to convert a binarystring into a decimal number - Implement to throw a NumberFormatException

  What situations would not warrant the use of an array

In what programming situations would the use of an array be beneficial - What situations would not warrant the use of an array?

  Write method called median that accepts an array of integer

Write a method called median that accepts an array of integers as its parameter and returns the median of the numbers in the array.

  Suppose that a variable a is declared as int java eclipse

Suppose that a variable a is declared as int a = 2147483647 (or equivalently,Integer.MAX_VALUE). What do each of the following print. System.out.println(a);

  Create a world class that contains a 2d array

You have to create a world class that contains a 2d array then create an abstract class called organism that contains move() method the organism should move randomly one step at the time.

  Create a class called invoice that a hardware store may use

Create a class called Invoice that a hardware store may use to represent an invoice for an item sold at the store.  The class should have four (4) instance variables: part number : string and part description : string (what is the item)

  Write a program that evaluates the day of the week for new

write a program that evaluates the day of the week for new years day in the year 3000. to do this you must create your

  Describe the project requirements and other assumptions

Summarize the project requirements and other assumptions (i.e., budget, human resources, workload, environmental dependencies, etc.). Define a work breakdown structure and describe the methodology behind constructing one

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

Submit Assignment

Academics

Major Subjects

Majors

Get In Touch

whatsapp: +1-415-670-9521

Phone: +1-415-670-9521

Email: [email protected]

TERMS & POLICIES

HELP & SUPPORT

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd