นักวิจัยหักล้างความเชื่อที่แพร่หลายเกี่ยวกับอัลกอริทึมออนไลน์ นิตยสารควอนต้า

ในชีวิตบางครั้งเราต้องตัดสินใจโดยไม่ได้รับข้อมูลทั้งหมดที่เราต้องการ นั่นเป็นเรื่องจริงในวิทยาการคอมพิวเตอร์ด้วย นี่คือขอบเขตของอัลกอริธึมออนไลน์ ซึ่งถึงแม้จะมีชื่อ แต่ก็ไม่จำเป็นต้องเกี่ยวข้องกับอินเทอร์เน็ตเสมอไป แต่กลับเป็นกลยุทธ์ในการแก้ปัญหาที่ตอบสนองต่อข้อมูลเมื่อมาถึง โดยที่ไม่รู้ว่าอะไรจะเกิดขึ้นต่อไป ความสามารถในการรับมือกับความไม่แน่นอนทำให้อัลกอริธึมเหล่านี้มีประโยชน์สำหรับปริศนาในโลกแห่งความเป็นจริง เช่น การจัดการหน่วยความจำบนแล็ปท็อป หรือการเลือกโฆษณาที่จะแสดงต่อผู้ที่ท่องเว็บ

นักวิจัยศึกษาปัญหาเหล่านี้ในรูปแบบทั่วไปเพื่อตรวจสอบวิธีการใหม่ในการแก้ไขปัญหาเหล่านั้น ที่มีชื่อเสียงที่สุดคือ “k-ปัญหาเซิร์ฟเวอร์” ซึ่งอธิบายถึงงานที่ยุ่งยากในการจัดส่งตัวแทนจำนวนมากเพื่อตอบสนองคำขอที่เข้ามาทีละคน พวกเขาอาจเป็นช่างซ่อมหรือนักดับเพลิง หรือแม้แต่พนักงานขายไอศกรีมเร่ร่อน

“มันง่ายมากที่จะกำหนดปัญหานี้” กล่าว มาร์ซิน บีนคอฟสกี้นักวิจัยอัลกอริทึมจากมหาวิทยาลัย Wrocław ในโปแลนด์ แต่กลับ “กลายเป็นเรื่องยากอย่างประหลาด” เนื่องจากนักวิจัยเริ่มโจมตี k- ปัญหาเกี่ยวกับเซิร์ฟเวอร์ในช่วงปลายทศวรรษ 1980 พวกเขาสงสัยว่าอัลกอริธึมออนไลน์สามารถจัดการงานนี้ได้ดีเพียงใด

ในช่วงหลายทศวรรษที่ผ่านมา นักวิจัยเริ่มเชื่อว่ามีระดับประสิทธิภาพของอัลกอริทึมที่คุณสามารถทำได้เสมอ k-ปัญหาเซิร์ฟเวอร์ ดังนั้นไม่ว่าคุณจะจัดการกับปัญหาเวอร์ชันใด ก็จะมีอัลกอริธึมที่บรรลุเป้าหมายนี้ แต่ในบทความที่ตีพิมพ์ครั้งแรกทางออนไลน์เมื่อเดือนพฤศจิกายนปีที่แล้ว มีนักวิทยาศาสตร์คอมพิวเตอร์สามคน แสดงให้เห็นว่า ว่าสิ่งนี้ไม่สามารถทำได้เสมอไป ในบางกรณี ทุกอัลกอริธึมมีข้อผิดพลาด

“ฉันดีใจที่บอกว่ามันเป็นเรื่องเซอร์ไพรส์ครั้งใหญ่สำหรับฉัน” กล่าว อนุปัม คุปตะซึ่งศึกษาอัลกอริทึมที่มหาวิทยาลัย Carnegie Mellon และไม่เกี่ยวข้องกับบทความนี้ งานนี้นำเสนอ "ข้อมูลเชิงลึกเกี่ยวกับปัญหาสำคัญในพื้นที่นี้"

นักวิทยาศาสตร์คอมพิวเตอร์ก่อน กล่าวถึงปัญหานี้ ในปี 1988 เพื่อทำความเข้าใจ ลองจินตนาการถึงบริษัทที่จ้างช่างประปา เมื่อมีสายเข้า บริษัทจำเป็นต้องตัดสินใจว่าช่างประปาคนไหนจะไปที่สถานที่ใด เป้าหมายของบริษัท — และเป้าหมายของอัลกอริทึมสำหรับ k-ปัญหาเซิร์ฟเวอร์ — คือการลดระยะทางทั้งหมดที่ช่างประปาทุกคนเดินทาง

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

แต่นักวิจัยต้องการเข้าใกล้ให้มากที่สุด โดยจะวัดประสิทธิภาพของอัลกอริทึมออนไลน์โดยการเปรียบเทียบระยะทางในการเดินทางในแต่ละกลยุทธ์ โดยคำนวณสิ่งที่เรียกว่าอัตราส่วนการแข่งขัน นักออกแบบอัลกอริทึมพยายามสร้างกลยุทธ์ออนไลน์ที่เข้าใกล้อุดมคติแบบออฟไลน์ โดยลดอัตราส่วนนี้ลงเหลือ 1

