حل مساله بار 1-0 چند بعدی توسط سیستم‌های P به همراه ورودی و غشاء فعال
| دسته بندی | عمران |
| فرمت فایل | doc |
| حجم فایل | 83 کیلو بایت |
| تعداد صفحات فایل | 28 |
حل مساله بار 1-0 چند بعدی توسط سیستم‌های P به همراه ورودی و غشاء فعال:
خلاصه:
سیستم‌های غشایی از نظر زیستی مدل‌های تئوری محاسبه همسو و توزیع شده را فعال می‌کند. در این مقاله الگوریتم غشایی را نشان می‌دهیم تا به کمک آن مساله بار 1-0 چند بعدی را در زمانی خطی توسط سیستم‌های شناسنده P به همراه ورودی غشاهای فعال که از دو قسمت استفاده می‌کند، حل کند. این الگوریتم را می‌توان اصلاح کرد و از آن برای حل مساله برنامه‌نویسی عدد صحیح 1-0 عمومی استفاده کرد.
مقدمه:
سیستم‌های P، طبقه‌ای از ابزار محاسله همسوی توزیع شده یک نوع بیوشیمی هستند که در [4] معرفی شد و می‌توان آن را به عنوان معماری محاسبه کلی دانست که انواع مختلف اشیاء در آن قسمت توسط عملکردهای مختلف پردازش می‌شوند. از این دیدگاه مطرح میشود که پردازش‌های خاصی که در ساختار پیچیده موجودات زنده صورت می‌گیرد، به صورت محاسباتی درنظر گرفته می‌شوند.
از زمانی که Gh, Paun آن را مطرح کرد، دانشمندان کامپیوتر و بیولوژیست‌ها این زمینه را با نقطه نظرهای مختلف خود غنی‌سازی کرده‌اند. برای انگیزه و جزئیات توضیحات مربوط به مدل‌های متفاوت سیستم P لطفاً به [6/4] توجه کنید. تقسیم‌بندی غشایی (الهام شده از تقسیمات سلولی گفته شده در بیولوژی)، تنها راهی است که برای بدست آوردن فضای کاری ---- در زمان خطی بیشتر و بر اساس حل مسائل مشکل (عموماً مسائل تکمیل شده VP) در زمان چند جمله‌ای (اغلب به صورت خطی) بررسی شده است. جزئیات را می‌توان در [4.6.8] ببینید.
اخیراً مسائل کامل PSPACE به این روش مطرح شدند. در گفتگویی غیررسمی، در سیستم‌های P به همراه غشاء فعال می‌توانیم از 6 نوع قانون استفاده کنیم:
1.قوانین بازگشت چندگانه؛
2.قوانین مربوط به حل معرفی اشیاء در غشاءها؛
3.قوانین مربوط به ارسال اشیاء به بیرون از غشاء؛
4.قوانین مربطو به حل غشاء؛
5.قوانین مربوط به تقسیم غشاء اولیه؛
6.قوانین مربوط به تقسیم غشاء ثانویه.
در [10] Perez-Jimenez، مساله قابل راضی کننده‌ای را در زمان خطی با توجه به تعداد متغیرها و شروط فرمول‌گزاره‌ای توسط سیستم تشخیص دهنده P به همراه ورودی و به همراه غشاء فعال 2 قسمتی حل می‌کند. مساله قابل راضی شدن hard NP نیست، چون الگوریتم‌های تقریبی چند جمله‌ای وجود دارد که آن را حل می‌کند و این نمونه‌ای برای مساله بار 1-0 چند جمله‌ای به حساب نمی‌آید. در این مقاله به حل مساله بار 1-0 چند بعدی توسط سیستم P توجه کردیم.
مساله اصلی تکمیل NP می‌باشد و همچنین مساله بار 1-0 چندبعدی به درجه مساله تکمیل NP بستگی دارد. بنابراین این مساله در زمان چندجمله‌ای توسط سیستم‌های P با ورودی و با غشاء فعال که از تقسیم 2 استفاده می‌کند، حل خواهد شد. می‌توانیم این نوع محلول را با کمک کاهش مساله بار 1-0 چندبعدی برای مساله راضی شدن بدست آوریم تا آن سیستم P را که به حل مساله راضی شدن در زمان خطی می‌پردازیم، بکار بریم. همچنان این مساله قابل بحث است که چگونه می‌توان مساله NP را به مساله تکمیل شده NP دیگر بوسیله سیستم P ساده کرد.
در این مقاله مستقیماً الگوریتم غشایی را برای حل مساله بار 1-0 چندبعدی در زمان خطی توسط سیستم تشخیص دهنده P به همراه ورودی به همراه غشاء فعال که از تقسیم 2 استفاده می‌کند، ارائه می‌دهیم.در اینجا به طرحی از یک محدوده سیستم P توجه می‌کنیم که مساله بار 1-0 چندبعدی را حل می‌کند (نه به شکل بررسی رسمی الگورینتم غشایی). همانطور که در بخش 4 گفته شد، استفاده از این الگوریتم اصلاح شده برای حل مساله برنامه‌نویسی عدد صحیح 1-0 کلی، کار آسانی است.
سیستم‌های P در الگوریتم در [5] تقریباً به طور یکسان به شکلی ساخته می‌شوند که برای هر نمونه از مساله قابل راضی شدن، یک سیستم P شکل می‌گیرد. در الگوریتم ما مربوط به مساله 0-1 چندبعدی، سیستم‌های P به طور یکسان شکل می‌گیرند. برای همه نمونه‌هایی که یک اندازه هستند، یک سیستم P طراحی میشود.
الگوریتم مربوط به مساله قابل راضی شدن در [5] از سیستم P با قوانین نوع (a)، (f)-(c) استفاده می‌کند و الگوریتم برای مساله راضی شدن در ]6] از سیستم‌های P با قوانین نوع (c)-(a) و (e) استفاده می‌کند. در اینجا برای حل مساله بار 1-0 چندبعدی از سیستم‌های P محدوتر استفاده می‌کنیم، یعنی سیستم P به همراه قوانین نوع (a)، (c) و (e).
مساله کلاسیک بار مورد خاصی از مساله بار 1-0 چندبعدی با یک بعد می‌باشد. تقریباٌ می‌توان الگوریتم غشایی را برای حل مساله بار کلاسیک [7]درنظر بگیریم. الگوریتم جدید ما نسبت به الگوریتم در [7] مراحل محاسبه کمتری دارد، بویژه در الگوریتم در [7]. 2n+1 مرحله برای مطرح کردن همه assignment متغیرها استفاده میشود، حال آنکه در الگوریتم جدید ما، n+1 مرحله برای تولید کردن همه assignment متغیرها استفاده میشود. در اینجا n تعداد متغیرهاست. در این مفهوم، الگوریتم ما، اصلاح الگوریتم [7] می‌باشد.
این مقاله به صورت زیر طبقه‌بندی شده است:
در بخش 2، مفهوم سیستم P سازمان دهنده معرفی میشود که مدل محاسبه‌ای برای حل مساله بار 1-0 چندبعدی بوده و آن را در محاسبه با غشاءها درجه پیچیدگی چندجمله‌ای می‌نامند.
در بخش 3، برای حل مساله بار 1-0 چندبعدی به کمک سیستم‌های P سازمان دهنده با غشاءهای فعال 2 قسمتی، الگوریتم غشایی ارائه می‌دهد.
در بخش 4، بحث ارائه شده است.
2. سیستم P:
با توجه به [5] با معرفی سیستم P با غشاءهای فعال شروع می‌کنیم که در این قسمت جزئیات بیشتری وجود دارد.
ساختار یک غشاء به صورت نمودار Venn مطرح شد و با کمک رشته‌ای از پرانتزهای انتخابی دقیق (با یک جفت پرانتز خارجی) معرفی میشود. این جفت پرانتزهای خارجی با غشاء خارجی که «موپست» نامیده میشود، تطبیق دارد. هر غشایی بدون داشتن غشایی درونی، غشاء اولیه نامیده میشود. به عنوان مثال، ساختار درون همه غشاءها شماره‌گذاری شده است.در اینجا ما از عدد 1 تا 8 استفاده کرده‌ایم. عدد غشاءها، درجه ساختار غشاء را نشان می‌دهد، در حالی که بلندترین درخت مربوط به روش معمول با ساختار، عمق آن می‌باشد. در نمونه بالا ساختار غشایی با درجه 8 و عمق 4 داریم.