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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

بسته‌بندی مجموعه یک مسئله ان‌پی کامل کلاسیک در نظریه پیچیدگی محاسباتی و ترکیب شناسیست و یکی از ۲۱ مسئله ان‌پی-کامل کارپ می‌باشد. فرض کنید ما یک مجموعه محدود 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 یا مجموعه مستقل که موردِ خاصی از بسته بندی مجموعه هاست.

پانویس[ویرایش]

منابع[ویرایش]

پیوند به بیرون[ویرایش]