ตอนผมไปเข้าค่ายคอมพิวเตอร์ หนึ่งในสิ่งมหัศจรรย์ที่ได้เรียนรู้คือ algorithm ต่างๆ
ที่มนุษย์คิดค้นหลังจากมีคอมพิวเตอร์ ภายในระยะเวลาเพียง 70-80 ปี มีการคิดโน่นนี่นั่นออกมามากมาย หาวิธีทำงาน วิธีประมวลผลให้ได้เร็วที่สุด
หนึ่งใน algorithm ที่ผมประทับใจมากๆ คือ Single-Source Shortest Paths หรือ SSSP ที่คิดค้นโดย Edsger W. Dijkstra นักวิทยาการคอมพิวเตอร์ชาวดัตช์ (1930–2002) ที่เป็นหนึ่งในตำนานของวงการคอมพ์ยุคแรกๆ
เขาคิดค้นคิดอัลกอริทึม Dijkstra’s Shortest Path ในปี 1956 ตอนกำลังเดินเล่นไปซื้อกาแฟ (เขาเล่าว่าใช้เวลาประมาณ 20 นาที แถมทำบนกระดาษดินสอด้วย)
ผลงานไม่ได้มีแค่ algorithm ในการหาเส้นทางสั้นที่สุด เขายังเป็นคนผลักดันการพัฒนา structured programming และแนวคิด “โปรแกรมต้องถูกต้องโดยการออกแบบ” (correctness by construction) ที่เป็นรากฐานของวงการ software มาจนถึงปัจจุบัน
เขายังไม่กลัวที่จะวิจารณ์คนอื่นแรงๆ เขามีจดหมายและเรียงความที่ด่าโค้ดมั่ว ด่า goto ด่า naming ไม่ดี เต็มไปหมด ถ้าให้เปรียบ คงเหมือน Linus Torvalds ในสมัยนี้
และเขาก็ได้รางวัล Turing Award ปี 1972 ซึ่งเป็นเหมือนรางวัลโนเบลของสายคอมพ์เลยทีเดียว
Dijkstra’s algorithm คือวิธีหาทางสั้นที่สุดจากจุดเริ่มต้น (source) ไปยังจุดอื่นๆ ในกราฟที่มี น้ำหนักขอบเป็นค่าบวกหรือศูนย์ เท่านั้น
คิดภาพว่าเป็นการเดินในเมืองที่มีถนนหลายเส้น แต่ละเส้นมี “ค่าใช้จ่าย” (เวลา ระยะทาง หรือค่าโดยสาร) และคุณอยากรู้ว่าไปทุกที่ต้องจ่ายน้อยสุดเท่าไหร่ จึงถูกเรียกว่าเป็น Single source เพราะมันค้นหาคำตอบจากจุดเริ่มต้นจุดเดียวไปยังทุกจุดที่เหลือ
ในตอนแรก algorithm ของเขาเป็น O(n^2) ซึ่งยังช้าอยู่ แต่ Fredman & Tarjan (1984) ได้ปรับ algorithm ของ Dijkstra ให้เปลี่ยนไปใช้ Fibonacci priority heap จนทำให้มันเร็วขึ้นเป็น O(n log n + m) ซึ่งคนในวงการส่วนใหญ่เชื่อกันว่ามันน่าจะเร็วที่สุดแล้ว
แต่ใน paper จากนักวิจัยชาวจีนนี้อ้างว่า พบ algorithm ใหม่ ที่ทำได้ในเวลา O(m log^(2/3) n) ลดลำดับกำลังลงได้จริง ซึ่งนี่คือการ “ทะลุกำแพง sorting barrier” ที่เชื่อว่าติดมานาน โดยไม่จำเป็นต้องใช้ priority queue
อัลกอริทึมของ Dijkstra จำเป็นต้องจัดลำดับ (sorting) เส้นทางทั้งหมดใน “ขอบเขตการขยาย” หรือ frontier อย่างต่อเนื่อง เพื่อรักษาลำดับของระยะทางจากน้อยไปมาก ซึ่งเป็นสาเหตุสำคัญที่ทำให้ประสิทธิภาพถูกจำกัดที่ n log n
Algorithm ใหม่นี้เลือกที่จะคำนวณเฉพาะระยะทางสั้นที่สุดไปยังทุกจุด โดยไม่จำเป็นต้องคงลำดับของจุดทั้งหมดแบบสมบูรณ์ จึงสามารถหลีกเลี่ยงต้นทุนจากการจัดลำดับได้สำเร็จ
แนวทางนี้ใช้กลยุทธ์เลือก “pivot node” จำนวนเล็กและเทคนิคการจัดกลุ่ม (bucketing)
และเป็นครั้งแรกที่มีการพิสูจน์ให้เห็นว่า Dijkstra ไม่ optimal สำหรับปัญหา SSSP บน sparse graph ถึงแม้อัลกอริทึมนี้ไม่ได้แทนที่ Dijkstra โดยตรง เนื่องจาก Dijkstra ยังคงเหมาะสมในกรณีที่ต้องการลำดับจุดครบถ้วน หรือมีเงื่อนไขการประมวลผลพิเศษ แต่ผลงานนี้ได้พิสูจน์ว่าข้อจำกัดด้านความเร็วสูงสุดของปัญหา shortest path ใน sparse graph ไม่ได้เป็นเพดานที่ถาวร หากแต่เป็นข้อสมมุติที่สามารถก้าวข้ามได้ด้วยวิธีคิดใหม่
วันหนึ่งในอนาคต ตำราทุกเล่มที่เคยบอกว่า Dijkstra บน sparse graph “เกือบจะดีที่สุดแล้ว” อาจต้องเตรียมพิมพ์เพิ่มพร้อมแก้โน้ตเชิงอรรถว่ามีของใหม่เจ๋งกว่าเดิมแล้ว
ส่วนจะถูกต้องมั้ย จริงมั้ย ไว้รอผู้เชี่ยวชาญมาวิเคราะห์ครับ แต่เปิดผ่านคร่าวๆ ดูค่อนข้างเข้าใจง่ายดีครับ
- 4
โฆษณา
- ดาวน์โหลดแอปพลิเคชัน
- © 2025 Blockdit