ลองจินตนาการว่าบริษัทประปาของเรามีช่างประปาเพียงสองคน และให้บริการเฉพาะถนนสายยาวเส้นเดียวเท่านั้น โทรเข้ามาทีละครั้ง แนวทางแรกที่สมเหตุสมผลซึ่งเรียกว่าอัลกอริธึมโลภคือส่งช่างประปาคนใดก็ตามที่อยู่ใกล้ตำแหน่งของสายเรียกเข้ามากที่สุด แต่นี่เป็นสถานการณ์ที่อัลกอริธึมนี้ประสบปัญหา ลองนึกภาพช่างประปาคนหนึ่งเริ่มต้นที่ปลายถนนด้านตะวันตก และอีกคนหนึ่งที่ปลายด้านตะวันออก และเสียงเรียกทั้งหมดมาจากบ้านสองหลังที่อยู่ใกล้เคียงทางทิศตะวันตก ในกรณีนี้ ช่างประปาคนหนึ่งไม่เคยขยับเลย ในขณะที่อีกคนหนึ่งทำงานเป็นระยะทางไกลหลายกิโลเมตรที่บ้านทั้งสองหลัง เมื่อมองย้อนกลับไป กลยุทธ์ที่ดีที่สุดคือการย้ายช่างประปาทั้งสองไปยังพื้นที่ที่มีปัญหา แต่น่าเสียดาย คุณคงไม่รู้เลยว่าสิ่งนั้นจะอยู่ที่ไหน

อย่างไรก็ตาม Bieńkowski กล่าวว่า เป็นไปได้ที่จะทำได้ดีกว่าอัลกอริธึมโลภ “ความคุ้มครองสองเท่า” อัลกอริธึมจะย้ายช่างประปาทั้งสองคนในอัตราเดียวกันไปยังสายที่อยู่ระหว่างกัน จนกระทั่งหนึ่งในนั้นถึงสายนั้น วิธีการนี้ทำให้ได้อัตราส่วนการแข่งขันที่ต่ำกว่าอัลกอริธึมโลภ

แม้ว่าปัญหาเชิงนามธรรมนี้ไม่เกี่ยวข้องกับบริษัทประปาจริงๆ k-ปัญหาเซิร์ฟเวอร์นั้นเป็นคำถามสำคัญจริงๆ” ในการใช้คอมพิวเตอร์ออนไลน์กล่าว ยูวัล ราบานีนักวิทยาศาสตร์คอมพิวเตอร์จากมหาวิทยาลัยฮิบรูแห่งเยรูซาเลมซึ่งเป็นผู้ร่วมเขียนรายงานล่าสุด ส่วนหนึ่งเป็นเพราะเครื่องมือและเทคนิคที่พัฒนาขึ้นระหว่างการทำงานเกี่ยวกับ k-ปัญหาเซิร์ฟเวอร์มักจะพบแอปพลิเคชันอื่นในการศึกษาอัลกอริธึมออนไลน์ หรือแม้แต่ภายนอกก็ตาม

“นี่เป็นส่วนหนึ่งของความมหัศจรรย์ของการทำงานกับอัลกอริธึม” เขากล่าว

เมื่อพวกเขาศึกษาปัญหาเหล่านี้ นักวิทยาศาสตร์มักจะมองว่ามันเป็นเกมที่ต่อสู้กับศัตรู ฝ่ายตรงข้ามเลือกลำดับคำขอที่ชั่วร้ายเพื่อทำให้อัลกอริทึมออนไลน์ทำงานได้แย่ที่สุดเท่าที่จะเป็นไปได้เมื่อเปรียบเทียบกับคู่ออฟไลน์ เพื่อปล้นพลังบางส่วนของศัตรู นักวิจัยใช้อัลกอริธึมที่ประกอบด้วย การตัดสินใจแบบสุ่ม.

กลยุทธ์นี้ค่อนข้างมีประสิทธิภาพ และนักวิจัยตั้งข้อสงสัยตั้งแต่ต้นทศวรรษ 1990 ว่าคุณสามารถค้นหาอัลกอริธึมแบบสุ่มที่บรรลุเป้าหมายประสิทธิภาพที่เฉพาะเจาะจงได้เสมอ นั่นคืออัตราส่วนการแข่งขันตามสัดส่วนของบันทึก kที่นี่มี k คือจำนวนตัวแทน สิ่งนี้เรียกว่าการสุ่ม k-การคาดเดาจากเซิร์ฟเวอร์ และนักวิจัยได้แสดงให้เห็นว่ามันเป็นเรื่องจริงสำหรับบางพื้นที่ หรือการสะสมคะแนนเฉพาะ (เทียบเท่ากับบ้านที่อาจต้องใช้ช่างประปา) แต่ยังไม่ได้รับการพิสูจน์ทุกกรณี

