Answer only 3.3 please. you need matlab for this. 3.31, Logistics: Route Planning Suppose we have a

Answer only 3.3 please. you need matlab for this.

Transcribed Image Text:

3.31, Logistics: Route Planning Suppose we have a business operating in six cities around the Pacific Rim: San Diego, San Francisco, Tokyo, Shanghai, Manila, and Honolulu. We are interested in counting the number of ways we can travel from one city to another with at most n stopovers. We look up all the direct flights and put them in a table: Destination San Diego San Francisco San Francisco San Diego, Tokyo, Shanghai, Manila, Honolulu Tokyo San Francisco, Shanghai, Manila Shanghai San Diego, San Francisco, Tokyo, Manila Manila Tokyo, Shanghai, Honolulu Honolulu San Francisco, Shanghai, Manila Let's say we want to get from San Diego to Manila with at most three stops along the way. For example, the trip going from San Diego through San Francisco, then Honolulu, then Shanghai, then Manila is a trip with exactly three stops.. Exercise 3.2 List all possible ways to get from San Diego to Manila with exactly three stops. Doing that last exercise by hand is a pain because there are so many cases to check, and this is a relatively simple example. If we want to do this efficiently, linear algebra is the perfect tool. We'll start by encoding the data from our table into what's called an adjacency matrix. The first step is to number our cities in the order they are listed: San Diego is 1, San Francisco is 2, and so on. We now determine the entries of our adjacency matrix, which we will call A, using the following rule: if there is a flight from city i to city, then the entry A, is set to 1. Otherwise, we set that entry to 0. We will also set all of the diagonal entries to 0. since you can't take a flight from a city to itself. This procedure gives us the following matrix A: 010000 101 111 010110 111010 001101 010110 What's neat about this is that the powers of A have useful information too. For example, take the entry (A) (ie, the entry of A in the third row and sixth column). We compute this as (A)6 AA+AA+AA+AA+AA + A6A6 Let's look at the terms here: AAs is 1 if and only if both A and As are 1. This means we get a 1 for the th term if and only if we can fly from Tokyo (city 3) to city k and from city k to Honolulu (city 6). Thus, (A) counts the number of ways to fly from Tokyo to Honolulu with exactly one stop. Similar reasoning shows that the number of ways of flying from city / to city with exactly n stops is just (A) Exercise 3.3 a. Enter the above adjacency matrix A into MATLAB. By looking at the entry of A in the first row and the fifth column, find the number of ways to get from San Diego to Manila with exactly three stops. Does your answer here agree with your explicit count in the previous exercise? If not, find the missing trips. Include your input and output in your document. b. Now use MATLAB find the number of ways to get from San Francisco to Tokyo with at most four stops. (This is not the same as finding the number of ways with exactly four stops!) Include all of your commands and output in your write-up. Note 3.1: As you may have realized, the method we've just used counts silly trips like San Francisco - Shanghai San Francisco - Shanghai as a trip with two stops. User beware! 3.31, Logistics: Route Planning Suppose we have a business operating in six cities around the Pacific Rim: San Diego, San Francisco, Tokyo, Shanghai, Manila, and Honolulu. We are interested in counting the number of ways we can travel from one city to another with at most n stopovers. We look up all the direct flights and put them in a table: Destination San Diego San Francisco San Francisco San Diego, Tokyo, Shanghai, Manila, Honolulu Tokyo San Francisco, Shanghai, Manila Shanghai San Diego, San Francisco, Tokyo, Manila Manila Tokyo, Shanghai, Honolulu Honolulu San Francisco, Shanghai, Manila Let's say we want to get from San Diego to Manila with at most three stops along the way. For example, the trip going from San Diego through San Francisco, then Honolulu, then Shanghai, then Manila is a trip with exactly three stops.. Exercise 3.2 List all possible ways to get from San Diego to Manila with exactly three stops. Doing that last exercise by hand is a pain because there are so many cases to check, and this is a relatively simple example. If we want to do this efficiently, linear algebra is the perfect tool. We'll start by encoding the data from our table into what's called an adjacency matrix. The first step is to number our cities in the order they are listed: San Diego is 1, San Francisco is 2, and so on. We now determine the entries of our adjacency matrix, which we will call A, using the following rule: if there is a flight from city i to city, then the entry A, is set to 1. Otherwise, we set that entry to 0. We will also set all of the diagonal entries to 0. since you can't take a flight from a city to itself. This procedure gives us the following matrix A: 010000 101 111 010110 111010 001101 010110 What's neat about this is that the powers of A have useful information too. For example, take the entry (A) (ie, the entry of A in the third row and sixth column). We compute this as (A)6 AA+AA+AA+AA+AA + A6A6 Let's look at the terms here: AAs is 1 if and only if both A and As are 1. This means we get a 1 for the th term if and only if we can fly from Tokyo (city 3) to city k and from city k to Honolulu (city 6). Thus, (A) counts the number of ways to fly from Tokyo to Honolulu with exactly one stop. Similar reasoning shows that the number of ways of flying from city / to city with exactly n stops is just (A) Exercise 3.3 a. Enter the above adjacency matrix A into MATLAB. By looking at the entry of A in the first row and the fifth column, find the number of ways to get from San Diego to Manila with exactly three stops. Does your answer here agree with your explicit count in the previous exercise? If not, find the missing trips. Include your input and output in your document. b. Now use MATLAB find the number of ways to get from San Francisco to Tokyo with at most four stops. (This is not the same as finding the number of ways with exactly four stops!) Include all of your commands and output in your write-up. Note 3.1: As you may have realized, the method we've just used counts silly trips like San Francisco - Shanghai San Francisco - Shanghai as a trip with two stops. User beware!

Answer rating: 100% (QA)

33 a Program code screen shot Sample Output Program code to copy define the Adjacency matrix as specified in the question that is each row is corresponds to the source city and each column specifies t... View the full answer