ชุดบรรจุภัณฑ์

Q: การกำหนดรูปแบบโปรแกรมเชิงเส้นจำนวนเต็ม

ปัญหาการบรรจุเซตสูงสุดสามารถกำหนดได้เป็น โปรแกรมเชิงเส้นจำนวนเต็ม ดังต่อไป นี้

Q: ชุดบรรจุภัณฑ์ที่มีขนาดจำกัด

ปัญหาดังกล่าวมีรูปแบบที่จัดการได้ง่ายกว่า โดยกำหนดให้ k เป็นจำนวนเต็มบวกใดๆ ≥ 3 ปัญหาการบรรจุเซต k เป็นรูปแบบหนึ่งของการบรรจุเซต ซึ่งแต่ละเซตจะมีสมาชิกไม่เกิน k ตัว

ปัญหา การจัดเรียงเซต (Set packing problem)เป็น ปัญหา NP-complete คลาสสิก ในทฤษฎีความซับซ้อนของการคำนวณและ คณิตศาสตร์เชิง การจัดเรียงและเป็นหนึ่งใน21 ปัญหา NP-complete ของ Karpสมมติว่าเรามีเซตจำกัดSและรายการของเซตย่อยของSปัญหาการจัดเรียงเซตจะถามว่า เซตย่อย kเซตในรายการนั้นไม่มี สมาชิก ร่วมกัน เป็นคู่ๆ หรือไม่ (กล่าวคือ ไม่มีเซตย่อยสองเซตใดที่มีสมาชิกร่วมกัน)

กล่าวอย่างเป็นทางการมากขึ้น เมื่อกำหนดเอกภพและตระกูลของเซตย่อยของ เอกภพนั้น การจัดเรียง เซต(packing)คือตระกูลย่อยของเซตที่เซตทั้งหมดในตระกูลนั้นไม่มีส่วนร่วมกันเป็นคู่ๆ ขนาดของการจัดเรียงเซตคือ ใน ปัญหาการตัดสินใจจัดเรียงเซต (set packing decision problem ) ข้อมูลที่ป้อนเข้าคือคู่และจำนวนเต็มคำถามคือมีการจัดเรียงเซตที่มีขนาดหรือมากกว่าหรือไม่ ในปัญหาการหาค่าเหมาะสมที่สุดของการจัดเรียงเซต (set packing optimization problem ) ข้อมูลที่ป้อนเข้าคือคู่และงานคือการหาการจัดเรียงเซตที่ใช้เซตมากที่สุด ${\คณิตศาสตร์ {U}}$ ${\mathcal {S}}$ ${\คณิตศาสตร์ {U}}$ ${\mathcal {C}}\subseteq {\mathcal {S}}$ ${\mathcal {C}}$ $|{\mathcal {C}}|$ $({\mathcal {U}},{\mathcal {S}})$ $t$ $t$ $({\mathcal {U}},{\mathcal {S}})$

ปัญหานี้จัดอยู่ในกลุ่ม NP อย่างชัดเจน เนื่องจากเมื่อกำหนดเซตย่อยแล้ว เราสามารถตรวจสอบได้อย่างง่ายดายว่าเซตย่อยเหล่านั้นไม่ทับซ้อนกันเป็นคู่ๆ ในเวลาพหุนาม $t$

ปัญหาการจัดเรียงเซตสูงสุด ( Maximum Set Packing ) เป็นรูปแบบการหาค่าที่เหมาะสมที่สุด โดยถามถึงจำนวนเซตที่ไม่ซ้ำกันเป็นคู่ๆ มากที่สุดในรายการ เป็นปัญหาการหาค่าสูงสุดที่สามารถกำหนดได้อย่างเป็นธรรมชาติในรูปของโปรแกรมเชิงเส้นจำนวนเต็มซึ่งจัดอยู่ในกลุ่มของปัญหาการจัดเรียงเซต (Packing Problem )

การกำหนดรูปแบบโปรแกรมเชิงเส้นจำนวนเต็ม

ปัญหาการบรรจุเซตสูงสุดสามารถกำหนดได้เป็นโปรแกรมเชิงเส้นจำนวนเต็ม ดังต่อไป นี้

