ใช้ Dijkstra's algorithm ในการหาเส้นทาง (ชั้น 1)

    ในการที่จะคำนวณหาเส้นทางที่สั้นที่สุดนั้นจำเป็นจะต้องมีการกำหนดจุด หรือ node ลงไปบนแผนที่จริงก่อน และทำการใส่ระยะทางระหว่างจุดแต่ละจุด จึงจะสามารถคำนวณเส้นทางที่สั้นที่สุดได้ โดยในตอนนี้ผมได้ทำการวาดกราฟที่กำหนดจุดเทียบกับสถานที่จริงของตึกคณะวิศวกรรมศาสตร์ในชั้นที่ 1 ไว้ประมาณนี้ ( ตัวกราฟยังอยู่ในขั้นทดลองอาจจะมีผิดพลาด ยังไม่ถูกต้องทั้งหมด )

                                    

                                 


    โดยในการทดลองเราจะทดลองเดินทางจากจุด A ไปยังจุด H หรือ จากหน้าตึก 81 ไปยังหน้าตึก 88 เส้นทางไหนจะสั้นที่สุด ซึ่งผลการนำข้อมูลของกราฟที่ได้ไประมวลผลเป็นดังนี้

    A=>B=>D=>F=>G=>H จะเป็นเส้นทางที่สั้นที่สุด โดยมีระยะรวม 227 เมตร

    ซึ่งถ้าอ้างอิงจากกราฟนี้ จะสามารถเดินทางได้อีก 2 ทาง ได้แก่

    A=>B=>C=>E=>G=>H และ  A=>B=>D=>E=>G=>H ซึ่งทั้ง 2 เส้นทางนี้จะได้ระยะทางรวมเป็น 252 เมตร ซึ่งมากกว่า เส้นทางที่ประมวลผลได้

สิ่งที่จะทำต่อไป

    1) ทดลองเพิ่มเติมกับชั้นที่ 2 และ 3
    2) แก้ไขเพิ่มเติมกราฟของชั้นที่ 1

Dijkstra's algorithm in Javascript

    จากครั้งที่แล้วเราได้หาตัวอย่างการ implement โค้ดของ Dijkstra's algorithm ในภาษา Python ไปแล้ว แต่เนื่องจากว่าภาษาที่เราใช้ในการพัฒนาแอปพลิเคชั่นคือภาษา Javascript เราจึงค้นคว้าหาข้อมูลเกี่ยวกับการ implement algorithm ดังกล่าว
    ซึ่งก็ได้มีหลายต่อหลายคนได้ทำและก็แชร์ข้อมูลผ่านต่างเว็บไซต์ต่างๆมากมาย โดยแต่ละแหล่งข้อมูลก็ได้มีวิธีการทำที่แตกต่างกัน แต่ผลลัพธ์ที่ได้ออกมานั้นก็จะเป็นในลักษณะคล้ายๆกัน คือเป็น array เรียงลำดับจาก node เริ่มต้นไปยัง node ถัดๆไป จนถึง node ปลายทางได้สำเร็จโดยใช้จะเป็นเส้นทางที่ใช้ระยะทางสั้นที่สุด
    ในบรรดาหลายๆแหล่งข้อมูลนั้น ก็มีที่ผมนั้นสนใจอยู่ที่หนึ่งก็คือ Link โดยจะตัวโค้ดนั้นสามารถนำมาทดลองใช้ได้ง่าย และโค้ดของส่วนการสร้างกราฟนั้นก็ไม่ซับซ้อนมากนัก เข้าใจได้ง่าย

 

    ในส่วนของการสร้างข้อมูลกราฟนั้นสามารถทำได้ดังนี้

    จากตัวอย่างกราฟด้านบน ถ้าเรานำมาแปลงเป็นโค้ดจะได้ดังนี้ 

    โดยวิธีการใส่ข้อมูลนั้นจะเป็นลักษณะของการนำ node ทุกตัว มาใส่รายละเอียดข้อมูลว่าเชื่อมกับจุดใดบางด้วยระยะทางเท่าไร ซึ่งจะไม่เหมือนกับตัวอย่างของภาษา Python ที่เราได้ทดลองในบทความครั้งที่แล้ว โดยคำตอบที่ได้จะเป็น A => B => D => F

                                                    

