Graph

The Functions of Google Maps

เรื่องที่ต้องการศึกษา :  Google Maps

หลักการ Discrete Mathematic ที่ต้องการศึกษาใน Google Maps
- ทฤษฎีกราฟ (graph theory)
- Dijkstra Algorithm
- A* Search Algorithm

หลักการศึกษา 
1. ต้องการศึกษาว่าใน  Google Maps ใช้หลักทฤษฎีกราฟทำงานอย่างไร
- การทำงานของ Google Maps ที่สามารถบอกเส้นทางที่ใกล้ที่สุดในการเดินทางจากที่หนึ่งไปที่หนึ่งมีความสัมพัทธ์กับทฤษฎีกราฟอย่างไร
- รูปภาพหรือตัวอย่างประกอบการอธิบาย

2. ใช้ Algorithm ใดบ้างใน Google Maps โดยจะยกตัวอย่าง Algorithm แค่บางส่วนเท่านั้นเพราะใน Google Maps ใช้กับ Algorithm ที่หลากหลาย
- ยกตัวอย่าง Dijkstra Algorithm และ A* Search Algorithm
- รูปภาพหรือตัวอย่างประกอบการอธิบาย

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

ความคิดเห็น

แสดงความคิดเห็น

โพสต์ยอดนิยมจากบล็อกนี้

ทฤษฎีกราฟ 4

รูปภาพ
Euler Circuit คือ กราฟที่ต้องเดินผ่านทุกด้าน ไม่มีการซ้ำด้าน เริ่มตรงไหนจบตรงนั้น โดยจุดยอดทุกจุดจะมีดีกรีคู่ ภาพประกอบจาก https://www.geeksforgeeks.org/wp-content/uploads/Euler 2. png จากภาพจะพบว่าทุกจุดยอดมีดีกรีคู่ เมื่อมีการเดินผ่านทุกด้านโดยไม่ซ้ำจุดเริ่มต้นและสิ้นสุดจะเป็นจุดเดียวกัน Euler Path คือ กราฟที่ต้องเดินผ่านทุกด้าน ไม่มีการซ้ำด้าน แต่ เริ่มต้นกับสิ้นสุดต้องเป็นคนละจุด สามารถสังเกตได้จากกราฟว่าจะมีสองจุดยอดเท่านั้นที่มีดีกรีเป็นเลขคี่ ภาพประกอบจาก https://www.geeksforgeeks.org/eulerian-path-and-circuit/ จากภาพพบว่ามีสองจุดเท่านั้นที่มีดีกรีคี่ คือ จุด 0 และ จุด 4 เมื่อมีการเดินผ่านทุกด้านพบว่าจุดเริ่มต้นและสิ้นสุดเป็นคนละจุดกัน   Hamilton Circuit คือ กราฟที่ไม่จำเป็นต้องเดินผ่านทุกด้าน จุดเริ่มต้นและสิ้นสุดเป็นจุดเดียวกัน ไม่ซ้ำจุด ภาพประกอบจาก https://slideplayer.com/slide/ 7549367/ เมื่อเดินผ่านทุกจุดพบว่าจุดเริ่มต้นและสิ้นสุดเป็นจุดเดียวกัน ทั้งสองภาพ H...
อ่านเพิ่มเติม

ทฤษฎีกราฟ 3

รูปภาพ
Bipartite graph คือ กราฟที่สามารถแบ่งออกเป็นสองส่วน โดยทั้งสองส่วนนั้นจะมีเส้นเชื่อมเชื่อมกันแต่จะไม่มีเส้นเชื่อมภายในส่วนเดียวกัน ภาพประกอบจาก https://study.com/cimages/multimages/ 16/ bipartite 4. jpg จากภาพจะพบว่าสามารถแบ่งกราฟออกเป็นสองส่วน โดยแต่ละจุดยอดของกลุ่ม 1 จะมีเส้นเชื่อมไปยังกลุ่ม 2 ทุกเส้นแต่ไม่มีเส้นใดเลยที่เชื่อมกันเองภายในกลุ่ม การแทนที่กราฟและการสมสัณฐานของกราฟ (Representing graph and graph Isomorphism) การแทนที่กราฟด้วย Adjacency matrix แบ่งเป็น แบบไม่มีทิศทางและแบบมีทิศทาง ภาพประกอบจาก https://bournetocode.com/projects/AQA_A_Theory/pages/graph.html จากภาพเป็นการแทนที่กราฟด้วย Adjacency Matrix กราฟเป็นแบบไม่มีทิศทาง จุดยอดที่มีเส้นเชื่อมไปยังอีกจุดยอดหนึ่งจะแทนด้วย เลข 1 แต่ถ้าไม่มีจะแทนด้วย เลข 0 ในกรณีที่กราฟนั้นเป็นกราฟเชิงเดียวหรือ simple graph โดยอันดับแรกจะเขียนจุดยอดที่หลักและแถว จากนั้นให้สังเกตแต่ละจุดยอดว่ามีเส้นเชื่อมไปยังจุดใดบ้างให้ทำแบบนี้ไปเรื่อยๆจนถึงจุดยอดสุดท้าย ภาพประกอบจาก https://bournetocode.com...
อ่านเพิ่มเติม

ทฤษฎีกราฟ

รูปภาพ
ทฤษฎีกราฟ กราฟมีบทบาทสำคัญกับชีวิตของเราอย่างไร ? ถนนที่เราใช้ในการสัญจรเป็นตัวอย่างหนึ่งที่มีการนำทฤษฎีกราฟมาใช้รวมทั้งการวางระบบท่อประปา และวงจรไฟฟ้า ชีวิตประจำวันของเราล้วนเกี่ยวข้องกับคณิตศาสตร์ในเรื่องต่างๆรวมถึงเรื่องทฤษฎีกราฟ กราฟ G ประกอบด้วยคู่ลำดับของเซต คือ 1.          เซตของจุดยอด (Vertex) ที่ไม่เป็นเซตว่าง V(G) 2.          เซตของเส้นเชื่อม (Edge) ระหว่างคู่ที่เชื่อมจุดยอด E(G) ภาพที่ 1 ภาพประกอบจาก https://www 3. nd.edu/~dgalvin 1/40210/40210 _F 12/ CGT_early.pdf จากภาพ   เซตของจุดยอด หรือ V(G) คือ { a, b, c, d, e, f, g, h}   เซตของเส้นเชื่อมที่เชื่อมจุดยอด หรือ E(G) คือ {{a, e},{a, d},{b, e},{b, g},{b, c},{c, f},{d, f},                                                                     ...
อ่านเพิ่มเติม