เพิ่มสูงสุด	$\sum _{S\in {\mathcal {S}}}x_{S}$		(เพิ่มจำนวนเซตย่อยทั้งหมดให้มากที่สุด)
ขึ้นอยู่กับ	$\sum _{S\colon e\in S}x_{S}\leqslant 1$	สำหรับทุกคน $e\in {\mathcal {U}}$	(เซตที่เลือกต้องไม่ทับซ้อนกันเป็นคู่ๆ)
	$x_{S}\in \{0,1\}$	สำหรับทุกคน $S\in {\mathcal {S}}$	(สินค้าแต่ละชุดจะมีบรรจุภัณฑ์หรือไม่ก็ได้)

ความซับซ้อน

ปัญหาการบรรจุเซตไม่เพียงแต่เป็นปัญหา NP-complete เท่านั้น แต่เวอร์ชันการหาค่าเหมาะสมที่สุด (ปัญหาการบรรจุเซตสูงสุดทั่วไป) ยังได้รับการพิสูจน์แล้วว่ายากต่อการประมาณค่าเช่นเดียวกับปัญหาคลิกสูงสุดโดยเฉพาะอย่างยิ่ง ไม่สามารถประมาณค่าได้ภายในปัจจัยคงที่ใดๆ^{[ 1 ]} อัลกอริทึมที่เป็นที่รู้จักดีที่สุดสามารถประมาณค่า ได้ภายในปัจจัย^[²^]ตัวแปรแบบถ่วงน้ำหนักก็สามารถประมาณค่าได้เช่นกัน^[³^] $O({\sqrt {|{\mathcal {U}}|}})$

ชุดบรรจุภัณฑ์ที่มีขนาดจำกัด

ปัญหาดังกล่าวมีรูปแบบที่จัดการได้ง่ายกว่า โดยกำหนดให้k เป็นจำนวนเต็มบวกใดๆ ≥ 3 ปัญหาการบรรจุเซตkเป็นรูปแบบหนึ่งของการบรรจุเซต ซึ่งแต่ละเซตจะมีสมาชิกไม่เกินkตัว

เมื่อk = 1 ปัญหาจะง่ายมาก เมื่อk = 2 ปัญหาจะเทียบเท่ากับการหาการจับคู่ที่มีจำนวนสมาชิกมากที่สุดซึ่งสามารถแก้ไขได้ในเวลาพหุนาม

สำหรับค่า k ≥ 3 ใดๆ ปัญหานี้เป็นปัญหา NP-hard เนื่องจากมีความซับซ้อนกว่าการจับคู่แบบ 3 มิติอย่างไรก็ตาม มีอัลกอริธึมประมาณค่าด้วยปัจจัยคงที่อยู่ :

Cygan ^{[ 4 ]}นำเสนออัลกอริทึมที่สำหรับ ε>0 ใดๆ จะได้ค่าประมาณ ( k +1+ε)/3 เวลาในการทำงานเป็นพหุนามตามจำนวนเซตและองค์ประกอบ แต่เป็นแบบเลขชี้กำลังสองเท่าตาม 1/ε
Furer และ Yu ^{[ 5 ]}นำเสนออัลกอริทึมที่บรรลุการประมาณค่าเดียวกัน แต่มีเวลาทำงานแบบเอกซ์โปเนนเชียลเดี่ยวใน 1/ε

การบรรจุเซตที่มีระดับจำกัด

ในอีกรูปแบบหนึ่งที่จัดการได้ง่ายกว่า หากไม่มีองค์ประกอบใดปรากฏในเซตย่อยมากกว่าdเซต คำตอบสามารถประมาณได้ภายในตัวคูณdซึ่งก็เป็นจริงสำหรับเวอร์ชันที่มีการถ่วงน้ำหนักเช่นกัน

ปัญหาที่เกี่ยวข้อง

ปัญหาที่เทียบเท่ากัน

การจับคู่ไฮเปอร์กราฟเทียบเท่ากับการจัดเรียงเซต: เซตต่างๆ สอดคล้องกับไฮเปอร์เอดจ์

ปัญหาเซตอิสระ เทียบเท่ากับ ปัญหาการจัดเรียงเซตเช่นกัน กล่าวคือ มีการลดรูปหนึ่งต่อหนึ่งที่ใช้เวลาเชิงพหุนามระหว่างกัน:

