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