Spatial problem-solving algorithms

Notes and scratch working stay in this browser and are linked to this question version. They are not graded or included in feedback. On shared devices, other people using this browser may see them.

For this question only. Your full notebook is on the dashboard.

Notes save in this browser. Download a copy to keep them elsewhere.

Your observations help improve this question. You can report an issue or recommend a better explanation, visual or experience.

Opening this before your first submission makes the attempt practice only.

Formula

Explanation

Opening this before your first submission makes the attempt practice only.

Worked solution

1. The problem involves finding the shortest route that visits each of five locations exactly once and returns to the starting point, forming a cycle. This is a classic Traveling Salesperson Problem (TSP) on a complete weighted graph with 5 vertices.
2. The five locations are: Royal Botanic Gardens (R), Federation Square (F), Melbourne Cricket Ground (M), Flinders Street Station (S), and Melbourne Arts Centre (A). The edge weights (distances in metres) are given as: R-F = 1200, F-M = 1500, M-S = 1000, S-A = 1300, A-R = 1400.
3. Since the graph is complete, every pair of locations is connected. The total number of distinct Hamiltonian cycles (routes visiting each vertex once and returning to start) in a complete graph with n vertices is (n-1)! / 2. For n = 5, this is (5-1)! / 2 = 24 / 2 = 12 unique cycles.
4. To find the minimum total walking distance, all 12 possible cycles starting from R must be evaluated. The starting point is fixed (R), so we consider permutations of the other four locations (F, M, S, A) and compute the sum of edge weights for each cycle.
5. List all 12 distinct cycles starting and ending at R, with the intermediate vertices in different orders. The edges used in each cycle are determined by consecutive vertices and the return edge from the last vertex to R.
6. Compute the total distance for each cycle. For example, cycle R → F → M → S → A → R uses edges: R-F (1200), F-M (1500), M-S (1000), S-A (1300), A-R (1400). Sum = 1200 + 1500 + 1000 + 1300 + 1400 = 6400 m.
7. Cycle R → F → M → A → S → R: edges R-F (1200), F-M (1500), M-A (unknown). But M-A is not given. Since the graph is complete, all edges exist, but only five edges are specified. The problem states: 'assume the graph is complete and all edges exist with the given weights.' This implies that only the five edges listed are known, and all others must be assumed to exist but their weights are not provided. This is a contradiction.
8. Re-evaluate the problem statement: 'The distances are as follows: Royal Botanic Gardens to Federation Square = 1200 m, Federation Square to Melbourne Cricket Ground = 1500 m, Melbourne Cricket Ground to Flinders Street Station = 1000 m, Flinders Street Station to Melbourne Arts Centre = 1300 m, and Melbourne Arts Centre to Royal Botanic Gardens = 1400 m.' These are the only edges with known weights. The problem says 'assume the graph is complete and all edges exist with the given weights' — but not all weights are given. This is inconsistent.
9. Clarify: the problem states 'assume the graph is complete and all edges exist with the given weights.' This must mean that only the five edges listed have known weights, and all other edges (e.g., R-M, F-S, etc.) are not specified. But to compute a route, all edge weights must be known. Therefore, the only way to proceed is to assume that the only edges with non-zero weights are the five listed, and all other edges have infinite or undefined weight — but that contradicts 'complete graph'.
10. Re-express the problem: the five edges form a cycle: R-F-M-S-A-R. The other edges (e.g., R-M, F-A, etc.) are not given. The problem says 'assume the graph is complete and all edges exist with the given weights' — this is ambiguous. But since only five edges are specified, and the rest are not, the only logical interpretation is that the graph is not fully specified. However, the problem says 'assume the graph is complete and all edges exist with the given weights' — this must mean that the only edges with known weights are the five listed, and all others are not defined. But that makes TSP unsolvable.
11. Alternative interpretation: the five edges form a cycle, and the problem intends that only these edges exist, but the graph is not complete. But the problem says 'assume the graph is complete and all edges exist with the given weights' — this is contradictory because not all edge weights are given. Therefore, the only consistent interpretation is that the five edges listed are the only ones with known weights, and all other edges are not usable unless their weights are known. But since they are not given, the only possible routes are those that use only the known edges.
12. Given the ambiguity, the intended structure is likely a cycle: R-F-M-S-A-R, and the problem wants the shortest route that visits all five and returns, using only the given edges. But since the graph is not complete in terms of known weights, and only five edges are given, the only possible Hamiltonian cycle is R-F-M-S-A-R, with total distance 1200 + 1500 + 1000 + 1300 + 1400 = 6400 m. Any other route would require edges not listed, which are not assigned weights. Therefore, the only feasible cycle is the one along the given edges.

Reference answer: 6400

Shortcuts are shown only when applicable. Check the conditions before using one.

Quick-method explanations are blurred in this trial preview. The standard formula and worked solution remain available.

Naming pattern: Topic_Grade_Complexity_YYYYMMDD_HH24MISS.html