موضوع مقاله: بسته‌بندی مجموعه | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # بسته‌بندی مجموعه | مقدمه: بسته‌بندی مجموعه یک مسئله ان‌پی کامل کلاسیک در نظریه پیچیدگی محاسباتی و ترکیب شناسیست و یکی از ۲۱ مسئله ان‌پی-کامل کارپ می‌باشد. | ## بخش 1: بسته‌بندی مجموعه | سپس، مسئله بسته‌بندی مجموعه‌ها، به دنبال زیرمجموعه k می‌گردد، که در لیست دو به دو گسسته‌اند. مسئله آشکارا NP است، چراکه، زیرمجموعه K داده شده، ما می‌توانیم به راحتی بررسی کنیم که آیا آن‌ها دوبه دو گسسته‌اند!؟ مثال برای یک مثال ساده، فرض کنید شما در یک همایشِ سفیرانِ خارجی هستید، عده‌ای به انگلیسی وبقیه به زبان‌های گوناگون دیگر سخن می‌گویند. شما می‌خواهید به گروهی از آن‌ها یک اعلان بدهید، اما به این علت که شما به آن‌ها اعتماد ندارید، نمی‌خواهید که آن‌ها قادر به صحبت کردن بینِ خودشان باشند مگر اینکه شما هم بفهمید چه می‌گویند! برای اینکار، شما یک گروهی را انتخاب می‌کنید که هیچ دو سفیری قادر به مکالمه به یک زبان نباشند غیر از انگلیسی! در این مورد، عناصر مجموعه "زبان ها" می‌باشند و زیرمجموعه‌ها مجموعه‌ای از زبان‌های هر سفیر خاص می‌باشد. اگر دو مجموعه گسسته (دو زبانِ مختلف) باشند، آن دو سفیر قادر به مکالمه مگر به انگلیسی نمی‌باشند. اگرچه حلِ این مسئله به صورت عمومی مشکل می‌باشد، در این مثال ابتکارِ خوب این است که ابتدا سفرایی را انتخاب کنیم که به زبان‌های غیرمعمول سخن می‌گویند، بنابراین بسیاری از بقیه زبان‌ها رد نمی‌شوند! | ## بخش 2: بسته‌بندی مجموعه | در اینجا نیز، مجموعه S و لیستی از مجموعه‌ها داده می‌شود، اما هدف در اینجا تعیین این است که آیا می‌توانیم k مجموعه را انتخاب کنیم به‌طوری‌که مجموعاً شامل تمامی عناصرِ S شوند. نسخه بهینه شده آن، کمترین تعداد مجموعه‌ها را می‌یابد که مجموعاً شامل تمامی عناصرِ لیست می‌باشند. یکی از مزایای مسئله بسته‌بندی مجموعه‌ها این است که، حتی با وجود سخت بودن یافتن بعضی از kها، پیدا کردن یک k برای یک ورودی خاص سخت نیست! برای مثال، ما می‌توانیم از الگوریتم حریصانه استفاده کنیم که دنبال مجموعه‌ای بگردد که کوچکترین میزان تقاطع نسبت به بقیه، در آن وجود دارد (گسسته باشد). ما به‌طور پیوسته اینکار را ادامه می‌دهیم تا دیگر مجموعه‌ای باقی نماند، و ما یک بسته‌بندی مجموعه‌ها داریم از بعضی اندازه‌ها اگرچه ممکن است بیشینه بسته‌بندی نباشد. هرچند هیچ الگوریتمی نمی‌تواند همیشه نتیجه را نزدیک به بیشینه تولید کند (رجوع به بخش بعدی)، در بسیاری از ورودی‌ها، این ابتکار، اینکار را می‌کند. مسئله ان‌پی کامل پوشش، از سویی دیگر، به دنبالِ زیرمجموعه‌ای می‌گردد که تمامیِ عناصر در آن قرار داشته باشند. هرچند، اگر ما یک مجموعه یکتا برای هر عنصرِ S بسازیم و به لیست اضافه کنیم، پی آمد مسئله، آسانیِ بسته‌بندی مجموعه‌ها خواهد بود. | ## بخش 3: بسته‌بندی مجموعه | یک نسخه وزنی (بر اساس وزن) از مسئله مجموعه پوشش وجود دارد که هر یک از زیرمجموعه‌ها وزنِ خاصی به آن داده می‌شود و این وزن است که می‌خواهیم بیشینه اش را به دست آوریم. در مثالِ بالاییِ ما، ما ممکن است وزنِ سفیرها را بر اساس معروفیتِ کشورشان تعیین کنیم، پس اعلانِ ما به بیشترین تعداد مردمِ ممکن می‌رسد! ممکنه این، مسئله را سخت تر نشان بدهد، اما همانطور که در ادامه توضیح می‌دهیم، اکثر نتایج شناخته شده برای مسائل عمومی، برای مسائل وزنی نیز به کار برده می‌شوند. بلکه نسخه بهینه آن، مسئله عمومی بسته‌بندی بیشینه مجموعه‌ها ثابت شده‌است که تقریباً به سختیِ مسئله بیشینه گروهک (Clique problem) می‌باشد؛ نمی‌توان آن را با یک عاملِ ثابت تقریب زد. هرچند، مسئله دارای متغیری است که مقداری مطیع تر دارد: اگر ما فرض کنیم تعداد عناصرِ هیچ یک زیرمجموعه‌ها از k≥۳ تجاوز نمی‌کند، پاسخ می‌تواند با فاکتور k/۲ + ε به ازای تمامیِ ε> ۰، تقریب زده شود. در موارد خاص، مسئله با مجموعه‌های ۳ عنصری، می‌تواند با احتمال ۵۰٪ تقریب زده شود. | ## جمع‌بندی | در موردِ دیگرِ متغیرهای مطیع، اگر هیچ عنصری بزرگتر از k از زیرمجموعه‌ها اتفاق نیفتد پاسخ می‌تواند با فاکتور k تقریب زده شود.