กำหนดให้มีปัญหาการจัดเรียงเซตบนชุดข้อมูลหนึ่งสร้างกราฟที่แต่ละเซตมีจุดยอดและมีเส้นเชื่อมระหว่างและก็ต่อเมื่อทุกเซตอิสระของจุดยอดในกราฟที่สร้างขึ้นจะสอดคล้องกับการจัดเรียงเซตใน ${\mathcal {S}}$ $S\in {\mathcal {S}}$ $v_{S}$ $v_{S}$ $v_{T}$ $S\cap T\neq \varnothing$ ${\mathcal {S}}$
กำหนดให้ปัญหาเซตจุดยอดอิสระบนกราฟสร้างชุดเซตที่แต่ละจุดยอดจะมีเซตที่ประกอบด้วยขอบทั้งหมดที่อยู่ติดกับ จุดยอดนั้น เซตทุกเซตในชุดเซตที่สร้างขึ้นจะสอดคล้องกับเซตจุดยอดอิสระในชุดเซตนั้น $G(V,E)$ $v$ $S_{v}$ $v$ $G(V,E)$

นี่เป็นการลดรูป PTAS แบบสองทิศทางเช่นกัน และแสดงให้เห็นว่าปัญหาทั้งสองนั้นยากต่อการประมาณค่าเท่ากัน

ในกรณีพิเศษเมื่อแต่ละเซตมีองค์ประกอบ ไม่เกิน k ตัว ( ปัญหาการบรรจุเซต k ) กราฟจุดตัดจะเป็นกราฟที่ไม่มีกรงเล็บ ( k +1) เนื่องจากถ้าเซตหนึ่งตัดกับ เซต k +1 เซต อย่างน้อยสองเซตในจำนวนนี้จะตัดกัน ดังนั้นจึงไม่มีกรงเล็บ ( k +1) ดังนั้นเซตอิสระสูงสุดในกราฟที่ไม่มีกรงเล็บ^[⁶^] จึง สามารถมองได้ว่าเป็นการวางนัยทั่วไปของการบรรจุเซต k สูงสุด

กรณีพิเศษ

การจับคู่กราฟเป็นกรณีพิเศษของการจัดเรียงเซต โดยที่ขนาดของเซตทั้งหมดคือ 2 (เซตเหล่านี้สอดคล้องกับขอบ) ในกรณีพิเศษนี้ สามารถค้นหาการจับคู่ที่มีขนาดสูงสุดได้ในเวลาพหุนาม

การจับคู่แบบ 3 มิติเป็นกรณีพิเศษที่ขนาดของเซตทั้งหมดเท่ากับ 3 และนอกจากนี้ องค์ประกอบยังถูกแบ่งออกเป็น 3 สี โดยแต่ละเซตจะมีองค์ประกอบสีละหนึ่งตัวเท่านั้น กรณีพิเศษนี้ยังคงเป็นปัญหา NP-hard แม้ว่าจะมีอัลกอริธึมประมาณค่าด้วยปัจจัยคงที่ที่ดีกว่ากรณีทั่วไปก็ตาม

ปัญหาอื่นๆ ที่เกี่ยวข้อง

ในปัญหาการครอบคลุมเซตเราจะได้รับตระกูลของเซตย่อยของเอกภพและเป้าหมายคือการพิจารณาว่าเราสามารถเลือกเซตt เซตที่รวมกันแล้วครอบคลุมทุกองค์ประกอบของ เอกภพได้หรือไม่ เซตเหล่านี้อาจซ้อนทับกันได้ เวอร์ชันการหาค่าเหมาะสมที่สุดจะหาจำนวนเซตที่น้อยที่สุดดังกล่าว การบรรจุเซตสูงสุดไม่จำเป็นต้องครอบคลุมทุกองค์ประกอบที่เป็นไปได้ ${\mathcal {S}}$ ${\คณิตศาสตร์ {U}}$ ${\คณิตศาสตร์ {U}}$

ใน ปัญหา การครอบคลุมที่แน่นอน (exact cover problem) ทุกองค์ประกอบของ เซต S จะต้องอยู่ในเซตย่อยเพียงหนึ่งเดียวเท่านั้น การหาการครอบคลุมที่แน่นอนดังกล่าวเป็นปัญหา NP-completeแม้ในกรณีพิเศษที่ขนาดของเซตทั้งหมดเท่ากับ 3 (กรณีพิเศษนี้เรียกว่าการครอบคลุมที่แน่นอน 3หรือX3C ) อย่างไรก็ตาม หากเราสร้างเซตที่มีสมาชิกเพียงตัวเดียวสำหรับแต่ละองค์ประกอบของSและเพิ่มเซตเหล่านี้ลงในรายการ ปัญหาที่ได้จะง่ายพอๆ กับปัญหาการบรรจุเซต (set packing problem) ${\คณิตศาสตร์ {U}}$

