นักวิทย์ทุบกำแพง 40 ปี! เจออัลกอริทึม 'หาทางลัด' ที่เร็วกว่าตำรา

ในที่สุดกำแพงที่ขวางวงการวิทยาศาสตร์คอมพิวเตอร์มานาน 40 ปีก็พังทลายลง เมื่อทีมนักวิจัยได้พัฒนาอัลกอริทึมใหม่สำหรับแก้ปัญหาคลาสสิกอย่าง 'การหาเส้นทางที่สั้นที่สุด' (Shortest Path Problem) ซึ่งเร็วกว่าอัลกอริทึมในตำราที่ใช้กันมาอย่างยาวนานอย่าง Dijkstra's Algorithm ได้สำเร็จ

ปัญหานี้เปรียบง่าย ๆ ก็เหมือนการหาเส้นทางจากบ้านไปที่ทำงานหรือซูเปอร์มาร์เก็ตที่เร็วที่สุด อัลกอริทึมสุดคลาสสิกของ Edsger Dijkstra ที่คิดค้นในปี 1956 จะทำงานโดยการหาจุดที่ใกล้ที่สุดก่อน แล้วค่อย ๆ ขยายวงออกไป ซึ่งวิธีนี้มีข้อจำกัดที่เรียกว่า 'กำแพงการจัดเรียง' (Sorting Barrier) เพราะยิ่งมีจุดให้สำรวจเยอะ ก็ยิ่งเสียเวลาไปกับการจัดลำดับความใกล้ไกล ทำให้นักวิจัยไปต่อไม่ได้มาตั้งแต่ปี 1984

แต่ Ran Duan นักวิทยาศาสตร์คอมพิวเตอร์จาก Tsinghua University ไม่ยอมแพ้ เขาและทีมได้คิดค้นแนวทางใหม่ที่ฉีกทุกกฎเกณฑ์ แทนที่จะเสียเวลาจัดเรียงข้อมูลเพื่อหาจุดที่ใกล้ที่สุด อัลกอริทึมใหม่นี้จะจัดกลุ่มจุดต่าง ๆ เป็นคลัสเตอร์ แล้วเลือกสำรวจแค่บางจุดจากแต่ละกลุ่มเท่านั้น ที่น่าสนใจคือ พวกเขาหยิบเอาอัลกอริทึมที่ขึ้นชื่อว่าช้ามากอย่าง Bellman-Ford มาใช้ประโยชน์อย่างชาญฉลาด โดยใช้มันเพียงไม่กี่สเต็ปเพื่อ 'สอดแนม' หาจุดที่เป็นเหมือน 'สี่แยกสำคัญ' ล่วงหน้า ทำให้การค้นหาเส้นทางโดยรวมมีประสิทธิภาพและเร็วกว่าเดิม

Robert Tarjan หนึ่งในนักวิจัยที่เคยพัฒนาอัลกอริทึม Dijkstra จนสุดทางเมื่อ 40 ปีก่อน ถึงกับเอ่ยปากชมว่า 'เป็นผลลัพธ์ที่น่าทึ่ง' เพราะแนวคิดของทีมนี้กล้าหาญมากที่คิดจะทลายกำแพงนี้ลง แถมเทคนิคที่ใช้ก็ไม่ได้ซับซ้อนจนเกินไป จน Mikkel Thorup จาก University of Copenhagen บอกว่า 'เรื่องนี้น่าจะถูกค้นพบได้ตั้งแต่ 50 ปีที่แล้วด้วยซ้ำ แต่มันก็ไม่'

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