Optimal Pathfinding in the Shortest Race
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