เดิมที Karp แสดงให้เห็นว่าปัญหาการจัดเรียงเซตเป็นปัญหา NP-complete ผ่านการลดรูปจากปัญหา คลิก

หมายเหตุ

^ Hazan, Elad; Safra, Shmuel; Schwartz, Oded (2006), "เกี่ยวกับความซับซ้อนของการประมาณค่า การบรรจุเซต k ", ความซับซ้อนในการคำนวณ , 15 (1): 20– 39, CiteSeerX 10.1.1.352.5754 , doi : 10.1007/s00037-006-0205-6 , MR 2226068 , S2CID 1858087ดูโดยเฉพาะหน้า 21: "คลิกสูงสุด (และด้วยเหตุนี้รวมถึงเซตอิสระสูงสุดและการจัดเรียงเซตสูงสุด) ไม่สามารถประมาณได้ภายในขอบเขตเว้นแต่ NP ⊂ ZPP" $O(n^{1-\เอปไซลอน })$
^ Halldórsson, Magnus M.; Kratochvíl, Jan; Telle, Jan Arne (1998). เซตอิสระที่มีข้อจำกัดการครอบงำ การประชุมวิชาการนานาชาติครั้งที่ 25 ว่าด้วยออโตมาตา ภาษา และการ เขียนโปรแกรม บันทึกการบรรยายในวิทยาการคอมพิวเตอร์ เล่มที่ 1443 Springer-Verlag หน้า 176–185
^ Halldórsson, Magnus M. (1999). การประมาณค่าของปัญหาเซตอิสระถ่วงน้ำหนักและเซตย่อยสืบทอด การประชุมวิชาการนานาชาติประจำปีครั้งที่ 5 ด้านการคำนวณและ คณิตศาสตร์เชิงผสม Lecture Notes in Computer Science เล่มที่ 1627 Springer-Verlag หน้า 261–270
^ Cygan, Marek (ตุลาคม 2013). "การประมาณค่าที่ดีขึ้นสำหรับการจับคู่สามมิติผ่านการค้นหาเฉพาะที่ที่มีความกว้างเส้นทางจำกัด" 2013 IEEE 54th Annual Symposium on Foundations of Computer Scienceหน้า 509–518 . arXiv : 1304.1424 . doi : 10.1109/FOCS.2013.61 . ISBN 978-0-7695-5135-7. S2CID 14160646 .
^ Fürer, Martin; Yu, Huiwen (2014). "การประมาณ ปัญหาการบรรจุเซต $k$ ด้วยการปรับปรุงเฉพาะที่"ใน Fouilhoux, Pierre; Gouveia, Luis Eduardo Neves; Mahjoub, A. Ridha; Paschos, Vangelis T. (บรรณาธิการ). การเพิ่มประสิทธิภาพเชิงการจัดเรียง . บันทึกการบรรยายในวิทยาศาสตร์คอมพิวเตอร์. เล่มที่ 8596. Cham: Springer International Publishing. หน้า 408–420 . doi : 10.1007/978-3-319-09174-7_35 . ISBN 978-3-319-09174-7S2CID 15815885
↑นอยโวห์เนอร์, ไมเกะ (2021) "อัลกอริธึมการประมาณที่ได้รับการปรับปรุงสำหรับปัญหาชุดที่เป็นอิสระจากน้ำหนักสูงสุดใน กราฟที่ไม่มีกรงเล็บ $d$ " ในเบลเซอร์ มาร์คุส; มอนเมจ, เบนจามิน (บรรณาธิการ). การประชุมวิชาการระดับนานาชาติครั้งที่ 38 ว่าด้วยแง่มุมทางทฤษฎีของวิทยาการคอมพิวเตอร์, STACS 2021, 16–19 มีนาคม 2564, ซาร์บรึคเคิน, เยอรมนี (การประชุมเสมือนจริง ) ลิปส์ ฉบับที่ 187. ชลอส ดากสตูห์ล – ไลบ์นิซ-เซนทรัม สำหรับข้อมูลสารสนเทศ หน้า 53:1–53:20. arXiv : 2106.03545 . ดอย : 10.4230/LIPICS.STACS.2021.53 .

ลิงก์ภายนอก