Dijkstra's algorithm in Python

    จากบทความที่แล้วผู้เขียนได้อธิบายการแก้ปัญหาการหาเส้นทางที่สั้นที่สุด โดยการใช้ Dijkstra's algorithm แบบพื้นฐาน โดยสามารถใช้มือคิดไปแล้ว ในส่วนของการเขียนโปรแกรมนั้นก็ได้มีบุคคลหลายท่านที่ได้นำขั้นตอนวิธีดังกล่าวมาเขียนให้อยู่ในรูปของโค้ดในหลายๆภาษา ซึ่งตัวผู้เขียนก็ได้ไปลองศึกษาโค้ด Dijkstra's algorithm ที่ใช้ภาษา Python ในการพัฒนา จากเว็บ https://dev.to/mxl/dijkstras-algorithm-in-python-algorithms-for-beginners-dkc 

    ในโค้ดตัวอย่างที่ทางเจ้าของบทความนำมาให้เราศึกษานั้นเราสามารถที่จะนำมาใช้ได้เลย โดยส่วนสำคัญที่เราจะต้องสนใจเพื่อที่จะใช้งานชุดโค้ดดังกล่าวนั้นมี 3 ส่วนด้วยกันดังนี้

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

2. ส่วนของการเรียกใช้ฟังก์ชั่น จะต้องใส่ค่าลงไปให้ 2 ตัว ได้แก่ จุดเริ่มต้น และ จุดปลายทาง ในตัวอย่างด้านบนจะเป็น จากจุด a ไปยังจุด e 

3. ส่วนของ output จะออกมาเป็น list  โดยสมาชิกใน list จะเป็นการเรียงลำดับจุดที่จะใช้ค่าระยะทางน้อยที่สุด

สิ่งที่ต้องทำต่อไป

1. หาวิธีขั้นตอนการทำ Dijkstra's algorithm ในภาษา Javascript         

2. ต้องเริ่มกำหนดจุดในตัวของแผนที่ว่าจะให้จุดแต่ละจุดอยู่ตรงไหนในสถานที่จริง และแต่ละจุดนั้นห่างกันเท่าไร

Dijkstra's algorithm

    ในสัปดาห์ก่อนๆเราได้มีการพูดคุยกันว่าจะใช้ตัวของ Dijkstra's algorithm ในการหาเส้นทางที่สั้นที่สุดในการเดินทางจากตำแหน่งปัจจุบันไปยังจุดหมายปลายทาง ซึ่งขั้นตอนวิธีทำนั้นค่อนข้างเรียบง่ายและไม่ซับซ้อนมากนัก โดยจะมีทั้งหมด 6 ขั้นตอนดังนี้ (ลิงค์แหล่งที่มา https://th.wikipedia.org/wiki/ขั้นตอนวิธีของไดก์สตรา, https://dev.to/mxl/dijkstras-algorithm-in-python-algorithms-for-beginners-dkc)

หมายเหตุ ผู้เขียนแนะนำให้อ่านขั้นตอนแล้วดูรูปภาพประกอบไปด้วยเพราะจะทำให้เข้าใจง่ายมากยิ่งขึ้น

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

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

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

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

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

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

รูปตัวอย่างจาก https://th.wikipedia.org/wiki/ขั้นตอนวิธีของไดก์สตรา

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

ความคืบหน้าโปรเจค 04/01/2019

สิ่งที่ได้ทำไป

- เพิ่มแถบ Status ด้านบน (Incomplete)

        แถบสถานะที่จะต้องแสดงหลังจากที่เริ่มต้นการนำทาง แต่ในตอนนี้ให้แสดงอยู่ตลอด และแสดงเพียงค่าระยะห่างจากจุดหมาย จะมีการเพิ่มเติมเรื่องการนำทางภายหลัง

- เพิ่ม Indicator บอกตำแหน่งของ model

        Indicator เป็นลูกศรบอกทิศทางของตัว Model ช่วยให้ผู้ใช้หันหน้าไปทิศทางที่ตัว Model อยู่ได้ถูกต้อง

เป้าหมายต่อไปที่คาดว่าจะทำ

• Search Box
• Menu