2-SAT¶
2-SAT که مخفف 2-Satisfiability است یک مسئله منطقیست.
نکته ای که وجود دارد این است که به شما یک عبارت با متغیر های منطقی داده شده و شما باید جوری متغیر ها را صفر و یک دهید که شرط برقرار شه و یا بگویید که نمی توان شراطی را برقرار کرد. این عبارت چیزی شبیه به \(({a_1} ∨ {b_1}) ∧ ({a_2} ∨ {b_2}) ∧ ··· ∧ ({a_m} ∨ {b_m})\) است که در آن \(a_i\) و \(b_i\) یکی از متغیر های \(({x_1}, {x_2},..., {x_n})\) و یا نقیض آن ها یعنی \(({¬x_1}, {¬x_2},..., {¬x_n})\) است.
الگوریتم¶
در ابتدا به ازای هر متغیر و نقیض آن یک راس در گراف می گذاریم (در مجموع 2n راس) و به ازای هر عبارت \(u ∨ w\) یک یال جهت دار از نقیض u به w و یک یال جهت دار از نقیض w به u می گذاریم.
اگر دو راس u و نقیض u در یک مولفه قویاً همبندی باشند به این معنی است که نمی توان شرایط این عبارت را برقرار کرد چرا که اگر u یک باشد آنگاه نقیض آن هم یک است و اگر u صفر باشد نقیض آن هم صفر است.
با توجه به این مفهوم می توانیم با الگوریتم کوسارا جو بفهمیم که آیا در یک مولفه قویاً همبندی یک راس با نقیضش آمده یا نه.
اگر نکته بالا برقرار بود یعنی می توانیم جوری متغیر ها را یک و صفر دهیم که شرایط عبارت سوال برقرار شود بنابراین در گام بعدی می خواهیم متغیر ها را یک و صفر دهیم.
راس های گراف را مرتب سازی توپولوژیک می کنیم. اگر u بعد از نقیضش بیاد مقدارش رو یک و اگر u قبل از نقیضش بیاد به آن صفر می دهیم.
این الگوریتم دارای اردر \(O(n + m)\) است.
کاربرد ها¶
از کاربرد های 2-SAT می توان به تشخیص دو بخش بودن گراف کرد. به این نحو که به ازای هر راس یک متغیر در نظر می گیریم. و اگر دو راس مانند u و v به هم یال داشتند دو شرط \((a_v ∨ ¬a_u) ∧ (¬a_v ∨ a_u)\) را به عبارت 2-SAT اضافه می کنیم. واضح است که می توانیم با این شرط ها گراف های دو بخشی را تشخیص دهیم. به این صورت که یک بخش گراف را صفر و بخش دیگر را یک در نظر بگیریم شرط 2-SAT برقرار است بنابراین اگر به جواب برسیم یعنی گراف دو بخشی است.
3-SAT¶
مسئله سخت تری نسبت به 2-SAT، که بجای دو متغیر در هر پرانتز سه متغیر وجود دارد. این مسئله NP است و بنابراین الگوریتم مناسبی برای آن موجود نیست. گفتی است که می توان تمام K-SAT ها را به 3-SAT تبدیل کرد که در آن k از سه بزرگ تر است.
این کتاب توسط مشارکت کنندگان شاززز به وجود آمده است.
این کتاب عمومی است و تحت پروانه cc-by-sa در دسترس است.
آخرین به روز رسانی در ژوئن 09, 2022.