[1] : โปรแกรม Pascal สำหรับแก้ปัญหา จากDiscrete Optimization Algorithms with Pascal Programsโดย MacIej M. Syslo, ISBN 0-13-215509-5.
เกณฑ์มาตรฐานพร้อมวิธีแก้ปัญหาที่ดีที่สุดที่ซ่อนอยู่สำหรับการคลุมฉาก การจัดฉาก และการตัดสินผู้ชนะ เก็บถาวรเมื่อ 25 กรกฎาคม 2017 ที่Wayback Machine
การแก้ปัญหาการจัดแพ็กเกจใน PHP
การเพิ่มประสิทธิภาพการจัดเรียงกล่องสามมิติ

[1] Hazan, Elad; Safra, Shmuel; Schwartz, Oded (2006), "เกี่ยวกับความซับซ้อนของการประมาณค่า การบรรจุเซต k ", ความซับซ้อนในการคำนวณ , 15 (1): 20– 39, CiteSeerX 10.1.1.352.5754 , doi : 10.1007/s00037-006-0205-6 , MR 2226068 , S2CID 1858087ดูโดยเฉพาะหน้า 21: "คลิกสูงสุด (และด้วยเหตุนี้รวมถึงเซตอิสระสูงสุดและการจัดเรียงเซตสูงสุด) ไม่สามารถประมาณได้ภายในขอบเขตเว้นแต่ NP ⊂ ZPP" $O(n^{1-\เอปไซลอน })$

[2] Halldórsson, Magnus M.; Kratochvíl, Jan; Telle, Jan Arne (1998). เซตอิสระที่มีข้อจำกัดการครอบงำ การประชุมวิชาการนานาชาติครั้งที่ 25 ว่าด้วยออโตมาตา ภาษา และการ เขียนโปรแกรม บันทึกการบรรยายในวิทยาการคอมพิวเตอร์ เล่มที่ 1443 Springer-Verlag หน้า 176–185

[3] Halldórsson, Magnus M. (1999). การประมาณค่าของปัญหาเซตอิสระถ่วงน้ำหนักและเซตย่อยสืบทอด การประชุมวิชาการนานาชาติประจำปีครั้งที่ 5 ด้านการคำนวณและ คณิตศาสตร์เชิงผสม Lecture Notes in Computer Science เล่มที่ 1627 Springer-Verlag หน้า 261–270

[4] Cygan, Marek (ตุลาคม 2013). "การประมาณค่าที่ดีขึ้นสำหรับการจับคู่สามมิติผ่านการค้นหาเฉพาะที่ที่มีความกว้างเส้นทางจำกัด" 2013 IEEE 54th Annual Symposium on Foundations of Computer Scienceหน้า 509–518 . arXiv : 1304.1424 . doi : 10.1109/FOCS.2013.61 . ISBN 978-0-7695-5135-7. S2CID 14160646 .

[5] Fürer, Martin; Yu, Huiwen (2014). "การประมาณ ปัญหาการบรรจุเซต $k$ ด้วยการปรับปรุงเฉพาะที่"ใน Fouilhoux, Pierre; Gouveia, Luis Eduardo Neves; Mahjoub, A. Ridha; Paschos, Vangelis T. (บรรณาธิการ). การเพิ่มประสิทธิภาพเชิงการจัดเรียง . บันทึกการบรรยายในวิทยาศาสตร์คอมพิวเตอร์. เล่มที่ 8596. Cham: Springer International Publishing. หน้า 408–420 . doi : 10.1007/978-3-319-09174-7_35 . ISBN 978-3-319-09174-7S2CID 15815885

[6] นอยโวห์เนอร์, ไมเกะ (2021) "อัลกอริธึมการประมาณที่ได้รับการปรับปรุงสำหรับปัญหาชุดที่เป็นอิสระจากน้ำหนักสูงสุดใน กราฟที่ไม่มีกรงเล็บ $d$ " ในเบลเซอร์ มาร์คุส; มอนเมจ, เบนจามิน (บรรณาธิการ). การประชุมวิชาการระดับนานาชาติครั้งที่ 38 ว่าด้วยแง่มุมทางทฤษฎีของวิทยาการคอมพิวเตอร์, STACS 2021, 16–19 มีนาคม 2564, ซาร์บรึคเคิน, เยอรมนี (การประชุมเสมือนจริง ) ลิปส์ ฉบับที่ 187. ชลอส ดากสตูห์ล – ไลบ์นิซ-เซนทรัม สำหรับข้อมูลสารสนเทศ หน้า 53:1–53:20. arXiv : 2106.03545 . ดอย : 10.4230/LIPICS.STACS.2021.53 .

[ 1 ]

[

[

[ 4 ]

[ 5 ]

[