حل مساله بار 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 داریم.
با توجه به چیزی که به دنبال دارد، غشاء می‌توان + یا – علامتگذاری کرد (و آن را به عنوان «تغییر الکتریکی» می‌نامند) یا با صفر (که آن را «تغییر خنثی» می‌نامند). در این مثال به ترتیب آن را به صورت می‌نویسند. غشاءهایی که فضای محدودی ندارند، دقیقاً بوسیله غشاءها معرفی می‌شون (فضای یا جایگاه یک غشاء بوسیله غشاء و همه غشاءهایی که بلافاصله درون آن قرار دارند، de limited میشود [البته اگر غشایی وجود داشته باشد]).
در این مقاله اشیاء را قرار می‌دهیم که توسط سمبل‌های یک الفبا نشان داده شده است. چندین کپی از اشیاء یکسان در این فضا قرار دارد. بنابراین با چندین مجموعه اشیاء سروکار داریم. مجموعه‌ای که در بالای حدف V قرار دارد، توسط رشته‌ای در بالای V نشان داده شده‌اند: تعداد رخدادهای یک سمبل در رشته‌ای (V مجموعه‌ای از همه رشته‌ها بر V میباشد، رشته خالی به وسیله I معرفی میشود) به صورت [X]a میباشد و فراوانی شیء a را در مجموعه‌ای که به صورت x میباشد، نشان می‌دهد.
یک سیستم P با غشاءهای فعال و دوقسمتی ساختاری به صورت زیر دارد:
در اینجا:
1) m≥1 (اولین درجه سیستم)؛
2) O حرف مربوط به اشیاء میباشد؛
3) H مجموعه محدودی از اعداد برای غشاءها میباشد؛
4) M ساختار غشاء میباشد، شامل m غشاء بوده و با حرف H علامتگذاری میشود.
5) w1…wm مجموعه‌ای را رشته‌ای از o میباشد و مجموعه‌ای از اشیاء را معرفی می‌کند که در جایگاه‌های m از قرار دارد.
6) R مجموعه محدودی از قوانین توسعه یافته میباشد که شامل شکل‌های زیر میباشد:
(قوانین تکامل یافته مربوط به غشاءها و وابسته به اعداد و بار الکتریکی غشاءها میباشد، اما مستقیماً شامل غشاءها نمی‌باشد، به این معنی که غشاءها نه در کابرد این قوانین شرکت می‌کند و نه می‌توان آنها را توسط آنها تغییر داد):
(قوانین برقراری ارتباط: یک شیء در غشاء تعریف میشود، احتمالاً در طول این فرآیند اصلاح میشود، همچنین قطبیت‌یابی غشاء متغیر میشود، اما نه شماره‌گذاری آن):
(قوانین ارتباط، یک شیء از غشاء خارج میشود، احتمالاً در طول این فرآیند تغییر می‌کند، همچنین قطبیت‌یابی این غشاء تغییر می‌کند، اما نه شماره‌گذاری آن):
(قانون انحلال، در واکنش با یک شیء یک غشاء انحلال می‌یابد، در حالی که شیء که جزء این قانون میشود، ممکن است تغییر یابد):
(قانون تقسیمات برای غشاهای ابتدایی، در واکنش با یک شیء غشاء به دو غشاء و با یک عدد تقسیم میشود، احتمالاً با قطبیت مختلف شیء که به یک قانون مربوط میشود با دو غشاء جدید و احتمالاً شیء جدید جایگزین میشود):
اگر غشاء با عدد ho نسبت به غشاءهایی با اعداد h1, … ,hm که در بالا مشخص شد، غشاهای دیگری را دربر گیرد. بنابراین برای کاربردی کردن این قانون باید تغییرات خنثی داشته باشند. این غشاءها کپی می‌شوند و سپس بخشی از محتوای هر دو کپی جدید غشاء ho می‌باشند.
(تقسیم‌بندی غشاءهایی که ابتدایی نیستند، تنها در صورتی انجام میشود که یک غشاء شامل 2 غشاء زیرین با قطبیت مخالف + و – باشد، این دو غشاء در دو غشاء جدید جدا می‌شوند، اما قطبیت‌یابی آنها تغییر می‌کند. همیشه همه غشاءها با قطبیت مخالف با بکار بردن این قانون جدا می‌شوند).
برای بیان توضیحات دقیق در مورد استفاده از این قوانین، باید به [5.6] اشاره کنیم. در اینجا می‌گوییمکه قوانین در حالت همسویی غیرقطعی مرسوم در محاسبه غشاء به شکل وارونه استفاده می‌شوند. در هر مرحله، ابتدا از قوانین نوع a استفاده می‌کنیم. از قوانین دیگری که شامل یک غشاء میشود، باید استفاده کرد که در یک مرحله غشاء می‌تواند موضوع تنها یک نوع قانون از قانون‌های (f)-(b) باشد. به این ترتیب از شکلگیری سیستم به شکلگیری بعدی تغییراتی خواهیم داشت. توالی تغییرات قابل محاسبه است، در صورتی که قوانین دیگر در آخرین شکلگیری بکار نرود، محاسبه متوقف میشود.
برای پی بردن به این مفهوم، یک مساله در زمان چندجمله‌ای توسط سیستم‌های P حل می‌شوند، ضروری است تا مقیاس پیچیده‌ای را برای سیستم‌های P همانطور که در [11] گفته شد، یادآوری کنیم.
به مساله تقسیم‌گیری A و دلالت آن بر A(n) مثالی از A باندازه n توجه کنید. طبقه‌بندی x از سیستم‌های غشاء و تابع کلی f: NN داده شده است (به عنوان مثال تابع‌های چندجمله‌ای و خطی). به نظر ما مساله A به MCx(f) تعلق دارد، در صورتی که گروهی از سیستم‌های غشایی از نوع x وجود دارد، به گونه‌ای که:
1. گروهی یک شکل میباشد، ماشین تورینگ دیده میشود که را در زمان چندجمله‌ای با شروع از n می‌سازد.
2. همریز میباشد.شیء شناخته شده yes دیده میشود، به گونه‌ای که یا در همه محاسبات شی yes از سیستم خارج میشود یا در هیچ محاسبه‌ای صورت نمی‌گیرد.
3. صدا میباشد، یعنی شی yes را خارج می‌کند، اگر جواب به ، «yes» باشد.
4. کارایی f میباشد، یعنی همیشه در مرحله f(n) مکث می‌کند.
درجه‌بندی پیچیدگی چندجمله‌ای مربوط به گروه سیستم‌های غشایی x به صورت زیر میباشد:
PMCx=U MCx(f)
در [6] توضیح این درجه‌بندی پیچیدگی بر اساس ساختار نیمه‌یکسان سیستم‌های P میباشد که مساله A را حل می‌کند: از n شروع نمی‌کنیم، بلکه از مثال A(n) شروع می‌کنیم. برای توضیح دقیقتر تفاوت بین سیستم P یک شکل و سیستم P نیمه یکسان لطفاً به [9] توجه کنید. برای چیزی که در زیر صورت گرفته، از سیستم‌های P تشخیص دهنده استفاده می‌کنیم. در ابتدا [9.11] را مطالعه کنید، سپس به سیستم P با ورودی را ملاحظه کنید. چنین ابزاری چندتایی ( ) میباشد، در اینجا:
سیستم P با حروف شیء و چندمجموعه اولیه میباشد (در ارتباط با غشاءهای عددگذاری شده به ترتیب با 1, … , m میباشد).
∑: حروف (ورودی) شامل بوده و در نتیجه w1, … ,w2 چند مجموعه می‌باشند.
Io: عدد غشاء شناخته شده (ورودی) میباشد.
در صورتی که w مجموعه‌ای از ∑ باشد، پس شکلگیری اولیه ( ) با ورودی w (μ, w'1, … ,w'm) میباشد و در اینجا w'i=wi، چون w'i.=wi.Uw, i≠io میباشد.
محاسیه سیستم P با ورودی را به روش طبیعی توضیح دادیم. توجه داشته باشید که شکلگیری اولیه را می‌توان با اضافه کردن چند مجموعه ورودی w بر ∑ به شکلگیری اولیه سیستم π بدست آورد:
اکنون سیستم P تشخیص دهنده، یک سیستم P به همراه ورودی (π, ∑, io) میباشد، به گونه‌ای که:
1. الفبا یا اعداد گذاری اشیاء شامل 2 بخش مجزای no, yes میباشد.
2. همه محاسبات سیستم متوقف میشود.
3. اگر C محاسبه π باشد، پس هدف yes یا هدف no (نه هر دو تا) از محیط خارج میشود (تنها در آخرین مرحله محاسبه).
به نظر ما c یک محاسبه قابل قبول میباشد، اگر هدف yes در محیط شکل مکث ظاهر شود.
3. حل مساله بار 1-0 چند بعدی توسط سیستم P تشخیص دهند، به همراه غشاهای فعال:
3-1 شکل مساله:
مساله بار 1-0 چندبعدی (MKP) مساله ترکیبی NP کامل شناخته شده میباشد. تصمیم‌گیری شکلگیری MKP به صورت زیر می‌گیرد:
عدد صحیح k داده میشود، تابع هدف نیز داده میشود و تابع روبرو شکل می‌گیرد ، چون و چون j=1, … ,n در اینجا bi, cj, wi,j عدد صحیح غیرمنفی هستند.
تصمیم می‌گیرند که آیا assignment متغیرهای xj به گونه‌ای وجود دارد که محدودیت‌ها را پر کند و تابع هدف بزرگتر از ----- یا برابر k شود.
MKP هم از نقطه‌نظر تئوری و هم عملی، مساله خوش‌بینانه ترکیبی مهم بحساب می‌آید که می‌تواند مسائل عملی زیادی را مثل بودجه‌بندی اصلی شکل دهد. در اینجا پروژه j، سود Cj و مصرف (wij) بخش‌هایی از منبع I را دارد. هدف اصلی تعیین زیرمجموعه پروژه‌های n میباشد، به گونه‌ای که سود کلی افزایش یابد و همه محدودیت‌های منبع از بین برود. کاربردهای مهم دیگر شامل بارگیری بار [12] مساله cutting stock و توزیع پردازشگر در سیستم‌های توزیع شده [3] میباشد.
نمونه خاص از MKP با m=1 مساله بار کلاسیک (kp) میباشد. Kp جزء NP-hard نیست، چون برای آن الگوریتم‌های تقریبی چندجمله‌ای وجود دارد. در واقع این موضوع موردی برای MKP کلی به حساب نمی‌آید. در چهارچوب محاسبه سلولی، الگوریتم غشایی برای حل kp در [7] گفته شده است. در بخش بعدی این فصل الگوریتم غشایی برای MKP کلی را مطرح می‌کنیم.
3-2 الگوریتم غشایی برای مساله بار 1-0 چندبعدی:
از طریق الگوریتم نیروی قوی در چارچوب سیستم‌های P تشخیص دهنده با غشاهای فعال 2 قسمتی، راه حل MKP را نشان می‌دهیم. با توجه به نمونه u از MKP که در بخش بالا گفته شد (براسی سهولت کار) را iمین نابرابری الزامی می‌دانیم و را نابرابری (m+1) می‌نامیم. به biyrction چند جمله‌ای ( ) بین (l≥2) N*, N*1 توجه کنید که به صورت زیر است:
(y1, y2)= (y1+y2)(y1+y2+1)/2+y1, (y1,y2,y3)[(y1, y2), y3] and (y1,…, yl-1, yl)=[(y1,…, yl-1), yl],
در اینجا N* بر مجموعه‌ای از اعداد صحیح غیرمنفی دلالت دارد. اندازه تابع h(u)=(n,k,,b1, … ,bm) و تابع ورودی 2 را توضیح می‌دهیم. در اینجا اولین زیرنویس i از xi, j, J بر iمین نابرابری دلالت دارد. دومین و سومین زیرنویس j از lxi, j, J متغیر xj مطابقت دارد.
برای هر (n, k, b1, … ,bm) به سیستم p تشخیص دهنده توجه می‌کنیم. در اینجا:
به صورت زیر تعریف میشود.
محتوای اولیه هر غشاء به صورت زیر است:
مجموعه قوانین یعنی R ارائه شده است (در مورد استفاده از این قوانین در طول محاسبات توضیحاتی می‌دهیم):
3-2-1 مرحله تولید یا ساخت
هر کدام از n مرحله اول، هر غشاء با شماره 2 کپی میشود تا همه assignmentهای احتمالی برای متغیرهای x1, x2, … ,xn فراهم شود.
قوانین در گروه G2 برای تکمیل فرآیندی میباشد که به غشاءها با شماره 2 اجازه می‌دهد تا assignment متغیر xj را ترکیب کند، به طریقی که اگر متغیر xj مقدار 1 را به خود اختصاص می‌دهند در غشاهای همانند با عدد با عدد 2 و بار الکتریکی مثبت، اشیاء (1≤i≤m)xi,j,0) برای شی‌های ri,j شکل می‌گیرد و شماهای xm+1,j,0 برای اشیاء sm+1,j شکل می‌گیرد، در غیر اینصورت اشیاء xm+1,j,0, xi,j,0 در غشاهای همانند با عدد 2 و بار الکتریکی خنثی ناپدید میشود.
قوانین در گروه (G2) تنها زمانی که سومین زیرنویس xi,j,j به صفر برسند، استفاده می‌شوند. قوانین (G3) مسوول کاهش سومین زیرنویس xi,j,j میباشد، به این طریق برای بدست آوردن همه assignmentهای احتمالی مسیری دایره‌وار ایجاد می‌کنند.
بعد از مرحله n+1، غشاهای 2n با عدد 2 ایجاد شده‌اند، هر کدام از آنها
فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد
تعداد صفحات این مقاله 24 صفحه
پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید
دانلود مقاله حل مساله بار 1-0 چند بعدی توسط سیستم‌های P