งานวิจัยอาจเป็นส่วนที่น่าสนใจที่สุดในการฝึกอบรมของเรา แนวคิดคือการลองตัวเองไปในทิศทางที่คุณเลือกในขณะที่ยังอยู่ในมหาวิทยาลัย ตัวอย่างเช่น นักศึกษาจากสาขาวิศวกรรมซอฟต์แวร์และการเรียนรู้ของเครื่องมักจะไปทำวิจัยในบริษัทต่างๆ (ส่วนใหญ่เป็น JetBrains หรือ Yandex แต่ไม่เพียงเท่านั้น)
ในโพสต์นี้ ฉันจะพูดถึงโครงการของฉันในสาขาวิทยาการคอมพิวเตอร์ ส่วนหนึ่งของงานของฉัน ฉันได้ศึกษาและนำแนวทางปฏิบัติมาใช้เพื่อแก้ไขปัญหา NP-hard ที่มีชื่อเสียงที่สุดปัญหาหนึ่ง: ปัญหาการครอบคลุมจุดยอด.
ปัจจุบันแนวทางที่น่าสนใจในการแก้ปัญหา NP-hard กำลังพัฒนาอย่างรวดเร็ว - อัลกอริธึมแบบกำหนดพารามิเตอร์ ฉันจะพยายามทำให้คุณทราบข้อมูลอย่างรวดเร็ว บอกอัลกอริธึมแบบกำหนดพารามิเตอร์ง่ายๆ ให้คุณทราบ และอธิบายวิธีการอันทรงพลังวิธีหนึ่งที่ช่วยฉันได้มาก ฉันนำเสนอผลลัพธ์ของฉันในการแข่งขัน PACE Challenge: จากผลการทดสอบแบบเปิด โซลูชันของฉันได้อันดับที่สาม และจะทราบผลสุดท้ายในวันที่ 1 กรกฎาคม
คำแถลง
ฉันชื่อ Vasily Alferov ตอนนี้ฉันเรียนจบชั้นปีที่สามที่ National Research University Higher School of Economics - เซนต์ปีเตอร์สเบิร์ก ฉันสนใจอัลกอริทึมมาตั้งแต่สมัยเรียน ตอนที่ฉันเรียนที่โรงเรียนมอสโกหมายเลข 179 และประสบความสำเร็จในการเข้าร่วมการแข่งขันโอลิมปิกวิทยาศาสตร์คอมพิวเตอร์
ผู้เชี่ยวชาญจำนวนจำกัดในอัลกอริธึมแบบกำหนดพารามิเตอร์เข้าสู่แถบ...
ตัวอย่างที่นำมาจากหนังสือ
ลองจินตนาการว่าคุณเป็นเจ้าหน้าที่รักษาความปลอดภัยที่บาร์ในเมืองเล็กๆ ทุกวันศุกร์ คนครึ่งเมืองจะมาที่บาร์ของคุณเพื่อผ่อนคลาย ซึ่งสร้างปัญหามากมายให้กับคุณ: คุณต้องโยนลูกค้าที่เกเรออกจากบาร์เพื่อป้องกันการทะเลาะกัน ในที่สุดคุณก็รู้สึกเบื่อหน่ายและตัดสินใจใช้มาตรการป้องกัน
เนื่องจากเมืองของคุณมีขนาดเล็ก คุณจึงรู้ได้อย่างแน่ชัดว่าลูกค้าคู่ไหนมีแนวโน้มที่จะทะเลาะกันหากพวกเขาจบลงที่บาร์ด้วยกัน มีรายการของ. n คนที่จะมาบาร์คืนนี้ คุณตัดสินใจที่จะกันชาวเมืองออกจากบาร์โดยไม่มีใครทะเลาะกัน ขณะเดียวกัน เจ้านายของคุณก็ไม่อยากเสียกำไรและจะไม่มีความสุขถ้าคุณไม่ปล่อยให้มากกว่านั้น k คน
น่าเสียดายที่ปัญหาที่อยู่ตรงหน้าคุณคือปัญหา NP-hard แบบคลาสสิก คุณอาจจะรู้จักเธอในชื่อ หรือเป็นปัญหาการปกคลุมจุดยอด สำหรับปัญหาดังกล่าว ในกรณีทั่วไป ไม่มีอัลกอริธึมที่ทำงานในเวลาที่ยอมรับได้ พูดให้ถูกก็คือ สมมติฐาน ETH (Exponential Time Hypothesis) ที่ไม่ได้รับการพิสูจน์และค่อนข้างแข็งแกร่งบอกว่าปัญหานี้ไม่สามารถแก้ไขได้ทันเวลา นั่นคือคุณไม่สามารถนึกถึงสิ่งใดได้ดีไปกว่าการค้นหาที่สมบูรณ์อย่างเห็นได้ชัด ตัวอย่างเช่น สมมติว่ามีคนกำลังจะมาที่บาร์ของคุณ n = 1000 มนุษย์. จากนั้นการค้นหาที่สมบูรณ์จะเป็น ตัวเลือกที่มีประมาณ - จำนวนบ้า โชคดีที่ฝ่ายบริหารของคุณให้ขีดจำกัดแก่คุณ กิโล = 10ดังนั้นจำนวนชุดค่าผสมที่คุณต้องวนซ้ำจึงน้อยกว่ามาก: จำนวนชุดย่อยขององค์ประกอบสิบรายการคือ . นี่จะดีกว่า แต่ก็ยังไม่ถูกนับในหนึ่งวันแม้จะอยู่ในคลัสเตอร์ที่ทรงพลังก็ตาม
เพื่อขจัดความเป็นไปได้ที่จะเกิดการต่อสู้ในรูปแบบความสัมพันธ์ที่ตึงเครียดระหว่างผู้มาเยี่ยมชมบาร์ คุณต้องกัน Bob, Daniel และ Fedor ออกไป ไม่มีทางแก้ไขที่จะเหลือเพียงสองคนเท่านั้น
นี่หมายความว่าถึงเวลาที่ต้องยอมแพ้และปล่อยให้ทุกคนเข้ามาใช่ไหม? ลองพิจารณาตัวเลือกอื่น ๆ ตัวอย่างเช่นคุณไม่สามารถปล่อยให้เฉพาะผู้ที่มีแนวโน้มที่จะต่อสู้กับคนจำนวนมากเข้ามาได้ ถ้าใครสามารถสู้ได้อย่างน้อยด้วย k+1 บุคคลอื่น ถ้าอย่างนั้นคุณจะปล่อยให้เขาเข้าไปไม่ได้อย่างแน่นอน ไม่อย่างนั้นคุณจะต้องกันทุกคนออกไป k+1 ชาวเมืองที่เขาสามารถต่อสู้ได้ซึ่งจะทำให้ผู้นำไม่พอใจอย่างแน่นอน
ให้คุณโยนทุกคนที่ทำได้ตามหลักการนี้ แล้วคนอื่นๆก็สู้ได้ไม่เกิน k ประชากร. โยนพวกเขาออกไป k เพื่อนคุณไม่สามารถป้องกันอะไรได้มากไปกว่า ข้อขัดแย้ง หมายความว่าถ้ามีมากกว่านั้น หากบุคคลใดมีส่วนร่วมในความขัดแย้งอย่างน้อยหนึ่งครั้ง คุณจะไม่สามารถป้องกันความขัดแย้งทั้งหมดได้อย่างแน่นอน เนื่องจากแน่นอนว่า คุณจะยอมให้คนที่ไม่มีความขัดแย้งเข้ามาได้อย่างแน่นอน คุณจึงต้องผ่านกลุ่มย่อยทั้งหมดที่มีขนาด XNUMX ใน XNUMX คน มีประมาณ และการดำเนินการจำนวนนี้สามารถแยกออกจากคลัสเตอร์ได้แล้ว
หากคุณสามารถนำบุคคลที่ไม่มีความขัดแย้งใดๆ ไปได้อย่างปลอดภัย แล้วผู้ที่มีส่วนร่วมในความขัดแย้งเพียงครั้งเดียวล่ะ? ในความเป็นจริงพวกเขาสามารถปล่อยให้เข้ามาได้โดยการปิดประตูใส่คู่ต่อสู้ อันที่จริงถ้าอลิซขัดแย้งกับบ็อบเท่านั้น ถ้าเราปล่อยอลิซออกจากสองคนนี้ เราจะไม่แพ้: บ็อบอาจมีความขัดแย้งอื่น ๆ แต่อลิซไม่มีความขัดแย้งนั้นอย่างแน่นอน ยิ่งไปกว่านั้น มันไม่สมเหตุสมผลเลยที่เราจะไม่ปล่อยให้เราทั้งคู่เข้าไป หลังจากการดำเนินการดังกล่าวก็ไม่มีอะไรเหลืออีกต่อไป แขกที่ชะตากรรมไม่ได้รับการแก้ไข: เรามีเท่านั้น ความขัดแย้ง แต่ละคนมีผู้เข้าร่วมสองคนและแต่ละคนมีส่วนร่วมในอย่างน้อยสองคน ดังนั้นสิ่งที่เหลืออยู่ก็คือการจัดเรียง ตัวเลือกที่สามารถพิจารณาได้อย่างง่ายดายครึ่งวันบนแล็ปท็อป
ในความเป็นจริง ด้วยการให้เหตุผลง่ายๆ คุณสามารถบรรลุเงื่อนไขที่น่าดึงดูดยิ่งขึ้นได้ โปรดทราบว่าเราจำเป็นต้องแก้ไขข้อพิพาททั้งหมดอย่างแน่นอน นั่นคือจากคู่ที่ขัดแย้งกันแต่ละคู่ เลือกอย่างน้อยหนึ่งคนที่เราจะไม่ปล่อยให้เข้าไป ลองพิจารณาอัลกอริธึมต่อไปนี้: รับข้อขัดแย้งใดๆ โดยเราจะลบผู้เข้าร่วมรายหนึ่งออกและเริ่มจากส่วนที่เหลือแบบวนซ้ำ จากนั้นจึงลบอีกรายการหนึ่งออกและเริ่มแบบวนซ้ำด้วย เนื่องจากเราโยนใครบางคนออกไปในทุกขั้นตอน แผนผังการเรียกซ้ำของอัลกอริทึมดังกล่าวจึงเป็นแผนผังไบนารีที่มีความลึก kดังนั้นโดยรวมแล้วอัลกอริธึมจึงใช้งานได้ ที่ไหน n คือจำนวนจุดยอด และ m - จำนวนซี่โครง ในตัวอย่างของเรา นี่คือประมาณสิบล้าน ซึ่งสามารถคำนวณได้ในเสี้ยววินาที ไม่เพียงแต่บนแล็ปท็อปเท่านั้น แต่ยังรวมถึงโทรศัพท์มือถือด้วย
ตัวอย่างข้างต้นเป็นตัวอย่าง อัลกอริธึมแบบกำหนดพารามิเตอร์. อัลกอริธึมแบบกำหนดพารามิเตอร์คืออัลกอริธึมที่ทำงานตามเวลา f(k) โพลี(n)ที่ไหน p - พหุนาม f เป็นฟังก์ชันคำนวณตามอำเภอใจ และ k - พารามิเตอร์บางตัวซึ่งอาจมีขนาดเล็กกว่าขนาดของปัญหามาก
การให้เหตุผลทั้งหมดก่อนที่อัลกอริทึมนี้จะเป็นตัวอย่าง เคอร์เนล เป็นหนึ่งในเทคนิคทั่วไปสำหรับการสร้างอัลกอริธึมแบบกำหนดพารามิเตอร์ Kernelization คือการลดขนาดปัญหาให้เป็นค่าที่ถูกจำกัดโดยฟังก์ชันของพารามิเตอร์ ปัญหาที่เกิดขึ้นมักเรียกว่าเคอร์เนล ดังนั้น ด้วยการให้เหตุผลง่ายๆ เกี่ยวกับองศาของจุดยอด เราได้เคอร์เนลกำลังสองสำหรับปัญหา Vertex Cover ซึ่งกำหนดพารามิเตอร์ตามขนาดของคำตอบ มีการตั้งค่าอื่นๆ ที่คุณสามารถเลือกได้สำหรับงานนี้ (เช่น Vertex Cover Above LP) แต่นี่คือการตั้งค่าที่เราจะพูดถึง
ก้าวที่ท้าทาย
การแข่งขัน (The parameterized Algorithms and Computational Experiments Challenge) ถือกำเนิดขึ้นในปี 2015 เพื่อสร้างการเชื่อมโยงระหว่างอัลกอริธึมแบบกำหนดพารามิเตอร์และวิธีการที่ใช้ในทางปฏิบัติเพื่อแก้ไขปัญหาทางคอมพิวเตอร์ การแข่งขันสามรายการแรกมีจุดประสงค์เพื่อค้นหาความกว้างของแผนภูมิต้นไม้ () ค้นหาต้นไม้ Steiner () และค้นหาชุดของจุดยอดที่ตัดวงจร (). ในปีนี้ ปัญหาหนึ่งที่คุณสามารถลองแก้ไขได้คือปัญหาการครอบคลุมจุดยอดตามที่อธิบายไว้ข้างต้น
การแข่งขันได้รับความนิยมทุกปี หากคุณเชื่อข้อมูลเบื้องต้น ในปีนี้ มี 24 ทีมเข้าร่วมการแข่งขันเพื่อแก้ปัญหาจุดยอดครอบคลุมเพียงอย่างเดียว เป็นที่น่าสังเกตว่าการแข่งขันใช้เวลาไม่กี่ชั่วโมงหรือหนึ่งสัปดาห์ แต่ใช้เวลาหลายเดือน ทีมมีโอกาสที่จะศึกษาวรรณกรรม เกิดแนวคิดดั้งเดิมของตนเอง และพยายามนำไปปฏิบัติ โดยพื้นฐานแล้วการแข่งขันครั้งนี้เป็นโครงการวิจัย แนวคิดสำหรับการแก้ปัญหาที่มีประสิทธิภาพสูงสุดและการมอบรางวัลของผู้ชนะจะจัดขึ้นร่วมกับการประชุม (International Symposium on parameterized and Exact Computation) ซึ่งเป็นส่วนหนึ่งของการประชุมอัลกอริทึมประจำปีที่ใหญ่ที่สุดในยุโรป . ข้อมูลรายละเอียดเพิ่มเติมเกี่ยวกับการแข่งขันสามารถดูได้ที่ และผลของปีที่แล้วก็โกหก .
รูปแบบการแก้ปัญหา
เพื่อแก้ปัญหาการครอบคลุมจุดยอด ฉันลองใช้อัลกอริธึมแบบกำหนดพารามิเตอร์ โดยทั่วไปจะประกอบด้วยสองส่วน: กฎการทำให้เข้าใจง่าย (ซึ่งเหมาะจะนำไปสู่เคอร์เนล) และกฎการแยก กฎการทำให้เข้าใจง่ายคือการประมวลผลอินพุตล่วงหน้าในเวลาพหุนาม วัตถุประสงค์ของการใช้กฎดังกล่าวคือเพื่อลดปัญหาให้เป็นปัญหาที่เล็กลง กฎการทำให้เข้าใจง่ายเป็นส่วนที่แพงที่สุดของอัลกอริธึม และการใช้ส่วนนี้จะนำไปสู่เวลาทำงานทั้งหมด แทนเวลาพหุนามอย่างง่าย ในกรณีของเรา กฎการแยกจะขึ้นอยู่กับข้อเท็จจริงที่ว่าสำหรับแต่ละจุดยอด คุณต้องใช้จุดนั้นหรือจุดใกล้เคียงเป็นคำตอบ
รูปแบบทั่วไปคือ: เราใช้กฎการทำให้เข้าใจง่าย จากนั้นเราเลือกจุดยอดบางส่วน และทำการเรียกซ้ำสองครั้ง: ครั้งแรกเราจะรับมันเพื่อตอบสนอง และอีกอันเราจะรับเพื่อนบ้านทั้งหมด นี่คือสิ่งที่เราเรียกว่าการแยก (การแตกแขนง) ตามจุดยอดนี้
จะมีการเพิ่มเติมหนึ่งครั้งในโครงการนี้ในย่อหน้าถัดไป
แนวคิดในการแบ่งกฎ (brunching)
เรามาพูดคุยกันถึงวิธีการเลือกจุดยอดที่จะเกิดการแยกกัน
แนวคิดหลักนั้นโลภมากในแง่ของอัลกอริธึม: ลองใช้จุดยอดของระดับสูงสุดแล้วแยกตามนั้น ทำไมมันดูดีขึ้นล่ะ? เพราะในสาขาที่สองของการเรียกซ้ำ เราจะลบจุดยอดจำนวนมากด้วยวิธีนี้ คุณสามารถวางใจได้ว่ายังมีกราฟเล็กๆ น้อยๆ เหลืออยู่ และเราสามารถดำเนินการแก้ไขได้อย่างรวดเร็ว
แนวทางนี้ ซึ่งใช้เทคนิคการเคอร์เนลแบบง่ายๆ ที่ได้กล่าวไปแล้ว แสดงให้เห็นได้ดีและแก้การทดสอบบางอย่างที่มีขนาดหลายพันจุดยอดได้ แต่ ตัวอย่างเช่น กราฟนี้ทำงานได้ไม่ดีกับกราฟลูกบาศก์ (นั่นคือ กราฟที่มีระดับของจุดยอดแต่ละจุดเป็น XNUMX)
มีแนวคิดอื่นที่อิงตามแนวคิดที่ค่อนข้างเรียบง่าย: หากกราฟถูกตัดการเชื่อมต่อ ปัญหาในส่วนประกอบที่เชื่อมต่อจะสามารถแก้ไขได้อย่างเป็นอิสระ โดยรวมคำตอบในตอนท้าย นี่เป็นการปรับเปลี่ยนตามสัญญาเล็กน้อยในโครงการซึ่งจะช่วยเร่งการแก้ปัญหาได้อย่างมาก: ก่อนหน้านี้ ในกรณีนี้ เราทำงานกับผลคูณของเวลาเพื่อคำนวณการตอบสนองของส่วนประกอบ แต่ตอนนี้เราทำงานเพื่อ ผลรวม. และเพื่อเร่งความเร็วในการแตกแขนง คุณต้องเปลี่ยนกราฟที่เชื่อมต่อให้เป็นกราฟที่ไม่เชื่อมต่อ
ทำอย่างไร? หากมีจุดประกบในกราฟ คุณต้องสู้กับจุดนั้น จุดประกบคือจุดยอดซึ่งเมื่อดึงออก กราฟจะสูญเสียการเชื่อมต่อ จุดเชื่อมต่อทั้งหมดในกราฟสามารถพบได้โดยใช้อัลกอริธึมแบบคลาสสิกในเวลาเชิงเส้น วิธีการนี้ช่วยเร่งการแตกแขนงได้อย่างมาก
เมื่อจุดยอดใดๆ ที่เลือกถูกลบออก กราฟจะแบ่งออกเป็นองค์ประกอบที่เชื่อมต่อกัน
เราจะทำเช่นนี้ แต่เราต้องการมากกว่านี้ ตัวอย่างเช่น มองหาการตัดจุดยอดเล็กๆ ในกราฟแล้วแยกไปตามจุดยอดจากนั้น วิธีที่มีประสิทธิภาพที่สุดที่ฉันรู้ในการค้นหาจุดยอดต่ำสุดทั่วโลกคือการใช้ต้นไม้ Gomori-Hu ซึ่งสร้างขึ้นในหน่วยเวลาลูกบาศก์ ในการแข่งขัน PACE Challenge ขนาดกราฟโดยทั่วไปคือหลายพันจุดยอด ในสถานการณ์นี้ จำเป็นต้องดำเนินการหลายพันล้านการดำเนินการที่แต่ละจุดยอดของแผนผังการเรียกซ้ำ ปรากฎว่าเป็นไปไม่ได้เลยที่จะแก้ไขปัญหาภายในเวลาที่กำหนด
เรามาลองเพิ่มประสิทธิภาพโซลูชันกัน การตัดจุดยอดขั้นต่ำระหว่างจุดยอดคู่หนึ่งสามารถพบได้โดยอัลกอริธึมใดๆ ก็ตามที่สร้างการไหลสูงสุด คุณสามารถปล่อยให้มันเข้าสู่เครือข่ายดังกล่าวได้ ในทางปฏิบัติมันทำงานได้เร็วมาก ฉันสงสัยว่าในทางทฤษฎีสามารถพิสูจน์การประมาณเวลาการทำงานได้ ซึ่งค่อนข้างเป็นที่ยอมรับอยู่แล้ว
ฉันพยายามหลายครั้งเพื่อค้นหาการตัดระหว่างจุดยอดแบบสุ่มคู่หนึ่งแล้วเลือกจุดยอดที่สมดุลที่สุด น่าเสียดายที่สิ่งนี้ให้ผลลัพธ์ที่ไม่ดีในการทดสอบ PACE Challenge แบบเปิด ฉันเปรียบเทียบกับอัลกอริธึมที่แยกจุดยอดที่มีระดับสูงสุด โดยเรียกใช้งานโดยมีข้อจำกัดด้านความลึกของการลง หลังจากที่อัลกอริธึมพยายามค้นหาการตัดด้วยวิธีนี้ ก็เหลือกราฟที่ใหญ่ขึ้น นี่เป็นเพราะความจริงที่ว่าการตัดนั้นไม่สมดุลมาก: เมื่อลบจุดยอดออก 5-10 จุดก็เป็นไปได้ที่จะแยกออกเพียง 15-20 จุด
เป็นที่น่าสังเกตว่าบทความเกี่ยวกับอัลกอริธึมที่เร็วที่สุดในทางทฤษฎีใช้เทคนิคขั้นสูงกว่ามากในการเลือกจุดยอดสำหรับการแยก เทคนิคดังกล่าวมีการใช้งานที่ซับซ้อนมากและมักจะมีประสิทธิภาพต่ำในแง่ของเวลาและความทรงจำ ฉันไม่สามารถระบุสิ่งที่ค่อนข้างเป็นที่ยอมรับสำหรับการปฏิบัติได้
วิธีการใช้กฎการทำให้เข้าใจง่าย
เรามีแนวคิดสำหรับเคอร์เนลแล้ว ฉันขอเตือนคุณ:
- หากมีจุดยอดที่แยกออกมา ให้ลบออก
- หากมีจุดยอดระดับ 1 ให้เอาออกแล้วตอบสนองเพื่อนบ้าน
- หากมีจุดยอดองศาเป็นอย่างน้อย k+1, เอามันกลับมา.
สองอันแรกทุกอย่างชัดเจน ส่วนอันที่สามมีเคล็ดลับอย่างหนึ่ง หากในปัญหาการ์ตูนเกี่ยวกับแท่งไม้ เราจะให้ขีดจำกัดบนเป็น kจากนั้นใน PACE Challenge คุณเพียงแค่ต้องหาจุดยอดที่มีขนาดน้อยที่สุด นี่เป็นการเปลี่ยนแปลงโดยทั่วไปของปัญหาการค้นหาเป็นปัญหาในการตัดสินใจ ซึ่งมักจะไม่มีความแตกต่างระหว่างปัญหาทั้งสองประเภท ในทางปฏิบัติ หากเรากำลังเขียนตัวแก้สำหรับปัญหาการครอบคลุมจุดยอด อาจมีความแตกต่างกัน เช่นในข้อที่สาม
จากมุมมองของการดำเนินการ มีสองวิธีในการดำเนินการ แนวทางแรกเรียกว่า Iterative Deepening เป็นดังนี้: เราสามารถเริ่มต้นด้วยข้อจำกัดที่สมเหตุสมผลจากด้านล่างของคำตอบ จากนั้นรันอัลกอริทึมของเราโดยใช้ข้อจำกัดนี้เป็นข้อจำกัดในคำตอบจากด้านบน โดยไม่ทำให้การเรียกซ้ำต่ำกว่าข้อจำกัดนี้ หากเราพบคำตอบแล้ว ก็รับประกันว่าจะเหมาะสมที่สุด ไม่อย่างนั้นเราจะเพิ่มขีดจำกัดนี้ขึ้นหนึ่งแล้วเริ่มใหม่อีกครั้ง
อีกวิธีหนึ่งคือจัดเก็บคำตอบที่เหมาะสมที่สุดในปัจจุบันและมองหาคำตอบที่เล็กลง โดยเปลี่ยนพารามิเตอร์นี้เมื่อพบ k เพื่อการตัดกิ่งก้านที่ไม่จำเป็นออกไปในการค้นหามากขึ้น
หลังจากทำการทดลองทุกคืนหลายครั้ง ฉันตัดสินใจใช้สองวิธีนี้ร่วมกัน ประการแรก ฉันเรียกใช้อัลกอริทึมโดยจำกัดความลึกในการค้นหา (เลือกเพื่อให้ใช้เวลาเพียงเล็กน้อยเมื่อเทียบกับโซลูชันหลัก) และใช้สิ่งที่ดีที่สุด วิธีแก้ปัญหาที่พบเป็นขีดจำกัดบนของคำตอบ - นั่นคือสิ่งเดียวกัน k.
จุดยอดของระดับ 2
เราได้จัดการกับจุดยอดระดับ 0 และ 1 แล้ว ปรากฎว่าสามารถทำได้ด้วยจุดยอดระดับ 2 แต่จะต้องใช้การดำเนินการที่ซับซ้อนมากขึ้นจากกราฟ
เพื่ออธิบายสิ่งนี้ เราต้องกำหนดจุดยอดด้วยวิธีใดวิธีหนึ่ง ลองเรียกจุดยอดของระดับ 2 ว่าจุดยอดกัน vและเพื่อนบ้าน - จุดยอด x и y. ต่อไปเราจะมีสองกรณี
- เมื่อ x и y - เพื่อนบ้าน แล้วคุณก็จะตอบได้ x и yและ v ลบ. อันที่จริง จากสามเหลี่ยมนี้ จะต้องมีจุดยอดอย่างน้อยสองจุดเป็นการตอบแทน และเราจะไม่แพ้อย่างแน่นอนหากเรารับ x и y: พวกเขาอาจมีเพื่อนบ้านคนอื่นและ v พวกเขาไม่ได้อยู่ที่นี่
- เมื่อ x и y - ไม่ใช่เพื่อนบ้าน จากนั้นมีการระบุไว้ว่าจุดยอดทั้งสามสามารถติดกาวเป็นหนึ่งเดียวได้ แนวคิดก็คือในกรณีนี้จะมีคำตอบที่ดีที่สุด ซึ่งเราจะเลือกคำตอบนั้น vหรือจุดยอดทั้งสอง x и y. ยิ่งกว่านั้นในกรณีแรกเราจะต้องตอบสนองเพื่อนบ้านทั้งหมด x и yแต่ในวินาทีนั้นไม่จำเป็น สิ่งนี้สอดคล้องกับกรณีที่เราไม่ได้ใช้จุดยอดที่ติดกาวในการตอบสนองและเมื่อเราทำเช่นนั้น เหลือเพียงข้อสังเกตว่าในทั้งสองกรณีการตอบสนองจากการดำเนินการดังกล่าวลดลงหนึ่งรายการ
เป็นที่น่าสังเกตว่าแนวทางนี้ค่อนข้างยากที่จะนำไปใช้อย่างแม่นยำในเวลาเชิงเส้นที่ยุติธรรม การติดจุดยอดเป็นการดำเนินการที่ซับซ้อน คุณต้องคัดลอกรายการเพื่อนบ้าน หากทำอย่างไม่ระมัดระวัง อาจส่งผลให้เวลาทำงานต่ำกว่าปกติโดยไม่แสดงอาการ (เช่น หากคุณคัดลอกขอบจำนวนมากหลังจากการติดกาวแต่ละครั้ง) ฉันตั้งใจที่จะค้นหาเส้นทางทั้งหมดจากจุดยอดระดับ 2 และวิเคราะห์กรณีพิเศษต่างๆ มากมาย เช่น วงจรจากจุดยอดดังกล่าวหรือจากจุดยอดดังกล่าวทั้งหมด ยกเว้นจุดเดียว
นอกจากนี้ จำเป็นที่การดำเนินการนี้สามารถย้อนกลับได้ เพื่อว่าเมื่อกลับมาจากการเรียกซ้ำ เราจะคืนค่ากราฟให้กลับสู่รูปแบบดั้งเดิม เพื่อให้แน่ใจว่าเป็นเช่นนี้ ฉันไม่ได้ล้างรายการขอบของจุดยอดที่รวมเข้าด้วยกัน ดังนั้นฉันจึงรู้ว่าขอบไหนไปอยู่ที่ไหน การใช้กราฟนี้จำเป็นต้องมีความแม่นยำเช่นกัน แต่ให้เวลาเชิงเส้นที่ยุติธรรม และสำหรับกราฟที่มีขอบหลายหมื่นเส้น มันจะพอดีกับแคชของโปรเซสเซอร์ ซึ่งให้ข้อได้เปรียบที่ยอดเยี่ยมในด้านความเร็ว
เคอร์เนลเชิงเส้น
สุดท้ายคือส่วนที่น่าสนใจที่สุดของเคอร์เนล
ขั้นแรก จำไว้ว่าในกราฟสองฝ่าย สามารถใช้ฝาครอบจุดยอดต่ำสุดได้ . ในการทำเช่นนี้คุณต้องใช้อัลกอริทึม เพื่อหาค่าที่ตรงกันสูงสุดจากนั้นจึงใช้ทฤษฎีบท .
แนวคิดของเคอร์เนลเชิงเส้นคือ: ก่อนอื่นเราแยกกราฟออกเป็นสองส่วนนั่นคือแทนที่จะเป็นจุดยอดแต่ละอัน v มาเพิ่มสองยอดกัน и และแทนที่จะเป็นแต่ละขอบ คุณ-วี เพิ่มซี่โครงสองอัน и . กราฟที่ได้จะเป็นแบบทวิภาคี ให้เราหาจุดยอดขั้นต่ำที่ครอบไว้ จุดยอดบางจุดของกราฟดั้งเดิมจะไปถึงจุดนั้นสองครั้ง บางจุดเพียงครั้งเดียว และบางจุดไม่เคยไปเลย ทฤษฎีบทเนมเฮาเซอร์-ทรอตเตอร์ระบุว่า ในกรณีนี้ เราสามารถลบจุดยอดที่ไม่ได้ชนแม้แต่ครั้งเดียว และนำจุดยอดที่ชนสองครั้งกลับคืนมา นอกจากนี้ เธอยังบอกว่าจุดยอดที่เหลือ (จุดยอดที่กระทบครั้งเดียว) คุณต้องใช้เวลาอย่างน้อยครึ่งหนึ่งเป็นคำตอบ
เราเพิ่งเรียนรู้ที่จะจากไปไม่เกิน 2k ยอดเขา อันที่จริง ถ้าคำตอบที่เหลือคืออย่างน้อยครึ่งหนึ่งของจุดยอดทั้งหมด ก็ไม่มีจุดยอดรวมมากไปกว่า 2k.
ที่นี่ฉันสามารถก้าวไปข้างหน้าเล็กน้อย เห็นได้ชัดว่าเคอร์เนลที่สร้างขึ้นในลักษณะนี้ขึ้นอยู่กับประเภทของจุดยอดที่น้อยที่สุดที่เราถ่ายในกราฟแบบสองฝ่าย ฉันอยากจะเอามาอันหนึ่งเพื่อให้จำนวนจุดยอดที่เหลืออยู่น้อยที่สุด ก่อนหน้านี้พวกเขาสามารถทำเช่นนี้ได้ทันเวลาเท่านั้น . ฉันคิดการนำอัลกอริธึมนี้ไปใช้ในเวลานั้น ดังนั้นแกนนี้สามารถค้นหาได้ในกราฟของจุดยอดนับแสนจุดในแต่ละขั้นตอนการแตกแขนง
ผล
การปฏิบัติแสดงให้เห็นว่าโซลูชันของฉันทำงานได้ดีกับการทดสอบจุดยอดหลายร้อยจุดและขอบหลายพันจุด ในการทดสอบดังกล่าว ค่อนข้างเป็นไปได้ที่จะคาดหวังว่าจะพบวิธีแก้ปัญหาภายในครึ่งชั่วโมง โดยหลักการแล้ว ความน่าจะเป็นในการค้นหาคำตอบในเวลาที่ยอมรับได้จะเพิ่มขึ้นหากกราฟมีจำนวนจุดยอดระดับสูงเพียงพอ เช่น ระดับ 10 และสูงกว่า
ในการเข้าร่วมการแข่งขันจะต้องส่งวิธีแก้ปัญหาไปที่ . พิจารณาจากข้อมูลที่นำเสนอที่นั่น โซลูชันของฉันในการทดสอบแบบเปิดอยู่ในอันดับที่สามจากทั้งหมดยี่สิบ โดยมีช่องว่างอย่างมากจากอันดับที่สอง พูดตามตรง ยังไม่ชัดเจนว่าโซลูชันจะได้รับการประเมินในการแข่งขันอย่างไร ตัวอย่างเช่น โซลูชันของฉันผ่านการทดสอบน้อยกว่าโซลูชันในอันดับที่สี่ แต่โซลูชันที่ผ่านจะทำงานเร็วกว่า
ผลการทดสอบแบบปิดจะทราบในวันที่ XNUMX กรกฎาคม
ที่มา: will.com