دانلود مقاله حل مساله بار 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: NN داده شده است (به عنوان مثال تابع‌هاي چندجمله‌اي و خطي). به نظر ما مساله 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 عدد صحيح غيرمنفي هستند.