Itinerary

The questions below are due on Friday May 10, 2019; 05:00:00 PM.
 
Music for this Problem

Our goal in these exercises will be to make a flight search engine...just like Travelocity only smaller. A flight is specified with a starting city and time and an ending city and time. Cities are represented as strings and times as integers.

We want to be able to answer queries that are specified with a starting city, starting time, final destination city and deadline time. The objective is to find a sequence of flights, starting in the starting city, leaving sometime at or after the starting time, and arriving at the final destination before (or at) the deadline.

We will formulate it as a search problem.

1. What is a good choice of state in this problem?

   -- Current city Current city and destination city Current city and current time Current city and deadline

   

2. Imagine that we have a procedure flight_successors, that returns the successors of a state in this domain.

Define a procedure find_itinerary that returns a plan, in the form of a sequence of (city, time) pairs, that represents a legal sequence of flights from start_city to end_city.

The search procedure from lib601 (see the lib601 documentation for details) has been defined for you, so you may make use of it in your code.

Here is the skeleton of a Flight class:

class Flight:
    def __init__(self, start_city, start_time, end_city, end_time):
        self.start_city = start_city
        self.start_time = start_time
        self.end_city = end_city
        self.end_time = end_time

    def __str__(self):
        return str((self.start_city, self.start_time))+' -> '+ str((self.end_city, self.end_time))
    __repr__ = __str__

Here is a database of fights:

flightDB = [Flight('Rome', 1, 'Paris', 4),
            Flight('Rome', 3, 'Madrid', 5),
            Flight('Rome', 5, 'Istanbul', 10),
            Flight('Paris', 2, 'London', 4),
            Flight('Paris', 5, 'Oslo', 7),
            Flight('Paris', 5, 'Istanbul', 9),
            Flight('Madrid', 7, 'Rabat', 10),
            Flight('Madrid', 8, 'London', 10),
            Flight('Istanbul', 10, 'Constantinople', 10)]

3) Write a method matches contained within the Flight class, that takes a pair (city,time) as an argument and returns a boolean based on whether or not the city and time specified "match" those of the flight, in the sense that the flight leaves from the same city, at a time later than time.

4. Define the procedure flight_successors. It should return a (possibly empty) list of tuples, representing the states that can legally be reached from this state in a single flight, given the available flights in flightDB.

Thinking Further

Ben Bitdiddle wants to find a way to get from Rome at time 1 to Istanbul at the earliest time possible. He proposes to start with a deadline of 1, and then increase it, one-by-one, calling `find_itinerary` each time, until it successfully finds a path.

Will this strategy find the path that arrives soonest, given that we start at time 1?

Imagine that if we use this strategy to solve a problem whose shortest path is length 100, it takes an amount x of calls on find_itinerary to solve. Roughly how many calls to find_itinerary will it take to solve a problem whose shortest path is length 200?

Write a procedure find_shortest_itinerary that implements this strategy.

Your procedure should take two strings, representing a starting location and an ending location, and should return a list of (location,time) tuples representing the shortest path between the two locations. You may assume that there is at least one path connecting the two locations.

Our implementation of the find_itinerary procedure has been included for you; you do not need to paste your own find_itinerary definition below.

As an additional challenge, try to minimize the number of times your procedure calls find_itinerary!