Compute the shortest path between two cities

Assignment Help Basic Computer Science

Reference no: EM131213559

Flight planning. This exercise uses the relation class implemented in section 9.6. Fly By Night airlines asks you to write a program that can plan flights for its passengers. We are given a database containing a set of facts of the form

The first two arguments represent a pair of cities served by Fly By Night airlines, the third argument is the great circle distance between the two cities, and the fourth argument is a boolean that is true if there is a direct flight between the two cities and false otherwise. For this exercise, do the following:

(a) Write a planner that, given a source city and a destination city, returns a path between the two cities that is noncircular, i.e., no city appears twice in the path. Define the planner as a function {Plan City1 City2} that returns a pair Distance#Path, where Distance is the total distance flown on the path from City1 to City2 and Path is a list of cities representing the path from City1 to City2.The function should be nondeterministic so that Solve can use it to generate different plans.

(b) Use the above planner to compute the shortest path between two cities. Define a function {Best Plan City1 City2} that returns the shortest path.

(c) The implementation of Best Plan will enumerate all solutions to find the best one. This can be very costly in time. To reduce the time, we can use a heuristic called best first. Whenever we need to choose a city, we choose first a connected city that has the shortest direct distance to the destination. Define a function {Good Plan City1 City2} that uses this heuristic.

Reference no: EM131213559

Questions Cloud

Explain your position in a clear and well-argued essay : Assume that you are Mr. Hegarty, the CEO of Mebel-Doran. What will you do now? What avenues are open to you? Explain your position in a clear and well-argued essay.

Attempted to remain anonymous : Outline a scenario in which you might be acting ethically but might still want to remain anonymous while using the Internet. Identify two approaches someone might take to learn your identity even if you attempted to remain anonymous.

Whether covered interest parity holds for one year : Determine whether covered interest parity holds for one-year government bonds issued by the U.S. and British governments.

Reduce the effect they have on the phosphorus cycle : What are some ways that humans can reduce the effect they have on the phosphorus cycle?

Compute the shortest path between two cities : Use the above planner to compute the shortest path between two cities. Define a function {Best Plan City1 City2} that returns the shortest path.

Construct a projected balance sheet and income statement : Sales for 2016 were $350 million, while net income for the year was $10.5 million. Construct a projected Balance Sheet and Income Statement for the year-ended 12/31/2016.

Identify key metrics that you propose for your organization : Using the balanced scorecard approach as detailed in Chapter 14 (Figure 14.1), identify four key metrics that you would propose for your organization's supply management system and how you propose to measure those 4 key metrics in your supply chai..

Explain the nature of the exchange rate risk : Explain the nature of the exchange-rate risk for each of the given, from the perspective of the U.S. firm or person.

Desirable properties of the relational computation model : For this exercise, investigate how to remove this restriction while maintaining the desirable properties of the relational computation model, i.e., its simple logical semantics and efficient implementation.

User Account

All Pages