ตัวอย่างโจทย์ที่กำหนดขึ้นเอง

ตัวอย่างการหาระยะทางที่สั้นที่สุด

โจทย์ :

เด็กชายทรงพล ต้องการไปยังโรงเรียนด้วยระยะทางที่ใกล้ที่สุด โดยจากบ้านไปยังสวนสาธารณะ วัด และตลาด เป็นระยะทาง 5 8 และ 4 เมตร จากสวนสาธารณะ ตลาด และวัด ไปยังโรงพยาบาลเป็นระยะทาง 7 5 และ 12 เมตร จากตลาด และวัด ไปยังสถานีตำรวจเป็นระยะทาง 11 และ 11 เมตร และจากโรงพยาบาล และสถานีตำรวจ ไปยังโรงเรียนเป็นระยะทาง 9 และ 6 เมตร ตามลำดับ

วิธีทำ :

ให้ A แทน บ้าน

     B แทน สวนสาธารณะ

     C แทน วัด

     D แทน ตลาด

                    E แทน โรงพยาบาล

     F แทน สถานีตำรวจ

     G แทน โรงเรียน

Step 1 : หาเส้นทางที่จะไปได้ ซึ่งจะเห็นได้ว่ามีจาก A ไป B  A ไป C และ A ไป D

Step 2 : เลือกเส้นทางที่ระยะทางสั้นที่สุด ซึ่งจะได้ A ไป D ระยะทาง 4 เมตร ที่สั้นที่สุด

Step 3 : หาเส้นทางที่จะไปได้ ซึ่งจะเห็นได้ว่ามีจาก A ไป D ไป E และ A ไป D ไป F

Step 4 : เลือกเส้นทางที่ระยะทางสั้นที่สุด ซึ่งจะได้ A ไป D ไป F ระยะทาง 9 เมตร ที่สั้นที่สุด

Step 5 : หาเส้นทางที่จะไปได้ ซึ่งจะเห็นได้ว่ามี A ไป D ไป E ไป G  และ A ไป D ไป F

Step 6 : เลือกเส้นทางที่ระยะทางสั้นที่สุด ซึ่งจะได้ A ไป D ไป F ระยะทาง 15 เมตร ที่สั้นที่สุด

Step 7 : เลือกเส้นทางที่ระยะทางสั้นที่สุด ซึ่งจะได้ A ไป D ไป E ไป G ระยะทาง 18 เมตร ที่สั้นที่สุด

Do when 16/12/2018 8.12 PM

2nd Data Summary

การหาเส้นทางที่สั้นที่สุด

     สำหรับการหาเส้นทางที่สั้นที่สุดนั้น จะเป็นการสร้างแบบจำลองเส้นทางหรือแผนที่เป็น กราฟ ซึ่งประกอบไปด้วย จุด และ เส้น ซึ่งจะให้ตำแหน่งแทนด้วยจุด และให้ถนนแทนด้วยเส้น จากนั้นจะทำกราฟที่ได้มาเป็นตัวแทนของแผนที่ เพื่อนำไปคำนวณเส้นทางที่สั้นที่สุด  

รูปที่ 1 กราฟทีมี 2 จุด 1 เส้น

รูปที่ 2 กราฟทีมี 4 จุด 3 เส้น

รูปที่ 3 กราฟเป็นวัฏจักร

                จากรูปที่ 1-3 เป็นกราฟแบบง่าย แต่เมื่อนำมาใช้ในแผนที่นั้นจะซับซ้อนกว่านั้น ซึ่งมีชื่อเรียกว่า Multiple Graph

รูปที่ 4 Multiple Graph

ที่มา https://www.ryerson.ca/science/research/stories/story_pralat_2013/

               การจะหาเส้นทางที่สั้นที่สุดนั้น จะดูจากเส้นทางที่ผ่านจุดหรือระยะทางน้อยที่สุด

รูปที่ 5

ที่มา https://myalgo.wordpress.com/2010/09/04/weighted-shortest-path-dijkstras-algorithm/

จากรูปจะเห็นได้ว่า เมื่อต้องการเดินทางจากจุดที่ 1 ไปยังจุดที่ 7 ระยะทางที่ใกล้ที่สุด คือจาก จุดที่ 1 ไปยังจุดที่ 4 แล้วไปยังจุดที่ 7 ซึ่งมีระยะทางเพียง 5

การหาเส้นทางที่สั้นที่สุดจะใช้อัลกอริทึมที่มีชื่อว่า Dijkstra’s algorithm แล้วนำมาแปลงเป็นเส้นทางถนนต่อไป โดยมีการใส่ระยะเส้นทางไปด้วย

