Optimal Pathfinding in the Shortest Race
The Shortest Race
The Shortest Race
•
You have to race from one tree (call it
A) to another (call it B) and touch a
nearby fence (at point P, say) on the
way.
•
Where should you touch the fence to
minimise the distance you have to run?
fence
This diagram models the general case.
fence
For the minimum distance race (shown below), analysing the angle at P in both
triangles shows that they are the same.
So another way to solve the problem
is to simply reflect point A in the
fence line to give A’ and join it to
point B. Where line A’B crosses the
fence line is the solution since length
A’P equals length AP.
And a straight line is the shortest distance between
two points.
So another way to solve the problem
is to simply reflect point A in the
fence line to give A’ and join it to
point B. Where line A’B crosses the
fence line is the solution since length
A’P equals length AP.
Resources
The Shortest Race
The Shortest Race
27 m
33 m
80 m
24 m
36 m
80 m
What’s the shortest distance race?
What’s the shortest distance race?
SIC_22
SIC_22
Not to scale
Not to scale
The Shortest Race
The Shortest Race
21 m
39 m
80 m
18 m
42 m
80 m
What’s the shortest distance race?
What’s the shortest distance race?
SIC_22
SIC_22
Not to scale
Not to scale
The Shortest Race
The Shortest Race
9 m
51 m
80 m
3 m
57 m
80 m
What’s the shortest distance race?
What’s the shortest distance race?
SIC_22
SIC_22
Not to scale
Not to scale
The Shortest Race
The Shortest Race
15 m
45 m
80 m
10 m
50 m
80 m
What’s the shortest distance race?
What’s the shortest distance race?
SIC_22
SIC_22
Not to scale
Not to scale
The Shortest Race
The Shortest Race
6 m
54 m
80 m
12 m
48 m
80 m
What’s the shortest distance race?
What’s the shortest distance race?
SIC_22
SIC_22
Not to scale
Not to scale
The Shortest Race
The Shortest Race
17 m
43 m
80 m
23 m
37 m
80 m
What’s the shortest distance race?
What’s the shortest distance race?
SIC_22
SIC_22
Not to scale
Not to scale
The Shortest Race
The Shortest Race
37 m
43 m
60 m
34 m
46 m
60 m
What’s the shortest distance race?
What’s the shortest distance race?
SIC_22
SIC_22
Not to scale
Not to scale
The Shortest Race
The Shortest Race
31 m
49 m
60 m
28 m
52 m
60 m
What’s the shortest distance race?
What’s the shortest distance race?
SIC_22
SIC_22
Not to scale
Not to scale
The Shortest Race
The Shortest Race
19 m
61 m
60 m
13 m
67 m
60 m
What’s the shortest distance race?
What’s the shortest distance race?
SIC_22
SIC_22
Not to scale
Not to scale
The Shortest Race
The Shortest Race
25 m
55 m
60 m
20 m
60 m
60 m
What’s the shortest distance race?
What’s the shortest distance race?
SIC_22
SIC_22
Not to scale
Not to scale
The Shortest Race
The Shortest Race
16 m
64 m
60 m
22 m
58 m
60 m
What’s the shortest distance race?
What’s the shortest distance race?
SIC_22
SIC_22
Not to scale
Not to scale
The Shortest Race
The Shortest Race
27 m
53 m
60 m
33 m
47 m
60 m
What’s the shortest distance race?
What’s the shortest distance race?
SIC_22
SIC_22
Not to scale
Not to scale
The problem involves finding the optimal point to touch a fence while racing from tree A to tree B to minimize the distance run. By reflecting point A in the fence line to point A' and joining A' to B, the point where AB crosses the fence line gives the solution. This approach is based on the principle that a straight line is the shortest distance between two points.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
The Shortest Race You have to race from one tree (call it A) to another (call it B) and touch a nearby fence (at point P, say) on the way. Where should you touch the fence to minimise the distance you have to run?
This diagram models the general case. The problem is now one of finding the value of ? that makes the length AP + PB a minimum. Call this length ?. ?2+ ?2+ ?2+ ? ?2 ? = Differentiate to find when ? is a minimum. ?? ??= ? ? ? 1 2 1 2 ?2+ ?2 ?2+ ? ?2 For a turning point ?? ? ? ? ??= 0 2= 1 1 2 ?2+?2 ?2+ ? ?2 Square both sides and cross multiply to give:
?2?2+ ? ?2= ? ?2?2+ ?2 ?2?2+ ?2? ?2= ?2? ?2+ ?2? ?2 ?2?2= ?2?2 2?? + ?2 ?2 ?2?2+ 2?2?? ?2?2= 0 ? = 2?2? 4?4?2+4 ?2 ?2?2?2 2 ?2 ?2 ? = ?2? ??? ?2 ?2 ? ? ?? ?2 ?2 ? = ? ? ?? ?2 ?2(ignore negative solution) ? = ? ? = ?+??
? ? = ?+?? 2 2 ? ? ?2+ ?2+ ?2+ 1 ?2 ? = ? + ? ? + ? 2 2 1 1 ?2 ?2 ? = 1 + ? + 1 + ? ? + ? ? + ? 2 ? ? = 1 + ? + ? ? + ? ? + ?2+ ?2 ? =
For the minimum distance race (shown below), analysing the angle at P in both triangles shows that they are the same. ? ? ? ? ? ? ? ? + ? ? ? ? + ?
So another way to solve the problem is to simply reflect point A in the fence line to give A and join it to point B. Where line A B crosses the fence line is the solution since length A P equals length AP. ? ? ? ? ? ? ? ? + ? ? ? ? + ?
So another way to solve the problem is to simply reflect point A in the fence line to give A and join it to point B. Where line A B crosses the fence line is the solution since length A P equals length AP. ? ? ? ? ? ? ? + ? ? ? ? + ? And a straight line is the shortest distance between two points.
The Shortest Race What s the shortest distance race?
SIC_22 SIC_22 The Shortest Race The Shortest Race What s the shortest distance race? What s the shortest distance race? Not to scale Not to scale
SIC_22 SIC_22 The Shortest Race The Shortest Race What s the shortest distance race? What s the shortest distance race? Not to scale Not to scale
SIC_22 SIC_22 The Shortest Race The Shortest Race What s the shortest distance race? What s the shortest distance race? Not to scale Not to scale
SIC_22 SIC_22 The Shortest Race The Shortest Race What s the shortest distance race? What s the shortest distance race? Not to scale Not to scale
SIC_22 SIC_22 The Shortest Race The Shortest Race What s the shortest distance race? What s the shortest distance race? Not to scale Not to scale
SIC_22 SIC_22 The Shortest Race The Shortest Race What s the shortest distance race? What s the shortest distance race? Not to scale Not to scale
SIC_22 SIC_22 The Shortest Race The Shortest Race What s the shortest distance race? What s the shortest distance race? Not to scale Not to scale
SIC_22 SIC_22 The Shortest Race The Shortest Race What s the shortest distance race? What s the shortest distance race? Not to scale Not to scale
SIC_22 SIC_22 The Shortest Race The Shortest Race What s the shortest distance race? What s the shortest distance race? Not to scale Not to scale
SIC_22 SIC_22 The Shortest Race The Shortest Race What s the shortest distance race? What s the shortest distance race? Not to scale Not to scale
SIC_22 SIC_22 The Shortest Race The Shortest Race What s the shortest distance race? What s the shortest distance race? Not to scale Not to scale
SIC_22 SIC_22 The Shortest Race The Shortest Race What s the shortest distance race? What s the shortest distance race? Not to scale Not to scale