เช่นเดียวกับนักวิจัยส่วนใหญ่ Rabani และผู้ร่วมเขียนของเขา — เซบาสเตียน บูเบค ของ Microsoft Research และ คริสเตียน คอสเตอร์ แห่งมหาวิทยาลัยออกซ์ฟอร์ด - คิดว่าการคาดเดานั้นเป็นเรื่องจริง “ฉันไม่มีเหตุผลที่จะต้องสงสัย” โคสเตอร์กล่าว

แต่นั่นเริ่มเปลี่ยนไปเมื่อพวกเขาแก้ไขปัญหาออนไลน์อื่น มันมีการเชื่อมต่อกับ k-ปัญหาเซิร์ฟเวอร์ และขีดจำกัดล่างของอัตราส่วนการแข่งขันสูงอย่างไม่คาดคิด มันทำให้พวกเขาคิดว่าบางทีอาจเป็นเป้าหมายที่ต่ำที่สุด k สำหรับ k-ปัญหาเซิร์ฟเวอร์มีแง่ดีมากเกินไป

Rabani กล่าวว่า Coester เป็นคนแรกที่แนะนำว่าการสุ่ม k-การคาดเดาของเซิร์ฟเวอร์อาจเป็นเท็จ “ทันทีที่เขาพูด ทุกอย่างก็สมเหตุสมผล”

เพื่อหักล้างการคาดเดา ผู้เขียนเล่นบทฝ่ายตรงข้าม สร้างพายุที่สมบูรณ์แบบที่จะป้องกันไม่ให้อัลกอริทึมออนไลน์ใดๆ มีอัตราส่วนการแข่งขันของบันทึก k. กลยุทธ์ของพวกเขามีสองส่วน: พวกเขาสร้างกลุ่มของช่องว่างที่มีลักษณะคล้ายแฟร็กทัลที่ซับซ้อน และออกแบบการกระจายลำดับคำขอที่อาจเป็นเรื่องยากสำหรับอัลกอริทึมที่เป็นไปได้ ในการเคลื่อนไหวครั้งแรกของอัลกอริธึม โครงสร้างของพื้นที่ทำให้ต้องเลือกระหว่างสองเส้นทางที่เหมือนกัน ซึ่งหนึ่งในนั้นจะต้องมีการเดินทางเพิ่มเติมตามคำขอในที่สุด จากนั้น ผู้เขียนได้ใช้วิธีการที่เรียกว่าการเรียกซ้ำเพื่อสร้างพื้นที่ที่จะคูณจุดตัดสินใจเหล่านี้ บังคับให้อัลกอริธึมกลายเป็นตัวเลือกที่ไม่ดีและผลักดันต้นทุนให้สูงขึ้น

ตัวเลือกเหล่านี้ทำให้ Rabani นึกถึงบทกวีของ Robert Frost”ถนนที่ไม่ถูกยึด,” ซึ่งนักเดินทางพิจารณาถึงเส้นทางที่เป็นไปได้สองทางผ่านป่าสีเหลือง “เราแค่ใช้บทกวีซ้ำ ๆ กัน” เขาพูดติดตลก “แล้วเรื่องก็เลวร้ายจริงๆ”

ผู้เขียนแสดงให้เห็นว่าในพื้นที่ที่พวกเขาสร้างขึ้น อัลกอริธึมแบบสุ่มไม่สามารถบรรลุอัตราส่วนการแข่งขันได้ดีไปกว่า (บันทึก k)²ผลักดันเป้าหมายสากลของไม้ซุง k ไกลเกินเอื้อมตลอดไป พวกเขาปฏิเสธการคาดเดานี้

ซึ่งผลงานชิ้นนี้ได้รับรางวัลก รางวัลกระดาษดีเด่น ที่ การประชุมสัมมนาเรื่องทฤษฎีคอมพิวเตอร์ประจำปี 2023ถือเป็นหลักชัยสำคัญที่ "มั่นคงทางทฤษฎี" Gupta กล่าว ผลลัพธ์ประเภทนี้ช่วยระบุประสิทธิภาพที่เราคาดหวังได้จากอัลกอริทึมของเรา อย่างไรก็ตาม ในทางปฏิบัติ ผู้ออกแบบอัลกอริทึมมักไม่ได้วางแผนเกี่ยวกับสถานการณ์ที่เลวร้ายที่สุด โดยมีศัตรูที่มีอำนาจทุกอย่างและไม่รู้อนาคตโดยสิ้นเชิง เมื่ออัลกอริธึมถูกเปิดเผยต่อปัญหาในโลกแห่งความเป็นจริง มักจะเกินความคาดหมายทางทฤษฎี

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

บางทีการค้นพบในอนาคตเหล่านั้นอาจท้าทายความคาดหวังของนักวิจัยเช่นเดียวกับเรื่องนี้ Rabani กล่าว “นี่เป็นหนึ่งในกรณีที่รู้สึกดีจริงๆ ที่ทำผิด”

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