Google Maps เลือกเส้นทางด้วย Shortest path สั้นที่สุด เพื่อไปยังจุดหมาย

Google Maps เลือกเส้นทางด้วย Shortest path สั้นที่สุด เพื่อไปยังจุดหมาย

Google maps เลือกเส้นทางอย่างไร

Google maps เลือกเส้นทางที่สั้นที่จุดโดยใช้ขั้นตอนวิธีแบบ Shortest path เพื่อไปยังจุดหมายปลายที่กำหนด หากมีสัญญาณ GPS แล้วทั้งสองสิ่งนี้คืออะไร มาหาคำตอบกัน

ว้าว ๆ Google maps นี่มันฉลาดจริง อยากไปที่ไหนแค่กำหนดจุดหมายปลายทางไปก็สามารถบอกเส้นทางเราได้แล้ว เพียงแค่อยู่ในสถานที่ที่ไม่เป็นจุดอับสัญญาณ GPS เท่านั้นเอง แถมมีเส้นทางให้เราเลือกด้วย แต่ปกติเรามักเลือกเส้นทางที่ application แนะนำมานั้นแหละ ด้วยความเชื่อที่ว่าแอพมันคงฉลาดเลือกทางที่ดีที่สุดมาให้แล้วละ หรือจริง ๆ แค่ขี้เกียจเลือกกันแน่นะ ฮ่า ฮ่า

สัญญาณ GPS สำคัญแค่ไหน ทำไม Google maps ถึงจำเป็นต้องใช้มันด้วย มาทำความรู้จักสัญญาณ GPS กันครับ

GPS คืออะไร

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

กลับมาที่ GPS กันต่อครับ ชื่อก็บอกอยู่แล้วว่าเป็นระบบระบุตำแหน่งบนโลก แสดงว่าไม่ได้มีเพียงส่วนเดียวแน่นอน

ใช่แล้วครับ GPS ประกอบไปด้วย 3 ส่วนหลัก คือ

  1. ส่วนอวกาศ เป็นพื้นที่สำหรับการโคจรของเครือข่ายดาวเทียม ปัจจุบันมี 3 ค่ายหลัก คือ
    • NAVSTAR (Navigation Satellite Timing and Ranging GPS) ของสหรัฐอเมริกา ซึ่งเปิดให้ประชาชนทั่วไปใช้ได้ในระดับความแม่นยำที่ไม่เป็นภัยต่อความมั่นคงของรัฐ ตามนโยบายสิทธิการเข้าถึงข้อมูลและข่าวสารสำหรับประชาชนของรัฐบาลสหรัฐอเมริกา NAVSTAR ประกอบด้วยดาวเทียม 24 ดวง โดยแบ่งเป็น 6 รอบวงโคจรในลักษณะสานกันคล้าย ลูกตะกร้อแต่ละวงโคจรมีดาวเทียม 4 ดวง ดาวเทียมแต่ละดวงใช้ เวลาในการโคจรรอบโลก 12 ชั่วโมง
    • Galileo ของยุโรป มี 27 ดวง อยู่ภายใต้การดูแลของ European Satellite Agency
    • GLONASS( Global Navigation Satellite ) ของรัสเซีย อยู่ภายใต้การดูแลของ Russia VKS (Russia Military Space Force)
  1. ส่วนควบคุม เป็นส่วนที่อยู่บนภาคพื้นโลก แบ่งเป็น 2 ส่วน ได้แก่
    • Master Control Station คือ สถานีแม่ข่าย ซึ่งมีเพียง 1 สถานีในโลก ตั้งอยู่ที่ Schariever Airforce Base (FALCON AFB) รัฐโคโลราโด สหรัฐอเมริกา เป็นสถานีศูนย์กลางการสนับสนุนการทำงานให้กับสถานีลูกข่าย (Monitor Station) โดยคำนวณตำแหน่งและนาฬิกา ดูความคลาดเคลื่อนของดาวเทียมแต่ละดวงจากสถานีลูกข่าย และส่งคำสั่งแก้ไขไปยังสถานีลูกข่ายเพื่อส่งต่อไปยังดาวเทียมดวงนั้น ๆ
    • Monitor Station คือ สถานีลูกข่าย มีอยู่ 4 สถานีทั่วโลก ได้แก่ Hawaii, Ascension island, Diego Garcia และ Kwajalein ทำหน้าที่ตรวจสอบความสูง ตำแหน่ง  ความเร็ว และวงจรทั่วไปของดาวเทียม โดยแต่ละสถานีทำการตรวจสอบวันละ 2 ครั้ง เมื่อดาวเทียมโคจรรอบโลกผ่านสถานีนั้น ๆ
  2. ส่วนผู้ใช้งาน เป็นส่วนที่ต้องมีเครื่องรับบสัญญาณจากดาวเทียม และนำสัญญาณมาคำนวณหาตำแหน่งปัจจุบันตลอดเวลา (Real time) นอกจากตำแหน่งของเส้นรุ้ง เส้นแวง แล้วยังสามารถทราบถึงความเร็วในการเคลื่อนที่ด้วย

gps2

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

