ทีมนักวิจัยจากมหาวิทยาลัยชิงหวา (Tsinghua University) ร่วมมือกับมหาวิทยาลัยสแตนฟอร์ด สร้างความก้าวหน้าครั้งสำคัญในด้านความซับซ้อนเชิงคำนวณสำหรับปัญหาเส้นทางสั้นที่สุดแบบต้นทางเดียว (single-source shortest path, SSSP) โดยงานวิจัยนี้ได้รับรางวัล Best Paper ในการประชุม STOC 2025
วิธีที่ใช้กันมาอย่างยาวนานคืออัลกอริทึมของ Dijkstra ซึ่งมีความซับซ้อนเชิงเวลาเป็น O(m + n log n) (n = จำนวนโหนด, m = จำนวนเส้นเชื่อม)
พจน์ log n เป็นส่วนที่เกี่ยวข้องกับ priority queue หรือการเรียงลำดับ (sorting) และตลอด 40 ปีที่ผ่านมา ก็ยังไม่มีการปรับปรุงที่ก้าวข้ามข้อจำกัดในส่วนนี้ได้
อัลกอริทึมใหม่นี้ลดความซับซ้อนเชิงเวลาลงเหลือ O(m · log^(2/3) n)
เนื่องจาก log^(2/3) n เพิ่มขึ้นช้ากว่า log n (กล่าวคือเพิ่มขึ้นน้อยกว่า log n) ความแตกต่างจึงยิ่งชัดเจนเมื่อจำนวนโหนดมีขนาดใหญ่มาก
18 ความคิดเห็น
ทำให้นึกถึงความทรงจำ(?) ตอนที่ทำงานอยู่บริษัทซอฟต์แวร์ระบบนำทางรถยนต์และพัฒนาโมดูลค้นหาเส้นทางในช่วงปลายยุค 2000 ขึ้นมาเลย
Dijkstra ช้าเกินไปสำหรับการค้นหาเส้นทางในระบบนำทางเลยไม่ค่อยใช้กัน แต่จะใช้การค้นหาแบบ A* (A Star) ซึ่งเป็นเวอร์ชันที่ปรับปรุงด้วยฮิวริสติกแทน พอลองค้นดูก็พบว่า A* ไม่ใช่อัลกอริทึม SSSP แต่เป็นอัลกอริทึม SPSP (Single-Pair Shortest Path) นั่นเอง
ถ้าจะบอกว่าเหนือกว่าอัลกอริทึมที่เร็วในกรณีที่เป็น sparse ก็ดูจะยังพูดได้ไม่เต็มปากนัก
CLRS เพิ่งออกฉบับปรับปรุงมาได้ไม่นานเอง คงต้องพิมพ์ใหม่อีกแล้วสินะ
ให้ความรู้สึกเหมือนมีอัลบั้มใหม่ของวงดังอย่าง The Beatles หรือ Oasis ที่ยังได้รับความนิยมมาจนถึงทุกวันนี้ ออกมาเป็นครั้งแรกในรอบ 41 ปีเลยครับ ทั้งน่าทึ่งและชวนสนใจมาก 555
อเมริกาอาจมีอยู่แล้วก็ได้? โหดจัด
สวยงามจริง ๆ เลย ตะลึงมาก
ช่วงนี้จีนมาแรงจริง ๆ
ชื่ออัลกอริทึมจะถูกตั้งว่าอะไรนะ
เดี๋ยวคงมีใครสักคนเอาเงื่อนไขจำกัดแบบนั้นไปออกโจทย์ใน Baekjoon แน่ ๆ ตื่นเต้นจัง
ชวนให้นึกถึง Dijkstra เลย..
ว้าว... สุดยอดมาก...
เจ๋งมากครับ
ว้าว......
อันนี้ทำได้จริง ๆ แฮะ...
ว้าว~~
ว้าว....
คงต้องเพิ่มเนื้อหาในคาบเรียนอัลกอริทึมกันแล้วล่ะ 555
โอ๊ย...