- Experts Keep Answering The Question By Copying A Previous Question Similar To It But It S A Completely Different Questio 1 (264.02 KiB) Viewed 36 times
Experts keep answering the question by copying a previous question similar to it but it's a completely different questio
-
answerhappygod
- Site Admin
- Posts: 899603
- Joined: Mon Aug 02, 2021 8:13 am
Experts keep answering the question by copying a previous question similar to it but it's a completely different questio
Experts keep answering the question by copying aprevious question similar to it but it's a completely differentquestion. Please can you actually answer questionsQ1-3, Q1-4 and Q1-5?
Consider N cities in the UK other than London. We want to visit the N cities efficiently using a helicopter, departing and terminating at London. As a metric of efficiency, we consider the total length of the route. We assume that we can move one city to another along the line (geodesic) that passes through the two cities by helicopter, so we always consider the straight-line distance for any pair of cities. To formulate this problem as a graph problem, we consider a weighted graph such that the node set consists of the N cities and London, the edge set consists of all the pairs of cities, and the weight of an edge is defined by the straight-line distance between the two cities. A path of a graph is called a Hamiltonian circuit if it starts and ends at the same node and passes all the other nodes exactly once. A route departing at London, visiting the N cities, and terminating at London corresponds to a Hamiltonian circuit of the graph starting at London. The total length of a route is the weight of the corresponding Hamiltonian circuit, which is defined by the sum of the weights of the edges in the circuit. Thus, our problem is equivalent to finding a small-weight Hamiltonian circuit of the graph. For example, we consider the case of N = 3, where we visit Cardiff (CWL), Edinburgh (EDI), and Belfast (BFS) from London (LON), and the Hamiltonian circuit that passes through in this order. Then, the weight of the Hamiltonian circuit is given by its length d(CLON, CCWL) + d (CCWL, CEDI) + d(CEDI, CBFS) + d(CBFS, CLON), where d(c₁, c₁) indicates the distance between city I and city J (I,J = LON, CWL, EDI, BFS). In the following, we assume that the distance between any two cities is nonnegative and the triangle inequality always holds; in other words, d (c₁, c₁) + d(c₁, ck) ≥ d (C₁, Cg) holds for any Cities I, J, K. Answer the following questions. Q1 As a naïve way, consider the following algorithm, which can output the list of cities in the order of the shortest Hamiltonian circuit. Algorithm 1 Step 1. List all the Hamiltonian circuits starting from London. Step 2. For each Hamiltonian circuit listed in Step 1, calculate the circuit length. Step 3. Find the shortest circuit by finding the minimum of the circuit lengths calculated in Step 2, and output the list of cities in the visiting order of the circuit. Regarding Algorithm 1, answer the following questions. Q1-3 How many years do we need to calculate the lengths of all the Hamiltonian circuits? Here, let one year be 365 days and one day be 86400 seconds. Round the result to an integer and type the INTEGER in the following answer box. Do not include the derivation process. years [5 marks] From the above result, we can see that Algorithm 1 is not practical if N = 19. Let's consider how many cities we can apply Algorithm 1 to. Q1-4 Find the largest N for which we can calculate in one day the length of all the Hamiltonian circuits. Note that we have 86400 seconds in one day. Type an INTEGER in the following answer box. Do not include the derivation process. [5 marks] cities [5 marks] Q1-5 Find the largest N for which we can calculate in 365 days the length of all the Hamiltonian circuits. Note that we have 86400 seconds in one day. Type an INTEGER in the following answer box. Do not include the derivation process. cities
Consider N cities in the UK other than London. We want to visit the N cities efficiently using a helicopter, departing and terminating at London. As a metric of efficiency, we consider the total length of the route. We assume that we can move one city to another along the line (geodesic) that passes through the two cities by helicopter, so we always consider the straight-line distance for any pair of cities. To formulate this problem as a graph problem, we consider a weighted graph such that the node set consists of the N cities and London, the edge set consists of all the pairs of cities, and the weight of an edge is defined by the straight-line distance between the two cities. A path of a graph is called a Hamiltonian circuit if it starts and ends at the same node and passes all the other nodes exactly once. A route departing at London, visiting the N cities, and terminating at London corresponds to a Hamiltonian circuit of the graph starting at London. The total length of a route is the weight of the corresponding Hamiltonian circuit, which is defined by the sum of the weights of the edges in the circuit. Thus, our problem is equivalent to finding a small-weight Hamiltonian circuit of the graph. For example, we consider the case of N = 3, where we visit Cardiff (CWL), Edinburgh (EDI), and Belfast (BFS) from London (LON), and the Hamiltonian circuit that passes through in this order. Then, the weight of the Hamiltonian circuit is given by its length d(CLON, CCWL) + d (CCWL, CEDI) + d(CEDI, CBFS) + d(CBFS, CLON), where d(c₁, c₁) indicates the distance between city I and city J (I,J = LON, CWL, EDI, BFS). In the following, we assume that the distance between any two cities is nonnegative and the triangle inequality always holds; in other words, d (c₁, c₁) + d(c₁, ck) ≥ d (C₁, Cg) holds for any Cities I, J, K. Answer the following questions. Q1 As a naïve way, consider the following algorithm, which can output the list of cities in the order of the shortest Hamiltonian circuit. Algorithm 1 Step 1. List all the Hamiltonian circuits starting from London. Step 2. For each Hamiltonian circuit listed in Step 1, calculate the circuit length. Step 3. Find the shortest circuit by finding the minimum of the circuit lengths calculated in Step 2, and output the list of cities in the visiting order of the circuit. Regarding Algorithm 1, answer the following questions. Q1-3 How many years do we need to calculate the lengths of all the Hamiltonian circuits? Here, let one year be 365 days and one day be 86400 seconds. Round the result to an integer and type the INTEGER in the following answer box. Do not include the derivation process. years [5 marks] From the above result, we can see that Algorithm 1 is not practical if N = 19. Let's consider how many cities we can apply Algorithm 1 to. Q1-4 Find the largest N for which we can calculate in one day the length of all the Hamiltonian circuits. Note that we have 86400 seconds in one day. Type an INTEGER in the following answer box. Do not include the derivation process. [5 marks] cities [5 marks] Q1-5 Find the largest N for which we can calculate in 365 days the length of all the Hamiltonian circuits. Note that we have 86400 seconds in one day. Type an INTEGER in the following answer box. Do not include the derivation process. cities