เครื่องรับสัญญาณ GPS ทำงานโดยรับข้อมูล 2 อย่าง คือ เวลาและตำแหน่ง ณ ขณะที่ดาวเทียมส่งสัญญาณมายังเครื่องรับสัญญาณ แล้วนำมาประมวลผลเป็นระยะทางระหว่างเครื่องรับสัญญาณกับดาวเทียมดวงที่ส่งข้อมูลมา สามารถคำนวณได้ด้วยสูตรฟิสิกส์พื้นฐาน คือ ระยะทาง = เวลา × ความเร็ว ดังนี้

ระยะห่างระหว่างเครื่องรับสัญญาณกับดาวเทียม = (เวลาที่ได้รับสัญญาณ – เวลาที่สัญญาณถูกส่ง) × ความเร็วของคลื่นวิทยุ

หากพื้นโลกแบนราบอย่างที่คนทั้งโลกกล่าวกับโคลัมบัสเราคงใช้ดาวเทียมเพียง 3 ดวง ในการระบุตำแหน่งได้แม่นยำ แต่โลกเรากลมอย่างโคลัมบัสเชื่อ เราจึงต้องใช้ดาวเทียมอย่างน้อย 4 ดวง โดยดาวเทียมดวงที่เพิ่มเข้ามาจะใช้คำนวณความสูง เพื่อให้ได้ตำแหน่งที่แม่นยำมากขึ้น

gps

Google Maps เลือกเส้นทางอย่างไร

ผมเคยสงสัยนะ ทำไมแอพลิเคชันแผนที่นำทาง เช่น Google maps ถึงมีให้เลือกหลายเส้นทาง บางครั้งเราไม่เคยรู้มาก่อนว่าใช้เส้นทางนั้นได้ จนกระทั่งผมได้มาเรียนรู้กระบวนการหาทางเดินสั้นที่สุด (Shortest path algorithm) ของ Dijkstra ซึ่งเป็นเนื้อหาบางส่วนในเรื่องทฤษฎีกราฟ จึงทราบว่าแอพลิเคชันไม่ได้เลือกเส้นทางแบบเดาสุ่ม หรือเลือกเส้นทางให้ใกล้เคียงเส้นตรงมากที่สุด แต่อาศัย ระยะทาง, ความหนาแน่นของรถบนท้องถนน หรือระยะเวลา เป็นข้อมูลในการตัดสินใจ graph1

(แต่ตอนนี้ Google Maps ไม่ได้เลือกเส้นทางด้วยเส้นทางที่สั้นที่สุดอย่างเดียวแล้วนะครับ แต่เป็นเส้นทางที่ถึงไวที่สุด เนื่องจากได้นำข้อมูลอื่นๆ เช่น ปริมาณรถติดในแต่ละเส้นทาง มาเป็นปัจจัยในการเลือกเส้นทางด้วย)

Shortest path algorithm คืออะไร

Shortest path algorithm เป็นกระบวนการหาทางเดินสั้นที่สุด ในการเดินทางจากจุดหนึ่งไปยังอีกจุดหนึ่ง โดยวิธีของ Dijkstra จะให้กำหนดจุดเริ่มต้น, จุดปลายทาง, จุดระหว่างทาง(ทางแยกบนท้องถนน), เส้นเชื่อมจุดที่เป็นไปได้ และระยะทางของเส้นเชื่อมจุดแต่ละเส้น และมีวิธีหาทางเดินสั้นที่สุด ดังนี้

กำหนดจุดเริ่มต้น(ตำแหน่งปัจจุบัน) เป็น 0 และจุดอื่น ๆ เป็น infinity หรือไม่กำหนด

sp

เลือกเส้นทางที่ออกจากจุดเริ่มต้นไปจุดถัดไป แล้วบันทึกระยะทางที่เดินบนจุดนั้น

sp-12

เลือกเส้นทางที่ออกจากตำแหน่งปัจจุบัน(จุด 1 ) ไปจุดถัดไป แล้วบันทึกระยะทางที่เดินรวมกับค่าบนจุดที่เดินออกมาไว้บนจุดถัดไป

sp-34

เลือกเส้นทางที่ออกจากตำแหน่งปัจจุบัน(จุด 3 ) ไปจุดถัดไป แล้วบันทึกระยะทางที่เดินรวมกับค่าบนจุดที่เดินออกมาไว้บนจุดถัดไป

sp-56

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

sp-78

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

กระบวนการขนส่งอันรวดเร็วและคุ้มค่า

นอกจากการตัดสินใจเลือกเส้นทางของแอพลิเคชันแผนที่นำทาง ยังมี การขนส่งสินค้าที่ใช้ Shortest path algorithm เพื่อตัดสินใจเลือกเส้นทางที่รวดเร็วและคุุ้มค่าในการขนส่ง โดยใช้จำนวนเงินหรือระยะเวลาเป็นระยะทางของเส้นเชื่อมจุดแต่ละเส้น ซึ่งเป็นประโยชน์อย่างมากในการย่นระยะเวลา และลดต้นทุนในการขนส่งสินค้า

อ้างอิง:

เขียนโดย

Jetzada Chuaychuwong

นิสิตภาควิชาคณิตศาสตร์ ผู้หลงใหลในความเรียบง่ายที่แฝงไปด้วยความซับซ้อน