Dijkstra’s algorithm

Dijkstra’s algorithm ถูกคิดค้นขึ้นโดย Edsger Dijkstra นักวิทยาการคอมพิวเตอร์ชาวดัตช์ ในปี 1959 เพื่อแก้ไขปัญหาการหาเส้นทางที่สั้นที่สุดจากจุดหนึ่งใดๆ สำหรับกราฟที่มีความยาวของเส้นเชื่อมไม่เป็นลบ สำหรับขั้นตอนวิธี Dijkstra’s Algorithm นี้จะหาระยะทางสั้นที่สุดจากจุดหนึ่งไปยังจุดใด ๆ ในกราฟโดยจะหาเส้นทางที่สั้นที่สุดไปทีละจุดยอดเรื่อยๆ จนครบตามที่ต้องการ

Dijkstra’s algorithm

กำหนดให้จุด จุดหนึ่งภายในกราฟเป็นจุดเริ่มต้น และกำหนดให้ “ระยะทางของจุด X” หมายถึงระยะทางจากจุดเริ่มต้นไปยังจุด X ใด โดย Dijkstra’s algorithm จะกำหนดค่าระยะทางเริ่มต้นไว้บางจุดและจะเพิ่มค่าไปทีละขั้นตอน

1.             กำหนดให้ทุกจุดมีค่าระยะทางตามเส้นเชื่อม โดยให้จุดเริ่มต้นมีค่าเป็นศูนย์ และจุดอื่นๆมีค่าเป็นอนันต์

2.             ทำเครื่องหมายทุกจุด ยกเว้นจุดเริ่มต้นว่ายังไม่ไปเยือน ตั้งให้จุดเริ่มต้นเป็นจุดปัจจุบัน สร้างเซตของจุดที่ยังไม่ไปเยือนขึ้นมาเซตหนึ่งซึ่งประกอบด้วยจุดทุกจุด ยกเว้นจุดเริ่มต้น

3.     จากจุดปัจจุบัน พิจารณาจุดข้างเคียงตามเส้นเชื่อมทุกจุดที่ยังไม่ไปเยือน และคำนวณระยะทางต่อเนื่องของเส้นเชื่อม ตัวอย่างเช่น ถ้าจุดปัจจุบันคือ A มีระยะทางของจุดเป็น 6 และเส้นเชื่อมที่ต่อจาก A ไปยังจุดข้างเคียง B มีระยะทางเป็น 2 ดังนั้นระยะทางของจุด B (โดยผ่าน A) จึงเท่ากับ 6+2=8 เป็นต้น ถ้าระยะทางที่คำนวณได้มีค่าน้อยกว่าค่าระยะทางที่บันทึกอยู่ของจุดนั้น ให้เขียนทับค่าระยะทางของจุดดังกล่าว แม้ว่าจุดข้างเคียงได้ถูกพิจารณาแล้ว แต่ก็ยังไม่ทำเครื่องหมายว่าไปเยือนแล้ว (visited) ในขั้นตอนนี้ จุดข้างเคียงจะยังคงอยู่ในเซตของจุดที่ยังไม่ไปเยือนเช่นเดิม

4.     เมื่อพิจารณาจุดข้างเคียงจากจุดปัจจุบันครบทุกจุดแล้ว ทำเครื่องหมายที่จุดปัจจุบันว่าไปเยือนแล้ว (visited) และนำออกจากเซตของจุดที่ยังไม่ไปเยือน โดยจุดที่ไปเยือนแล้วนี้จะไม่ถูกนำมาตรวจสอบอีก ค่าระยะทางที่บันทึกอยู่จะสิ้นสุดและมีค่าน้อยที่สุด

5.     จุดปัจจุบันตัวถัดไปที่ถูกเลือกจะเป็นจุดที่มีค่าระยะทางน้อยสุดในเซตของจุดที่ยังไม่ไปเยือน

6.             ถ้าเซตของจุดที่ยังไม่ไปเยือนว่างแล้วให้หยุดการทำงาน ขั้นตอนวิธีเสร็จสิ้น แต่ถ้าหากไม่ใช่ให้เลือกจุดที่ยังไม่ไปเยือนที่มีค่าระยะทางน้อยสุดเป็นจุดปัจจุบัน แล้ววนกลับไปทำขั้นตอนที่ 3

รูปที่ 6 รูปแสดง Dijkstra’s algorithm

ที่มา https://www.appdisqus.com/2015/02/06/algorithm-of-google-here-apple-maps.html

Reference : https://www.appdisqus.com/2015/02/06/algorithm-of-google-here-apple-maps.html
                

Search when 15/12/2018 3.45 PM

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