Report & Presentation

- Presentation
 (https://www.youtube.com/watch?v=4HLd47LJcgQ&feature=youtu.be&fbclid=IwAR34K-mgBmgQ8UmzDopODX-Y7hezXKws5987jeep3_bJcE8f3kYUcu6_v_k)

-PowerPoint Slide 
(https://drive.google.com/open?id=1HS5H1Dbvn7OcjcNrpk1iRSD2zN_TEjOL)




-Report 
(https://drive.google.com/open?id=1heJrlSQb0I__KKuiLBGF6FCXscz9hEPI )



หมายเหตุ  : การเปิดไฟล์ Report หรือ Powerpoint หากเปิดดูบนเว็บไซต์อาจมีการคลาดเคลื่อนของ Fonts ตัวอักษรและไม่สามารถเคลื่อนไหวภาพนิ่งบน Powerpoint ได้

โดย                       

นายวุฒิเดช ม้าทอง 61070501050

นายกษิดิศ แสงอุทัย 61070501057

Discrete mathematics in Google Maps

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

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

GOOGLE MAPS

       Google Maps ซึ่งเป็นบริการที่คิดค้นเเละพัฒนามาจากบริษัท Google Inc. เป็นบริการที่เป็นที่รู้จักอย่างแพร่หลาย และเป็นที่นิยมเนื่องจากสามารถใช้บริการได้โดยไม่เสียค่าใช้จ่ายอีกด้วย แต่ทว่า ผู้คนที่ใช้บริการ Google Maps ส่วนใหญ่ ไม่ได้รู้ถึงหลักการทำงานหลักลำดับการคิดที่ใช้ในการประมวลผลของมันมากเท่าไหร่นัก ดังนั้นเราจึงจะกล่าวถึงหลักการทำงานและการประยุกต์ใช้ทฤษฎีจาก Discrete Mathematics มาใช้อธิบายประกอบกับหลักการทำงาน โดยในที่นี้ เราจะเน้นไปที่การหาระยะทางหรือเวลาที่ใช้ในการเดินทางที่สั้นที่สุดจากสถานที่หนึ่งไปยังอีกสถานที่หนึ่ง

       ก่อนอื่นเมื่อเราเปิด Google Maps ขึ้นมาใช้ เราจะต้องพิมพ์เข้าไปที่ช่อง Search เพื่อหาสถานที่หรือตำแหน่งของที่ที่เราต้องการหา ในส่วนของ Search Algorithm ทางบริษัทของ Google ไม่ได้เปิดเผย Algorithm ที่ใช้ออกมาสู่สาธารณะ ถ้าหากเป็นการหาชื่อสถานที่ที่มีชื่อเฉพาะหรือของเชตแคบ ระบุได้ชัดเจนก็จะแสดงออกมาได้ง่ายๆเลย แต่ถ้าหากเราหาเป็นชื่ออย่างไม่เจาะจงสถานที่มาก เช่น ร้านอาหารตามสั่ง Googles Maps จะทำการเเสดง list ของรายการสถานที่จากที่ที่ใกล้ตำแหน่งที่เราอยู่ขึ้นมาก่อน ในส่วนนี้จะเป็นการใช้การ Sort แต่ก็อีกเช่นเคย ทาง Google ไม่ได้เปิดเผย Algorithm ที่ใช้ในการ Sort ออกสู่สาธารณะอีกเช่นกัน

       จากที่กล่าวถึงฟังก์ชั่นของ Google Maps ในตอนต้น ที่ใช้หาระยะทางหรือเวลาที่ใช้ในการเดินทางที่สั้นที่สุด หรือเรียกอีกอย่างคือการหา Shortest path โดยจากการศึกษา Google ใช้การหา shortest path จาก Dijkstra's Algorithm ซึ่งเป็น Algorithm ที่จะใช้หาเส้นทางที่สั้นที่สุด โดยสนใจแค่เป้าหมายเดียว โดยมีหลักการทำงานดังนี้

(From : https://www.youtube.com/watch?v=etIB0swmIpI )

       ซึ่งนอกเหนือจากการทำงานที่ใช้หาระยะทางที่สั้นที่สุดหรือเวลาในการเดินทางน้อยที่สุดแล้ว ทาง Google Maps ยังมีฟังก์ชั่นที่เป็นการสร้างจัดหมายปลายทางหลายจุดได้ โดยสามารถเลือกให้ผ่านที่จุดที่ผู้ใช้เลือกไว้ได้ จากการศึกษาพบว่า มีการใช้หลักการคิดของ Hamilton's path ซึ่งคือการเดินทางผ่านครบทุกจุดโดยไม่ซ้ำจุดเดิม โดยใน Google Maps จะมีการประยุกต์เล็กน้อย โดยจะให้จุดเริ่มต้น ทางแยกบนถนน และ จุดจบ เป็น Nodes หรือจุดยอด และให้เส้นทางบนถนนเป็น Edges หรือเส้น 

       

       จากที่กล่าวมานี้ ไม่เพียงเเค่ Google Maps เท่านั้น แต่ Discrete Mathematics สามารถนำไปประยุกต์ใช้ในหลายๆการใช้งานที่เป็นส่วนสำคัญที่ใช้ในการสร้างสรรค์แอพพลิเคชั่นอื่น ๆ หรือการจัดการบริการต่าง ๆ 

Reference 5 (Search & Sort)

Reference 5

-From searching about search and sort algorithm that Google used, we find that Google Inc. doesn't review thier algorithm to public. So ,we will show the example about search and sort algorithm to explain how it work.

Reference from " https://joo.gl/dD5hkz4 " and " https://stackoverflow.com/questions/704120/what-searching-algorithm-concept-is-used-in-google "

-Sort algorithm that we will show to you is "Merge sort". This is the algorithm that use Divide and conquer . 

Reference from " https://www.youtube.com/watch?v=JSceec-wEyw "

-Search algorithm that we will show to you is "Linear search" because we think that it's simple and easy to understand.

Referenc from " https://www.youtube.com/watch?v=4GPdGsB3OSc "

Reference 4 (Warshall algorithm)

Reference 4

- From the studing , we found that when user use the function that mark multiple point in Google Maps it's must use the Warshall algorithm to find that the new point that user marked and check that have the ways to go to that point.

Resource of detail (Warshall algorithm)  " https://math.stackexchange.com/questions/369134/how-to-use-warshalls-algorithm " 

Reference 3 (Multiple destination function)

Reference 3

- From the studing of how google maps work. We found that google maps has a function that can mark each place in the map more than 2 point by using Microsoft Exel to assign the input . So it's show that it's about  Hamilton's path to find the ways that pass every place you marked it.
Resource of detail " https://www.youtube.com/watch?v=5MPhCDp7iTY "

Reference 2 ( How google Maps compute direction a to b)

Reference 2

- How google map compute direction from point a to b
https://stackoverflow.com/questions/430142/what-algorithms-compute-directions-from-point-a-to-point-b-on-a-map

- in this website we've learned how to create a google map in real world but it to hard to understand in the first time that you read that therefore I know some part of google map such as google map use
a Dijkstra's Algorithm with some modification to solve this problem and you have to create a several layer such as highways layer or secondary way to store a specific detail of a road and I found another document in comment " http://algo2.iti.uka.de/schultes/hwy/schultes_diss.pdf "

Update 12/12/2018

At the beginning we think that  Dijkstra's algorithm maybe not work in the enormous graph
but after we read a website its told our that " Dijkstra will not usually look at the complete graph but rather just a very small subset "

Reference 1 (Discrete Math real world & Google Maps Algorithm)

- Discrete Math in real world
http://www.mathily.org/dm-rw.html?fbclid=IwAR3oMJU82Upwpc6lOehyWPZG49EgyatXMXykGajApsL5p_JvzAFtAaLwhck

- Google map algorithym
https://motherboard.vice.com/en_us/article/4x3pp9/the-simple-elegant-algorithm-that-makes-google-maps-possible


- in the first website we decided to choose a google map as my topic so we find others website to find more knowledge about this topic and we found second website

- in the second website l've learned about how google map work by using graph theory and how to find a shortest path by using Dijkstra algorithms an algorithms that use only 20 minutes to discover

Proposal

Discrete Math Project

-      Topic: Discrete in Google maps

-      Statement: Reengineering เกี่ยวกับการทำงานของ Google maps ที่เป็นบริการของ google

-      Why Important:   graph theory, algorithm, sort

graph theory à เปรียบเทียบสถานที่เป็น Vertex ถนนเป็น edge และใช้กราฟถ่วงน้ำหนักเพื่อหาเส้นทางที่ดีที่สุดในการเดินทาง เช่น ใกล้ที่สุด (shorten path) หรือ เวลาที่ใช้เดินทางน้อยที่สุด

algorithm   à ลำดับขั้นตอนการทำงานตั้งแต่เปิดโปรแกรมไปจนถึงการนำทาง

sort      à  การเรียงข้อมูลต่าง ๆ ในช่องค้นหา เช่น จากสถานที่ที่ใกล้ตำแหน่งของผู้ใช้มากที่สุดไปจนถึงไกลที่สุดในระยะที่กำหนด

-       เหตุผลที่เลือก : เหตุผลที่เลือก Google maps เพราะในปัจจุบัน google เป็นเครื่องมือสำคัญที่ทุกคนแทบจะต้องใช้ในการนำทาง หรือประกอบการตัดสินใจในการเลือกเส้นทาง พวกเราจึงอยากศึกษาการทำงาน รวมไปถึงหลักการคิดที่สามารถนำความรู้จากวิชา Discrete mathematics  มาประยุกต์ใช้ได้ รวมไปถึงสามารถนำความรู้ไปต่อยอดในด้านอื่น ๆ ได้

-      Document File

https://drive.google.com/file/d/16unJ72vV8BwBUkt8tIKHRaGysDZdC8Gz/view?usp=sharing

นายวุฒิเดช ม้าทอง 61070501050

นายกกษิดิศ แสงอุทัย  61070501057