بسته‌بندی مجموعه

برای یک مثال ساده، فرض کنید شما در یک همایشِ سفیرانِ خارجی هستید، عده‌ای به انگلیسی وبقیه به زبان‌های گوناگون دیگر سخن می‌گویند. شما می‌خواهید به گروهی از آن‌ها یک اعلان بدهید، اما به این علت که شما به آن‌ها اعتماد ندارید، نمی‌خواهید که آن‌ها قادر به صحبت کردن بینِ خودشان باشند مگر اینکه شما هم بفهمید چه می‌گویند! برای اینکار، شما یک گروهی را انتخاب می‌کنید که هیچ دو سفیری قادر به مکالمه به یک زبان نباشند غیر از انگلیسی! از سویی دیگر همچنین می‌خواهید اعلانتان را به بیشترین تعدادِ ممکنِ سفیرها بدهید. در این مورد، عناصر مجموعه "زبان ها" می‌باشند و زیرمجموعه‌ها مجموعه‌ای از زبان‌های هر سفیر خاص می‌باشد. اگر دو مجموعه گسسته (دو زبانِ مختلف) باشند، آن دو سفیر قادر به مکالمه مگر به انگلیسی نمی‌باشند. در اینجا حداکثر مجموعه دسته بندی Maximum set packing بیشترین تعداد ممکن از سفیرها تحت محدودیتِ مشخص شده را، انتخاب می‌کند. اگرچه حلِ این مسئله به صورت عمومی مشکل می‌باشد، در این مثال ابتکارِ خوب این است که ابتدا سفرایی را انتخاب کنیم که به زبان‌های غیرمعمول سخن می‌گویند، بنابراین بسیاری از بقیه زبان‌ها رد نمی‌شوند!

بسته بندی مجموعه‌ها، یکی از خانواده مسائل مربوط به پوشش مجموعه(Set Covering Problem) یا جزءبندی (Set Partitioning Problem) عناصر مجموعه هاست. یکی از مسائل بسیار نزدیک، مسئله پوشش است. در اینجا نیز، مجموعه S و لیستی از مجموعه‌ها داده می‌شود، اما هدف در اینجا تعیین این است که آیا می‌توانیم k مجموعه را انتخاب کنیم به‌طوری‌که مجموعاً شامل تمامی عناصرِ S شوند. این مجموعه‌ها ممکن است اشتراکاتی هم داشته باشند. نسخه بهینه شده آن، کمترین تعداد مجموعه‌ها را می‌یابد که مجموعاً شامل تمامی عناصرِ لیست می‌باشند. بسته‌بندی بیشینه مجموعه‌ها، نیازی به پوشش دادن تمامی عناصرِ ممکن را ندارد!

یکی از مزایای مسئله بسته‌بندی مجموعه‌ها این است که، حتی با وجود سخت بودن یافتن بعضی از kها، پیدا کردن یک k برای یک ورودی خاص سخت نیست! برای مثال، ما می‌توانیم از الگوریتم حریصانه استفاده کنیم که دنبال مجموعه‌ای بگردد که کوچکترین میزان تقاطع نسبت به بقیه، در آن وجود دارد (گسسته باشد). ما به‌طور پیوسته اینکار را ادامه می‌دهیم تا دیگر مجموعه‌ای باقی نماند، و ما یک بسته‌بندی مجموعه‌ها داریم از بعضی اندازه‌ها اگرچه ممکن است بیشینه بسته‌بندی نباشد. هرچند هیچ الگوریتمی نمی‌تواند همیشه نتیجه را نزدیک به بیشینه تولید کند (رجوع به بخش بعدی)، در بسیاری از ورودی‌ها، این ابتکار، اینکار را می‌کند.

مسئله ان‌پی کامل پوشش، از سویی دیگر، به دنبالِ زیرمجموعه‌ای می‌گردد که تمامیِ عناصر در آن قرار داشته باشند. یافتنِ یک پوشش کامل بدون توجه به اندازه آن، یک مسئله ان‌پی کامل می‌باشد. هرچند، اگر ما یک مجموعه یکتا برای هر عنصرِ S بسازیم و به لیست اضافه کنیم، پی آمد مسئله، آسانیِ بسته‌بندی مجموعه‌ها خواهد بود.

یک نسخه وزنی (بر اساس وزن) از مسئله مجموعه پوشش وجود دارد که هر یک از زیرمجموعه‌ها وزنِ خاصی به آن داده می‌شود و این وزن است که می‌خواهیم بیشینه اش را به دست آوریم. در مثالِ بالاییِ ما، ما ممکن است وزنِ سفیرها را بر اساس معروفیتِ کشورشان تعیین کنیم، پس اعلانِ ما به بیشترین تعداد مردمِ ممکن می‌رسد! ممکنه این، مسئله را سخت تر نشان بدهد، اما همانطور که در ادامه توضیح می‌دهیم، اکثر نتایج شناخته شده برای مسائل عمومی، برای مسائل وزنی نیز به کار برده می‌شوند.

مسئله بسته‌بندی مجموعه‌ها تنها یک ان‌پی کامل نیست! بلکه نسخه بهینه آن، مسئله عمومی بسته‌بندی بیشینه مجموعه‌ها ثابت شده‌است که تقریباً به سختیِ مسئله بیشینه گروهک (Clique problem) می‌باشد؛ نمی‌توان آن را با یک عاملِ ثابت تقریب زد. بهترین الگوریتم شناخته شده، آن را با فاکتور ${\displaystyle O(\sqrt{|S|})}$

هرچند، مسئله دارای متغیری است که مقداری مطیع تر دارد: اگر ما فرض کنیم تعداد عناصرِ هیچ یک زیرمجموعه‌ها از k≥۳ تجاوز نمی‌کند، پاسخ می‌تواند با فاکتور k/۲ + ε به ازای تمامیِ ε> ۰، تقریب زده شود. در موارد خاص، مسئله با مجموعه‌های ۳ عنصری، می‌تواند با احتمال ۵۰٪ تقریب زده شود. در موردِ دیگرِ متغیرهای مطیع، اگر هیچ عنصری بزرگتر از k از زیرمجموعه‌ها اتفاق نیفتد پاسخ می‌تواند با فاکتور k تقریب زده شود. همچنین برای نسخه وزنی نیز درست است.

Independent Set یا مجموعه مستقل که موردِ خاصی از بسته‌بندی مجموعه هاست.

• ترجمه شده از منبعِ انگلیسی Set Packing.
• Steven S. Skiena "Set Packing" "راهنمای طراحی الگوریتم" آخرین ویرایش ۲ ژوئن ۱۹۹۷.
• "Maximum Set Packing" "بیشینه بسته‌بندی مجموعه ها".
• A compendium of NP optimization problems "خلاصه‌ای از مسائل بهینه‌سازی ان پی"، آخرین ویرایش، ۲۰ مارس ۲۰۰۰

• A Pascal program for solving the problem From Discrete Optimization Algorithms with Pascal Programs by MacIej M. Syslo ISBN 0-13-215509-5.
• Benchmarks with Hidden Optimum Solutions for Set Covering، Set Packing and Winner Determination بایگانی‌شده در ۲۵ ژوئیه ۲۰۱۷ توسط Wayback Machine
• Solving packaging problem in PHP