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

بسته‌بندی مجموعه یک مسئله ان‌پی کامل کلاسیک در نظریه پیچیدگی محاسباتی و ترکیب شناسیست و یکی از ۲۱ مسئله ان‌پی-کامل کارپ می‌باشد. فرض کنید ما یک مجموعه محدود S و یک لیست از زیرمجموعه‌های S داریم. سپس، مسئله بسته‌بندی مجموعه‌ها، به دنبال زیرمجموعه k می‌گردد، که در لیست دو به دو گسسته‌اند. (منظور این است، عناصرِ دو زیر مجموعه، جدا از هم هستند). مسئله آشکارا NP است، چراکه، زیرمجموعه K داده شده، ما می‌توانیم به راحتی بررسی کنیم که آیا آن‌ها دوبه دو گسسته‌اند!؟ نسخه بهینه شده این مسئله، "مسئله بسته‌بندی بیشینه مجموعه" (Maximum Set Packing Problem)، در لیست به دنبال بزرگترین عددی که دوبه دو گسسته‌اند می‌گردد! این یک مسئله بیشینه سازی است که طبعاً می‌تواند به صورت فرمول (Integer Linear Program) نیز در بیاید، متعلق به دسته (کلاس) مسائل دسته بندی است و حالت دوتاییِ آن (Dual Linear Program) مسئله مجموعه پوشاننده می‌باشد.

مثال

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

ابتکار و مسائلِ دیگر

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

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

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

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

پیچیدگی

مسئله بسته‌بندی مجموعه‌ها تنها یک ان‌پی کامل نیست! بلکه نسخه بهینه آن، مسئله عمومی بسته‌بندی بیشینه مجموعه‌ها ثابت شده‌است که تقریباً به سختیِ مسئله بیشینه گروهک (Clique problem) می‌باشد؛ نمی‌توان آن را با یک عاملِ ثابت تقریب زد. بهترین الگوریتم شناخته شده، آن را با فاکتور $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