- ทีมวิจัยของ Rasmus Kyng จาก ETH Zurich ได้พัฒนาอัลกอริทึมที่คำนวณปัญหาการหา การไหลสูงสุด ในเครือข่ายและลดต้นทุนการขนส่งให้น้อยที่สุดด้วยความเร็วที่เกือบถึงขีดจำกัดทางคณิตศาสตร์
- อัลกอริทึมใหม่นี้เป็นแนวทางแบบ เวลาเกือบเชิงเส้น ที่ให้คำตอบในระดับเวลาแทบเท่ากับเวลาที่ใช้ในการอ่านข้อมูลเครือข่าย และสามารถนำไปใช้กับการคำนวณเครือข่ายอย่างรถไฟ ถนน ทางน้ำ และอินเทอร์เน็ตได้
- ในอดีต หากให้จำนวนการเชื่อมต่อเป็น m ก่อนปี 2000 ไม่มีอัลกอริทึมที่เร็วกว่าระดับ m^1.5 และในปี 2004 อยู่ที่ระดับ m^1.33 แต่แนวทางของ Kyng ลด เวลาคำนวณเพิ่มเติม หลังจากอ่านข้อมูลให้อยู่ในระดับที่มองข้ามได้
- ทีมวิจัยคำนวณเส้นทางสั้นที่สุดและการไหลสูงสุดต้นทุนต่ำสุดในเวลาเกือบเชิงเส้นได้ ไม่เพียงในเครือข่ายแบบคงที่และมีทิศทาง แต่ยังรวมถึง กราฟเพิ่มขึ้น ที่มีการเพิ่มการเชื่อมต่อ และ กราฟลดลง ที่มีการลบการเชื่อมต่อ
- สิ่งนี้เป็นพื้นฐานสำหรับการคำนวณเส้นทางที่เหมาะสมใหม่อย่างรวดเร็วในสถานการณ์ที่เครือข่ายจริงเปลี่ยนแปลง เช่น การปิดและเปิดใช้งานบางส่วนของ Gotthard Base Tunnel หรือดินถล่มบนทางหลวง A13
คำนวณปัญหาการไหลของเครือข่ายด้วยความเร็วเกือบถึงขีดจำกัด
- อัลกอริทึมการไหลของเครือข่าย ของทีมวิจัย Rasmus Kyng จัดการกับปัญหาการหาเส้นทางที่สามารถส่งการไหลสูงสุดในเครือข่าย พร้อมลดต้นทุนการขนส่งให้น้อยที่สุด
- ตัวอย่างที่เป็นตัวแทนคือสถานการณ์ที่ต้องหาเส้นทางเพื่อขนส่งสินค้าให้ได้มากที่สุดจาก Copenhagen ไป Milan อย่างรวดเร็วและประหยัดที่สุด
- สามารถคำนวณการไหลต้นทุนต่ำที่เหมาะสมที่สุดในเครือข่ายที่มีการเชื่อมต่อและความจุ เช่น รถไฟ ถนน ทางน้ำ และอินเทอร์เน็ต
- ความเร็วในการคำนวณลดลงจนเกือบอยู่ในระดับเดียวกับเวลาที่คอมพิวเตอร์ใช้อ่านข้อมูลเครือข่าย
ทำไมจึงเป็นอัลกอริทึมที่ “เร็วที่สุด”
- ก่อนหน้านี้ เวลาที่ใช้คำนวณการไหลที่เหมาะสมที่สุดยาวนานกว่าเวลาที่ใช้ประมวลผลข้อมูลเครือข่ายมาก
- ยิ่งเครือข่ายใหญ่และซับซ้อนขึ้น เวลาคำนวณที่ต้องใช้ก็เพิ่มขึ้นเร็วกว่าขนาดของปัญหา
- แนวทางของ Kyng ทำให้ เวลาคำนวณ และ ขนาดเครือข่าย เพิ่มขึ้นในอัตราส่วนเดียวกัน
- หากให้จำนวนการเชื่อมต่อของเครือข่ายเป็น m แค่การอ่านข้อมูลหนึ่งครั้งก็ใช้เวลา m
- ก่อนปี 2000 ไม่มีอัลกอริทึมที่คำนวณได้เร็วกว่า m^1.5
- ในปี 2004 ปริมาณการคำนวณที่ต้องใช้ในการแก้ปัญหาลดลงเหลือ m^1.33
- อัลกอริทึมของ Kyng ลดเวลาคำนวณเพิ่มเติมเพื่อไปถึงคำตอบหลังจากอ่านข้อมูล ให้อยู่ในระดับที่มองข้ามได้
การประเมินและการขยายอัลกอริทึมเวลาเกือบเชิงเส้น
- ทีมวิจัยของ Kyng เผยแพร่论文ที่มีการพิสูจน์ทางคณิตศาสตร์ของแนวคิดนี้เมื่อ 2 ปีก่อน
- อัลกอริทึมที่เร็วเกือบเหมาะที่สุดเช่นนี้เรียกว่า อัลกอริทึมเวลาเกือบเชิงเส้น
- Daniel A. Spielman เปรียบอัลกอริทึมนี้กับ Porsche ที่แซงรถม้า
- งานวิจัยดังกล่าวได้รับ Best Paper Award ในงาน IEEE Annual Symposium on Foundations of Computer Science, FOCS ปี 2022
- Communications of the ACM ก็ได้กล่าวถึงงานวิจัยนี้ และกองบรรณาธิการ Quanta เลือกอัลกอริทึมของ Kyng เป็นหนึ่งใน 10 การค้นพบด้านวิทยาการคอมพิวเตอร์ประจำปี 2022
จากเครือข่ายคงที่สู่เครือข่ายที่เปลี่ยนแปลง
- อัลกอริทึมช่วงแรกมุ่งเน้นไปที่ เครือข่ายแบบตายตัว·คงที่ ซึ่งมีการกำหนดทิศทางของการเชื่อมต่อ
- การเชื่อมต่อแบบมีทิศทางมีโครงสร้างคล้ายถนนทางเดียวในเครือข่ายถนนเมือง
- หลังจากนั้น ทีมวิจัยได้พัฒนาอัลกอริทึมที่คำนวณการไหลที่เหมาะสมที่สุดได้แม้ในเครือข่ายที่ค่อย ๆ เปลี่ยนแปลงตามเวลา
- Simon Meierhans นำเสนออัลกอริทึมเวลาเกือบเชิงเส้นใหม่ในงาน Annual ACM Symposium on Theory of Computing, STOC ที่ Vancouver
- อัลกอริทึมนี้แก้ ปัญหาการไหลสูงสุดต้นทุนต่ำสุด ของเครือข่ายที่มีการเพิ่มการเชื่อมต่อใหม่
- ใน论文ฉบับที่สองซึ่งได้รับการตอบรับในงาน IEEE Symposium on Foundations of Computer Science, FOCS เดือนตุลาคม ทีมได้พัฒนาอัลกอริทึมที่รองรับการลบการเชื่อมต่อด้วย
- อัลกอริทึมทั้งสองระบุ เส้นทางสั้นที่สุด ในเครือข่ายที่มีการเพิ่มหรือลบการเชื่อมต่อ
ตัวอย่างการเปลี่ยนแปลงของเครือข่ายจริง
- Gotthard Base Tunnel ใน Switzerland ถูกปิดทั้งหมดหลังฤดูร้อนปี 2023 แล้วจึงกลับมาเปิดใช้งานบางส่วน
- บางส่วนของทางหลวง A13 ซึ่งเป็นเส้นทางทดแทนหลักของ Gotthard Road Tunnel ถูกทำลายจากดินถล่มเมื่อไม่นานมานี้
- เมื่อเกิดการเปลี่ยนแปลงเช่นนี้ คอมพิวเตอร์ บริการแผนที่ออนไลน์ และเครื่องมือวางแผนเส้นทางต้องคำนวณการเชื่อมต่อที่สั้นที่สุดและมีต้นทุนต่ำที่สุดระหว่าง Milan กับ Copenhagen ใหม่
- อัลกอริทึมใหม่ของ Kyng คำนวณเส้นทางที่เหมาะสมที่สุดได้ในเวลาเกือบเชิงเส้น แม้ในเครือข่ายที่มีการเพิ่มหรือลบการเชื่อมต่อ
- แม้เมื่อมีการเพิ่มการเชื่อมต่อจากเส้นทางอ้อมหรือเส้นทางใหม่ เวลาคำนวณเพิ่มเติมก็อยู่ในระดับที่มองข้ามได้
สองกลยุทธ์เดิมและวิธีผสานแบบใหม่
- การคำนวณการไหลของเครือข่ายต้องวิเคราะห์เครือข่ายหลายครั้งเพื่อหาเส้นทางการไหลที่เหมาะสมและมีต้นทุนต่ำสุด
- ในแต่ละรอบจะตรวจสอบการเปลี่ยนแปลง เช่น การเชื่อมต่อใดเปิดอยู่ ปิดอยู่ หรือแออัดเพราะถึงขีดจำกัดความจุแล้ว
- ก่อน Kyng นักวิทยาการคอมพิวเตอร์มักใช้หนึ่งในสองกลยุทธ์หลัก
- โมเดลเครือข่ายรถไฟ: ในแต่ละรอบ คำนวณทั้งส่วนหนึ่งของเครือข่ายที่การไหลของทราฟฟิกเปลี่ยนไป
- โมเดลโครงข่ายไฟฟ้า: ในแต่ละรอบ คำนวณทั้งเครือข่าย แต่ใช้ค่าเฉลี่ยเชิงสถิติของการไหลที่เปลี่ยนไปในแต่ละช่วงเพื่อเร่งการคำนวณ
- ทีมวิจัยของ Kyng นำข้อดีของทั้งสองกลยุทธ์มารวมกันเป็นแนวทางผสมแบบใหม่
- Maximilian Probst Gutenberg เห็นว่าการรวมขั้นตอนการคำนวณเล็ก ๆ จำนวนมากที่มีประสิทธิภาพและต้นทุนต่ำ จะเร็วกว่าขั้นตอนใหญ่ไม่กี่ขั้นมาก
บริบททางประวัติศาสตร์ของอัลกอริทึมการไหล
- ปัญหาการไหลของเครือข่ายเป็นหนึ่งในปัญหายุคแรก ๆ ที่ถูกแก้อย่างเป็นระบบด้วยอัลกอริทึมในทศวรรษ 1950
- อัลกอริทึมการไหลมีบทบาทสำคัญในการทำให้วิทยาการคอมพิวเตอร์เชิงทฤษฎีกลายเป็นสาขาวิจัยอิสระ
- อัลกอริทึมที่รู้จักกันดีของ Lester R. Ford Jr. และ Delbert R. Fulkerson ก็เกิดขึ้นในช่วงเวลานี้
- อัลกอริทึม Ford-Fulkerson แก้ ปัญหาการไหลสูงสุด ได้อย่างมีประสิทธิภาพ โดยขนส่งสินค้าให้ได้มากที่สุดผ่านเครือข่ายโดยไม่เกินความจุของแต่ละเส้นทาง
- งานวิจัยต่อมาชี้ให้เห็นว่า ปัญหาการไหลสูงสุด ปัญหาต้นทุนต่ำสุด และปัญหาการไหลของเครือข่ายหลายแบบ เป็นกรณีพิเศษของ ปัญหาการไหลต้นทุนต่ำสุด ทั่วไป
ข้อจำกัดของอัลกอริทึมเดิมและจุดเปลี่ยนในปี 2004
- อัลกอริทึมจำนวนมากก่อนงานวิจัยของ Kyng สามารถแก้ปัญหาเฉพาะอย่างหนึ่งได้อย่างมีประสิทธิภาพ แต่ยังไม่เร็วพอและยากที่จะขยายไปสู่ปัญหาการไหลต้นทุนต่ำสุดที่กว้างกว่า
- John Edward Hopcroft, Richard Manning Karp และ Robert Endre Tarjan ผู้สร้างอัลกอริทึมการไหลบุกเบิกในทศวรรษ 1970 ต่างได้รับ Turing Award
- Karp ได้รับรางวัลในปี 1985
- Hopcroft และ Tarjan ได้รับรางวัลในปี 1986
- ในปี 2004 Daniel Spielman, Shang-Hua Teng และต่อมา Samuel Daitch เขียนอัลกอริทึมที่ให้วิธีแก้ปัญหาได้รวดเร็วและมีประสิทธิภาพสำหรับปัญหาการไหลต้นทุนต่ำสุดด้วย
- กลุ่มนี้เปลี่ยนมุมมองจากรถไฟไปเป็น การไหลของไฟฟ้าในโครงข่ายไฟฟ้า
- ในโครงข่ายไฟฟ้า สามารถเบี่ยงการไหลของกระแสบางส่วนไปยังการเชื่อมต่อที่มีกระแสอื่นไหลอยู่แล้วได้
- Kyng ไม่ได้ทำตามแนวทางอัลกอริทึมอันทรงพลังของ Spielman สำหรับทั้งเครือข่ายโดยตรง แต่ได้นำแนวคิด การคำนวณเส้นทางบางส่วน ไปประยุกต์กับแนวทางเดิมของ Hopcroft และ Karp
- การคำนวณเส้นทางบางส่วนในแต่ละรอบมีบทบาทสำคัญในการทำให้การคำนวณการไหลทั้งหมดเร็วขึ้น
เครื่องมือคณิตศาสตร์และโครงสร้างข้อมูลใหม่
- ความก้าวหน้าของทีมวิจัย ETH Zurich ไม่ได้ตั้งอยู่บนอัลกอริทึมใหม่เท่านั้น แต่ยังรวมถึงการออกแบบ เครื่องมือคณิตศาสตร์ ที่ทำให้การคำนวณเร็วขึ้น
- ทีมวิจัยพัฒนาโครงสร้างข้อมูลใหม่สำหรับจัดระเบียบข้อมูลเครือข่าย
- โครงสร้างข้อมูลนี้ทำให้สามารถระบุการเปลี่ยนแปลงของการเชื่อมต่อในเครือข่ายได้อย่างรวดเร็วมาก
- การระบุการเปลี่ยนแปลงอย่างรวดเร็วทำหน้าที่เป็นปัจจัยที่เพิ่มความเร็วของวิธีแก้ปัญหาด้วยอัลกอริทึม
- อัลกอริทึมเวลาเกือบเชิงเส้นและโครงสร้างข้อมูลใหม่นี้วางพื้นฐานสำหรับการแก้ปัญหาขนาดใหญ่มากที่ก่อนหน้านี้ไม่สามารถคำนวณได้อย่างมีประสิทธิภาพ
งานวิจัยและแหล่งข้อมูลที่เกี่ยวข้อง
- Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality: งานวิจัย FOCS 2024 ว่าด้วยการไหลต้นทุนต่ำสุดและหัวข้ออื่น ๆ ในกราฟลดลง
- Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow: งานวิจัย STOC 2024 ว่าด้วยการตรวจจับวงจร, SCC, เส้นทางสั้นที่สุด s-t และการไหลต้นทุนต่ำสุดในกราฟเพิ่มขึ้น
- Maximum Flow and Minimum-Cost Flow in Almost-Linear Time: งานวิจัย FOCS 2022 ที่แก้การไหลสูงสุดและการไหลต้นทุนต่ำสุดในเวลาเกือบเชิงเส้น
- Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow: บทความที่เกี่ยวข้องจาก Communications of the ACM
- Researchers Achieve ‘Absurdly Fast’ Algorithm for Network Flow: บทความที่เกี่ยวข้องปี 2022 จาก Quanta Magazine
1 ความคิดเห็น
ความคิดเห็นบน Hacker News
อัลกอริทึมนี้มีความซับซ้อนเชิงเส้น เกือบเชิงเส้น แบบเชิงเส้นกำกับเมื่อ n -> inf
ช่วงท้ายวิดีโอบอกว่า การทำอัลกอริทึมนี้เป็น implementation ใด ๆ ก็ตาม ในโลกจริงน่าจะยากที่จะชนะอัลกอริทึมเดิม ๆ ได้
https://cacm.acm.org/research/almost-linear-time-algorithms-...
https://en.wikipedia.org/wiki/Galactic_algorithm
คำว่า ความเร็วที่เร็วที่สุดเท่าที่เป็นไปได้ เป็นคำกล่าวอ้างที่กล้ามากจริง ๆ
หลายครั้งการใช้เวลาแค่ 1% เพื่อให้ได้คุณภาพ 99% นั้นใช้งานได้จริงกว่ามาก
น่าสนใจที่คนคนเดียวกันยังทำงานวิจัยเพื่อทำให้ อัลกอริทึมสำหรับทฤษฎีล้วน ๆ ใช้งานได้ดีจริงด้วย [1]
แต่ดูเหมือนว่ากระบวนการนั้นจะใช้เวลาอีกราว 20 ปีเหมือนกัน [1] สร้างต่อจากความก้าวหน้าทางทฤษฎีในปี 2004 [2] และเท่าที่ผมเข้าใจ อัลกอริทึมเหล่านี้เพิ่งเริ่มใช้งานจริงได้ในปี 2024 ถ้าอย่างนั้นก็คงคาดหวังอัลกอริทึม minimum cost flow ที่ใช้งานได้จริงได้ในปี 2044
[1] https://arxiv.org/pdf/2303.00709
[2] https://arxiv.org/abs/cs/0310051
แต่ในทางทฤษฎีก็เป็นผลลัพธ์ที่เจ๋งมาก
บางครั้งรู้สึกเหมือนเราหลงทางไปหมดกับการใช้ความซับซ้อนเป็นตัวชี้วัด
มีอัลกอริทึมมากขึ้นเรื่อย ๆ ที่ปรับแต่ง ตัวชี้วัดความซับซ้อน จนสุดโต่ง แต่ในทางปฏิบัติไม่ได้มีประโยชน์
หลังจากผลงานที่ทำได้ง่ายหายไปหมด งานวิจัยอัลกอริทึมก็กลายเป็นอีกสาขาหนึ่งที่เฉพาะทางอย่างมาก และถ้าไม่ใช่นักวิจัยในสาขาที่ใกล้กันมาก ๆ บทความส่วนใหญ่ก็ไม่ค่อยคุ้มค่าที่จะใช้เวลาอ่าน
บทความที่เกี่ยวข้อง: https://news.ycombinator.com/item?id=31149038 (40 ความคิดเห็น)
https://news.ycombinator.com/item?id=31675015 (72 ความคิดเห็น)
บทความวิจัยหรือ โค้ด อยู่ที่ไหน?
https://cacm.acm.org/research/almost-linear-time-algorithms-...
ตรงนี้มีส่วนที่ผมสับสนอยู่ คือ o(n) ดูเหมือนเป็นข้ออ้างที่แข็งกว่า O(n)
เพราะอัลกอริทึม o(n) ทุกตัวเป็น O(n) แต่กลับกันไม่จริง อีกอย่าง ถ้า o(n) ใช้ได้กับ n เล็กแค่ไหนก็ได้ และ O(n) ใช้ได้เฉพาะเมื่อ n -> inf แล้วอัลกอริทึมนี้ก็ควรใช้ได้กับ n เล็ก ๆ ด้วยไม่ใช่หรือ? ถ้าอย่างนั้นมันก็ควรเป็นตรงข้ามกับอัลกอริทึมระดับกาแล็กซีที่พูดถึงข้างบนหรือเปล่า? ผมพลาดอะไรไปหรือเปล่า?
นิยามของ f(n) = o(g(n)) โดยคร่าว ๆ คือ lim (n -> infinity) f(n)/g(n) = 0 กล่าวอีกอย่างคือ สำหรับ n ที่ใหญ่พอ g จะโตเร็วกว่า f
เช่น ฟังก์ชัน f(n) = 10n if n < 1000 else 1e1000 เป็น o(n) เพราะเมื่อ n โตขึ้น 1e1000/n จะเข้าใกล้ 0 นี่เป็นการเขียนแบบ pseudo-Python ของฟังก์ชันแบ่งช่วงที่เพิ่มแบบเอ็กซ์โพเนนเชียลเป็น 101000 จนถึง n = 1000 แล้วหลังจากนั้นคงที่
ถ้าจำไม่ผิด 3↑↑64 คือจำนวนของ Graham
ให้ตายสิ ค่าคงที่ตัวคูณ พวกนี้ ทำเอาอยากชูกำปั้นเขย่าใส่ฟ้าเลย
ในบทคัดย่อบอกแค่ว่าเวลาเป็น m^(1+o(1))
มีใครรู้ไหมว่ามีขอบเขตบนที่เป็นรูปธรรมกว่านี้อยู่ที่ไหนหรือเปล่า?
https://de.m.wikipedia.org/wiki/Landau-Symbole
พูดอีกแบบคือเป็น โครงแบบอัลกอริทึม ที่สำหรับ ɛ>1 ใด ๆ จะได้อัลกอริทึมที่รันในเวลา O(m^ɛ)
little o คือฟังก์ชันที่เข้าใกล้ 0 เมื่อ n มุ่งสู่อนันต์ และเรียกว่า ละเลยได้ในเชิงเส้นกำกับ