1-page Proposal

Search the shortest path of GPS system

ในอดีตเวลาเดินทางไปยังต่างถิ่นที่เราไม่รู้จักเส้นทาง สิ่งสำคัญที่จำเป็นคือ แผนที่ ซึ่งการหาตำแหน่งของแผนที่นั้น เป็นเรื่องที่ยากและใช้เวลานานมาก และในปัจจุบันก็ได้มีตัวช่วยที่ทำให้ง่ายต่อการดูแผนที่มากขึ้น และง่ายต่อการระบุตำแหน่ง รวมถึงยังมีการค้นหาเส้นทางในการเดินทางอีกด้วย ซึ่งเทคโนโลยีนั้น มีชื่อเรียกว่า Global Positioning System หรือที่รู้จักกันว่า GPS

โดยการศึกษาค้นคว้าครั้งนี้ ทางคณะผู้จัดทำก็ได้ทำการค้นคว้าหาข้อมูลจากหลากหลายแหล่ง รวมถึงมีการทดลองใช้ Google Maps Application ที่มีการทำงานของระบบ GPS

GPS ทำงานอย่างไร ?

            ระบบการทำงานของ GPS จะทำงานผ่านดาวเทียมที่กระจายอยู่รอบโลก โดยจะทำการรับสัญญาณจากดาวเทียมเหล่านั้น แล้วทำการคำนวณระยะทางจากเวลาของคลื่นวิทยุที่ส่งสัญญาณกันระหว่างดาวเทียมกับเครื่องรับสัญญาณ

GPS ใช้ความรู้เรื่อง Discrete Mathematics ในเรื่องอะไร ?

         ใช้ความรู้เรื่อง Graph Theory ด้วยวิธีการของ Dijkstra เพื่อที่จะหาสิ่งหนึ่งที่เรียกว่า Single-Source Shortest Path หรือเส้นทางที่สั้นที่สุดจากจุดเดียว โดยมีหลักการโดย ให้ตำแหน่งแทนด้วยจุด vertices และแทนเส้นทางด้วย edges ซึ่งรวมเส้นทางทั้งหมด เรียกว่า Path

ทำไมถึงเลือกหัวข้อนี้

จากการใช้ Google Maps Application ที่มีการค้นหาเส้นทางและบอกเส้นทางให้กับเรา ซึ่งมักจะการแนะนำเส้นทางที่ระยะทางสั้นกว่ามาให้เราด้วย จึงทำให้รู้สึกสนใจ และอยากทราบว่ามีหลักการอะไรในการหาเส้นทางที่สั้นที่สุด

                                                                                                                       สมาชิก
                                                                                      นายกรฤทธิ์        ประสพรัตนโชค  61070501001
                                                                                      นางสาวดลยพร  วิวัฒน์                  61070501024 

1st Data Summary

การประยุกต์ใช้ Graph Theory ใน GPS

     Global Positioning System หรือที่รู้จักกันทั่วไปว่า GPS เป็นระบบที่ช่วยระบุตำแหน่งบนพื้นโลก โดยจะระบุทิศทางออกมาเป็น (x,y,z) จึงมีการใช้ประโยชน์มากมาย เช่น ใช้ติดตามการเคลื่อนที่ ใช้ค้นหาเส้นทาง คำนวนเวลาที่จะเดินทาง เป็นต้น การทำงานของ GPS นั้น จะเป็นการส่งสัญญาณไปมา โดยจะมีดาวเทียมที่คอยส่งสัญญาณไปยังตัวเครื่องรับสัญญาณ GPS แล้วทำการประมวลผลออกมา 

     โดยเรื่อง Graph Theory นำมาใช้ในการที่ GPS นั้น จะหาเส้นทางที่สั้นที่สุดจากปลายทางหนึ่งไปอีกปลายทางหนึ่ง โดยมีเป้าหมายคือ Vertices ที่มีการเชื่อมต่อกันเป็น Edges โดยระยะทางที่ดีที่สุดจะถูกกำหนดโดย software โดยใช้ Hamiltonian path สำหรับการรวมจุด Vertices ในเส้นทาง

Reference : https://www.academia.edu/34939310/An_Overview_Applications_of_Graph_Theory_in_Real_Field

Search when 25/11/2018 9.01 PM

2nd Data Search

Applications of the Global Positioning System

The Global Positioning System (GPS) can be used to determine position and velocity on the Earth or even in space. There are therefore many possible uses ("applications") of GPS.

Design an application of GPS. You can use some of the suggestions below, or think of your own. Draw a picture showing how GPS is to be used. You pictures should indicate where the GPS receiver should be located. Also show the locations of any human operators or computers, and any other equipment that is required.

For example, you might want to design a car that drives itself. Maybe you'll put the GPS receiver on the top of a car. The GPS receiver needs to be connected to a computer inside the car that a person gives commands to. Draw a picture showing these connections, and explain how the system is to be used.

Here are some other suggestions. Use one of these or think up your own.

• A space shuttle that navigates by itself using GPS
• A tractor that plows fields by itself using GPS
• An airplane that lands itself using GPS
• A football coach who tracks players on the field using GPS
• A hiker who loses her way and returns to safety using GPS
• Tracking a species of animal using GPS

Reference : https://www.cfa.harvard.edu/space_geodesy/ATLAS/applications.html

Search when 25/11/2018 8.07 PM

1st Data Search

Geographic Information Systems (GIS)

     GIS is one of the many fields that uses discrete math. Graph Theory is a popular topic that is used for the analysis of genetic codes, as well as sequencing and pattern matching. Many people rely on taking the shortest rout to reach their destination. Not only do people rely on using maps, but technology has allowed us to use Global Positioning Systems (GPS) in the car or on out smart phones. Graph theory helps us to determine what should be included or excluded from a map. These short routs make up a minimal spanning network. In Discrete mathematics we can use Prim's Algorithm to create a minimal spanning tree for a given graph. Here is an example below.

First edge:  Milwaukee - Indianapolis (cost 274 miles)

Second edge: Indianapolis - Kansas City (cost 482 miles)

Third edge: Indianapolis - Columbus (cost 183 miles)

Fourth edge: Columbus - Detroit (cost 203 miles)

Fifth edge: Columbus - Richmond (cost 479 miles)

Sixth edge: Richmond - Nashville (cost 614 miles)

Total Cost: 274 + 482 + 183 + 203 + 479 + 614 miles 

Reference : https://sites.google.com/site/realworldmathematics/discrete-mathematics

Search when 23/11/2018 10.52 PM