การหาเส้นทางที่สั้นที่สุด

สวัสดีครับ เป็นยังไงกันบ้าง หวังว่าทุกคนสบายดีนะครับ ช่วงนี้อากาศเริ่มเย็นลงแล้ว ก็ต้องรักษาเนื้อรักษาตัวกันให้ดีๆนะครับ ถ้ามีโอกาสก็ไปฉีดยาวัคซีนป้องกันไข้หวัดใหญ่นะครับ อากาศเย็นๆ อย่างนี้ทำให้นึกถึงช่วงพักฤดูร้อน 2 ปีที่แล้ว คณะเพื่อนๆ ก็ได้วางแผนเตรียมตัวขับรถเที่ยวกัน เราก็ได้ตกลงเลือกสถานที่ต่างๆ ที่น่าสนใจ แล้วก็ได้ใช้ โปรแกรมบนเวปช่วยจัดหาเส้นทางที่สั้นที่สุดจากที่หนึ่งไปยังอีกที่หนึ่ง โปรแกรมพวกนี้ดีมากๆ เลยนะครับ บอกลายละเอียดตั้งแต่ออกจากที่ต้นทาง บอกเมื่อไหร่ที่ต้องเลี้ยว บอกระยะทางที่ใช้บนถนนแต่ละเส้น และ ระยะทางรวมที่ใช้เดินทาง เว็ปตัวอย่างที่มีให้ทดลองใช้นะครับ คือ ของ http://maps.yahoo.com และ http://maps.expedia.com ลองเข้าไปใช้ดูนะครับ แต่ว่าเวปทั้งหมดนี้ยังไม่สามารถให้บริการกับที่อยู่ในเมืองไทยได้นะครับ เพราะฉะนั้นก็ทดลองใช้ที่อยู่นี้ทดลองดูนะครับ จะใช้ที่อยู่ไหนเป็นต้นทาง หรือ ปลายทางก็ได้นะครับ ทดลองดูว่าให้ความแตกต่างยังไง 1. 512 Hunt Club Rd., Blacksburg, VA 24060 2. 9204 Springhill Ln, Greenbelt, MD 20770

เป็นไงครับ เห็นความสามารถของโปรแกรมที่อยู่บนเว็ปแล้วนะครับ โปรแกรมพวกนี้ อาศัย หลักการพื้นฐานทางคณิตศาสตร์ที่เรียบง่าย รวมเข้ากับ ข้อมูลด้าต้าเบสของที่อยู่ และ สถานที่ของที่อยู่ขึ้นบนแผนที่ ด้าต้าเบสนี้เรียกว่า Geographic Information Systems (GIS) ข้อมูลที่เก็บในนี้ก็รวมไปถึงถนนต่างๆ ขนาดของถนน และ ทิศทางที่ถนนไป ซึ่งสามารถนำมาเป็นข้อมูลในการหาเส้นทางที่ต้องการ หลักการพื้นฐานทางคณิตศาสตร์ที่ใช้ในเว็บเหล่านี้ อยู่ในสาขาที่เรียกว่า Optimization และ นักคณิตศาสตร์ก็อาศัยรูปภาพเป็นตัวแทนของปัญหา ซึ่งรูปภาพเหล่านี้เรียกว่า เน็ทเวอร์ก (Network) หรือ กราฟ (Graph) ที่ผมเคยเล่าให้ฟังไปบ้างแล้ว ในฉบับที่ 2 นะครับ ซึ่งเน็ทเวอร์กนี้ประกอบไปด้วย เซ็ทของวงกลมที่เรียกว่า โหนด (Node) และ เชื่อมโยงด้วยเส้นที่เรียกว่า อาร์ก (Arc) ในการนำเน็ทเวอร์กไปใช้ส่วนมากจะให้โหนดแทนเมือง สี่แยก ป้ายรถเมล์ สถานีรถไฟ ข้อต่อของท่อน้ำ หรือ ทาวเวอร์ของโทรศัพท์ไร้สาย สำหรับอาร์กจะนำไปใช้เป็นตัวแทนของ สิ่งเชื่อมระหว่างโหนดต่างๆ ไม่ว่าจะเป็นถนน รางรถไฟ ท่อน้ำ สายเคเบิล หรือแม้กระทั่งสิ่งที่ไม่มีตัวตน เช่น ความสันพันธ์ระหว่างโหนด หรือ การติดต่อเชื่อมโยงระหว่างโหนด ในบางครั้งบนอาร์กจะมีตัวเลขที่แสดงถึงระยะทางที่ใช้เดินทางระหว่างโหนด หรือ ระยะเวลาที่ใช้ระหว่างโหนด หรือ ค่าใช้จ่ายบนเส้นทางนั้นๆ สำหรับวิธีการพื้นฐานทางคณิตศาสตร์ที่ใช้แก้ปัญหาในการหาเส้นทางบนเว็ปนั้นเรียกว่า วิธีการหาเส้นทางที่สั้นที่สุด (Shortest path) ระหว่างโหนด ซึ่งวิธีการนี้ได้นำมาเสนอในปี 1959 โดย Dijkstra และ วิธีการนี้ก็ได้มีชื่อว่า Dijkstra's algorithm เพื่อเป็นการให้เกียรติ และ ขั้นตอนของแอลกอริทึมสมีดังต่อไปนี้นะครับ
Dijkstra's Algorithm
1. ก่อนอื่นเรา จะเรียกโหนด ตามชื่อให้ไป และ แต่ละโหนด v เราจะอ้างถึงฟังก์ชั่น d(v) และ pred(v) ในตอนเริ่ม ทุกโหนดจะมีค่า d(v) = Infinity และ pred(v) = 0 2. สำหรับอาร์กที่เชื่อมระหว่างโหนด i และ j เราจะเรียกว่า arc(i,j) ส่วนระยะทางระหว่างโหนด i และ j เราจะเรียกว่า weight(i,j) 3. เราจะแบ่งกลุ่มของโหนดเป็น 2 กลุ่ม คือ กลุ่ม โหนดสีแดง และ กลุ่ม โหนดสีเหลือง ในตอนเริ่มต้นทุกโหนดจะมีสีเหลือง 4. เลือกโหนดเริ่มต้น จากกลุ่มสีเหลือง สมมุติว่าเป็นโหนด k และ ให้ d(k) = 0 5. (ขั้นเลือกโหนดระบายสีแดง) เลือกโหนด j จากกลุ่มสีเหลือง โดยที่มีค่า d(j) น้อยที่สุดในกลุ่มสีเหลือง ระบายสีแดงใส่โหนด j และ arc(j,pred(j) ) 6. (ขั้นปรับปรุุงระยะทาง) พิจารณาทุกอาร์กที่มีปลายหนึ่งติดกับโหนดที่มีสีแดง และ อีกปลายหนึ่งยังไม่มีสีแดง สมมุติว่าเป็น arc(i,j) เราจะได้โหนด i สีแดง และ โหนด j สีเหลือง และ เรียกโหนด j เป็นโหนดที่ติดกับโหนด i (Adjacent node) ถ้า d(i) + weight(i,j) < d(j) เราก็จะเปลี่ยนค่าของ d(j) โดยให้ d(j) = d(i) + weight(i,j) และ pred(j) = i 7. กลับไปที่ทำขั้นที่ 5, และ 6 จนกระทั่ง ทุกโหนดมีสีแดง แล้วเราก็จะได้เส้นทางที่สั้นที่สุดจากโหนดที่เริ่มต้นไปยังทุกๆโหนด ก่อนที่จะไปดูตัวอย่างกัน ขออธิบายเล็กน้อยว่า ฟังก์ชั่น d(v) และ pred(v) คือ อะไรนะครับ ทั่งสองฟังก์ชั่น เป็นฟังก์ชั่นที่จะคอยบอกเราว่า ระยะทางที่สั้นที่สุดจากจุดเริ่มต้นถึง โหนด v ต้องเดินทางเป็นระยะทางอย่างน้อยเท่ากับ d(v) และ ต้องเดินทางผ่านโหนด pred(v)

ตัวอย่างสำหรับ Dijkstra's Algorithm

เราลองมาดูตัวอย่างของแอลกอริทึมนะครับ มีกระดาษกับดินสอพร้อมหรือยังครับ ถ้าพร้อมแล้วก็ลอง ไปดูโจทย์นะครับ

ตัวอย่างสำหรับ Dijkstra's Algorithm

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





ก็เสร็จเรียบร้อยนะครับ เราลองมาดูสิว่าผลที่ได้เป็นยังไงนะครับ ถ้าเราต้องการเดินทางจาก A ไปยัง E เราต้องเดินทางผ่านเมือง F แล้วมีระยะทางในการเดินทาง เท่ากับ 9 เป็นยังไงครับพอจะเข้าใจหลักการพื้นฐานกันแล้ว ถ้าใครสนใจไปดูโปรแกรมที่เขียนด้วย Java ก็เข้าไปดูที่เวปนี้นะครับ http://www.cudenver.edu/~hgreenbe/sessions/dijkstra/DijkstraApplet.html ตอนนี้ทุกคนก็สามารถที่จะทำเวปให้บริการ หาเส้นทางขับรถ ในเมืองไทยกันได้ อย่าลืมอีเมล์มาบอกเวปไซส์ให้ผมนะครับ เผ่ือจะได้วางแผนขับเที่ยวในเมืองไทยกับเพื่อนๆ แล้วเจอกันใหม่ฉบับหน้าครับ