payamvha/North_RAG huggingface dataset:
از دترمینان ارائه داد که James Whitbread Lee Glaisher آن را کامل نمود. در سال ۱۹۷۹، ادسخر دیکسترا این مسئله را با استفاده از الگوریتم عقب‌گرد حل کرد. حل مسئله. مسئله هشت وزیر دارای ۹۲ راه حل متمایز است. اگر راه حل هایی که با چرخش و یا بازتاب برهم منطبق می‌شوند به عنوان یک راه حل در نظر گرفته شوند ، پازل دارای ۱۲ راه حل خواهد بود. به این راه حل‌ها، راه حل های پایه گفته می‌شود. هر یک از این راه حل‌ها در زیر نشان داده شده است: صورت مسئله. هدف از مسئله n وزیر، چیدن n مهره وزیر در یک صفحه شطرنج(n*n) است،
وزیر، چیدن n مهره وزیر در یک صفحه شطرنج(n*n) است، به‌طوری‌که هیچ دو وزیری یکدیگر را گارد ندهند، یعنی هیچ دو مهره‌ای نباید در یک سطر، ستون یا قطر یکسان باشند. وزیر در خانه‌های شطرنج به صورت عرضی، طولی و قطری می‌تواند حرکت کند. مسئله n وزیر از جمله مسائل در هوش مصنوعی است که روش‌های جستجوی معمولی قادر به حل آن‌ها نخواهد بود شمردن تعداد جواب‌ها. جدول زیر شمار راه حل‌های متمایز و همهٔ راه حل‌ها را برای جای گرفتن "n" وزیر بر روی صفحه "n" × "n" نشان می‌دهد. شمار پاسخ‌‌های حالت شش وزیر کمتر از پنج وزیر است. فرمول
حالت شش وزیر کمتر از پنج وزیر است. فرمول دقیق و حتی تقریبی درستی برای یافتن تعداد پاسخ‌های این مسئله وجود ندارد. صفحه ۲۷*۲۷ بزرگترین حالت مسئله است که پاسخ‌های آن به طور کامل تا به حال شمرده شده است. روش‌های حل مسئله. الگوریتم عقبگرد. از تکنیک عقبگرد برای حل مسائلی استفاده می‌شود که در آن‌ها دنباله‌ای از اشیاء از یک مجموعه مشخص انتخاب می‌شود، به‌طوری‌که این دنباله، ملاکی را در بر می‌گیرد. عقبگرد حالت اصلاح شدهٔ جستجوی عمقی یک درخت است. این الگوریتم همانند جستجوی عمقی است، با این تفاوت که فرزندان یک گره فقط
عمقی است، با این تفاوت که فرزندان یک گره فقط هنگامی ملاقات می‌شوند که گره امید بخش باشد و در آن گره حلی وجود نداشته باشد. با توجه به اینکه هیچ ۲ وزیری نباید همدیگر را گارد کنند و در یک سطر نمی‌توانند باشند، تعداد کل حالت‌ها برای n=۴ برابر ۴*۴*۴*۴=۲۵۶ است. در شطرنج یک وزیر می‌تواند به مهره‌هایی که در خانه‌های عمود یا مورب به وی قرار دارند حمله کند. یا به عبارت ریاضی، اگر ردیفها و ستونهای شطرنج را از یک تا هشت شماره‌گذاری کنیم و وزیر در خانه (i، j) قرار داشته باشد، مهره‌هایی که در خانه‌های (i، m) یا (m، j)
باشد، مهره‌هایی که در خانه‌های (i، m) یا (m، j) یا (i ± m، j ± m) قرار دارند توسط وزیر تهدید می‌شوند. برای سادگی تشریح این مسئله با استفاده از روش بازگشت به عقب، فرض می‌کنیم که خانه‌های شطرنج ۴x۴ و تعداد وزیرها نیز ۴ باشد. سپس بعد از یافتن راه حل برای این مسئله ساده شده، اقدام به نوشتن الگوریتم برای مسئله اصلی می‌کنیم. مراحل جستجو برای یافتن جواب را به این صورت دنبال می‌کنیم که: وزیر اول را در ردیف اول و ستون اول قرار می‌دهیم. در ردیف دوم از اولین ستون به جلو رفته و به دنبال خانه‌ای می‌گردیم که مورد تهدید
رفته و به دنبال خانه‌ای می‌گردیم که مورد تهدید وزیر اول نباشد و وزیر دوم را در این خانه قرار می‌دهیم. همانند قبل، در ردیف سوم از اولین ستون به جلو رفته و به دنبال خانه‌ای می‌گردیم که مورد تهدید وزیران اول و دوم نباشد. می‌بینیم که چنین خانه‌ای موجود نیست. پس به عقب یعنی ردیف دوم برگشته و وزیر دوم را به خانه‌ای دیگر از ردیف دوم منتقل می‌کنیم که مورد تهدید وزیر اول نباشد. دوباره در ردیف سوم اولین خانه‌ای را میابیم که مورد تهدید دو وزیر قبلی نباشد. این بار خانه را می‌یابیم و وزیر سوم را در آن قرار می‌دهیم.
را می‌یابیم و وزیر سوم را در آن قرار می‌دهیم. همانند قبل، در ردیف چهارم به دنبال اولین خانه‌ای می‌گردیم که مورد تهدید وزیران پیشین نباشد. چنین خانه‌ای موجود نیست. به ردیف قبل یعنی ردیف سوم باز می‌گردیم تا خانه‌ای دیگر برای وزیر سوم بیابیم. خانه دیگری وجود ندارد. به ردیف قبل یعنی ردیف دوم بر می‌گردیم تا خانه دیگری برای وزیر دوم پیدا کنیم. به آخرین ستون رسیده‌ایم و خانه دیگری نیست. به ردیف قبل یعنی ردیف اول بر می‌گردیم و وزیر اول را یک ستون به جلو می‌بریم. در ردیف دوم اولین خانه‌ای را میابیم که مورد تهدید
در ردیف دوم اولین خانه‌ای را میابیم که مورد تهدید وزیر اول نباشد و وزیر دوم را در آن خانه قرار می‌دهیم. در ردیف سوم اولین خانه‌ای را میابیم که مورد تهدید وزیران اول و دوم نباشد و وزیر سوم را در آن خانه می‌گذاریم. در ردیف چهارم اولین خانه‌ای را میابیم که مورد تهدید وزیران پیشین نباشد. این بار خانه را می‌یابیم و وزیر چهارم را در آن خانه قرار می‌دهیم. به یک جواب می‌رسیم. حال اگر فرض کنیم که این خانه جواب نیست و به مسیر خود ادامه دهیم، احتمالاً" می‌توانیم جوابهای دیگری نیز بیابیم. شبه کد پیاده‌سازی الگوریتم
دیگری نیز بیابیم. شبه کد پیاده‌سازی الگوریتم عقبگرد برای مسئله n وزیر. program nqueen(output); void queens (index i) index j; if (promising(i)) if (i == n) cout « col[1] through col[n]; else for (j = 1; j &lt;= n; j++) { col[i + 1] = j; queens(i + 1); bool promising (index i) index k; bool Switch; k = 1; Switch = true ; while (k &lt; i &amp;&amp; switch) { if (col[i] == col[k] || abs(col[i] – col[k] == i - k)) switch = false; k++; return Switch; برنامه زبان C به صورت غیر بازگشتی. int b[8]; inline static
C به صورت غیر بازگشتی. int b[8]; inline static int unsafe(int y) { int i, t, x; x = b[y]; for (i = 1; i &lt;= y; i++) { t = b[y - i]; if ((t == x) || (t == x - i) || (t == x + i)) { return 1; return 0; static void putboard(void) { static int s = ۰; int x, y; printf("\n\nSolution #٪i\n", ++s); for (y = 0; y &lt; 8; y++) { for (x = 0; x &lt; 8; x++) { printf((b[y] == x) ? "|Q": "|_"); printf("|\n"); int main(void) { int y = ۰; b[۰] = -۱; while (y &gt;= ۰) { do { b[y]++; } while ((b[y] &lt; 8) &amp;&amp;
{ do { b[y]++; } while ((b[y] &lt; 8) &amp;&amp; unsafe(y)); if (b[y] &lt; 8) { if (y &lt; 7) { b[++y] = -۱; } else { putboard(); } else { y--; return 0; برنامه زبان ++C به صورت بازگشتی. program nqueen(output); class EightQueens int m_size; int m_solution_count; int m_attempt_count; int m_queen[MAXSIZE]; bool m_row_inuse[MAXSIZE]; bool m_diag_rise[MAXSIZE*2]; bool m_diag_fall[MAXSIZE*2]; public: EightQueens(int size, bool is_alt) { assert(size &lt;= MAXSIZE); m_size = size; m_solution_count = 0;
MAXSIZE); m_size = size; m_solution_count = 0; m_attempt_count = 0; for (int i = 0; i &lt; m_size; i++) { m_queen[i] = i; m_row_inuse[i] = 0; for (int j = 0; j &lt; m_size*2; j++) { m_diag_rise[j] = 0; m_diag_fall[j] = 0; if (is_alt) SearchAlt(0); else Search(0); int GetSolutionCount() { return m_solution_count; int GetAttemptCount() { return m_attempt_count; private: void SearchAlt(int col){ if (col == m_size) { m_solution_count++; return; for (int row = 0; row &lt; m_size; row++) { m_attempt_count++; if
row &lt; m_size; row++) { m_attempt_count++; if (m_row_inuse[row] == 0 &amp;&amp; IsDiagValid(col, row)) { m_queen[col] = row; m_row_inuse[row] = 1; SetDiags(col, 1); SearchAlt(col+1); SetDiags(col, 0); m_row_inuse[row] = 0; m_queen[col] = -1; void Search(int col) { if (col == m_size) { m_solution_count++; return; for (int i = col; i &lt; m_size; i++) { if (SwapQueenIfDiagValid(col, i)) { Search(col+1); UnSwapQueen(col, i); void SwapQueenBasic(int i, int j) { int hold = m_queen[i]; m_queen[i] = m_queen[j];
{ int hold = m_queen[i]; m_queen[i] = m_queen[j]; m_queen[j] = hold; void SetDiags(int col, int val) { assert(m_diag_rise[m_queen[col] + col]!= val); m_diag_rise[m_queen[col] + col] = val; assert(m_diag_fall[m_queen[col] - col + m_size]!= val); m_diag_fall[m_queen[col] - col + m_size] = val; bool IsDiagValid(int col, int row) { return (m_diag_rise[row + col] == 0 &amp;&amp; m_diag_fall[row - col + m_size] == 0); bool SwapQueenIfDiagValid(int i, int j) { m_attempt_count++; if (IsDiagValid(i, m_queen[j])) {
if (IsDiagValid(i, m_queen[j])) { SwapQueenBasic(i, j); SetDiags(i, 1); return true; return false; void UnSwapQueen(int i, int j) { SetDiags(i, 0); SwapQueenBasic(i, j); void do_work(bool is_alt) int size = 8; EightQueens puzzle(size, is_alt); int soln = puzzle.GetSolutionCount(); int attempt = puzzle.GetAttemptCount(); assert(size!= 8 || soln == 92); const char* style = is_alt ? "cartesian": "permutation"; printf("EightQueens[%d] has %d solutions found in %5d attempts using %s search. \n", size, soln,
in %5d attempts using %s search. \n", size, soln, attempt, style); int main() printf("We should have 92 solutions for 8x8. \n"); do_work(0); do_work(1); الگوریتم مونت کارلو. از الگوریتم مونت کارلو برای برآورد کردن کارایی یک الگوریتم عقبگرد استفاده می‌شود. الگوریتم‌های مونت کارلو، احتمالی هستند، یعنی دستور اجرایی بعدی گاه به‌طور تصادفی تعیین می‌شوند. در الگوریتم قطعی چنین چیزی رخ نمی‌دهد. الگوریتم مونت کارلو مقدار مورد انتظار یک متغیر تصادفی را که روی یک فضای ساده تعریف می‌شود، با استفاده از مقدار میانگین
ساده تعریف می‌شود، با استفاده از مقدار میانگین آن روی نمونه تصادفی از فضای ساده بر آورد می‌کند. تضمینی وجود ندارد که این برآورد به مقدار مورد انتظار واقعی نزدیک باشد، ولی احتمال نزدیک شدن آن، با افزایش زمان در دسترس برای الگوریتم، افزایش می‌یابد. شبه کد پیاده‌سازی الگوریتم مونت کارلو برای الگوریتم عقبگرد مسئله n وزیر. program nqueen(output); int ostimate _ n_ queens (int n) index i , j , col [1..n]; int m , mprod , numnodes ; set _of_ index prom _children; i = 0; numnodes =1 ; m = 1; mprod = 1 ; while (m!=
= 0; numnodes =1 ; m = 1; mprod = 1 ; while (m!= 0 &amp;&amp; i!= n) { mprod = mprod * m ; numnodes = numnodes + mprod * n; i ++; m = 0 ; prom_childern = Ø; for (j = 1 ; j ≤ n ; j++;) { col [i] = j ; if (promising(i)) { m++; prom_children = prom _ children U {i}; if (m!= 0) { j = random selection from prom _childeren; col [i]; return numnodes; روش مکاشفه‌ای. برای حل این مسئله که دارای ۹۲ جواب است، باید تکنیکهایی جهت کاهش حالات، روش یا امتحان تک تک جواب‌ها انجام شود. تعداد همه حالاتی که می‌تواند در روش
انجام شود. تعداد همه حالاتی که می‌تواند در روش Brute Force چک شود برابر ۱۶٬۷۷۷٬۲۱۶ یا هشت به توان هشت است! یکی از روش‌های حل این مسئله برای n&gt;=4 یا n=1 استفاده از روش مکاشفه‌ای ( )است: 1- عدد n را بر عدد ۱۲ تقسیم کن و باقی‌مانده را یادداشت کن ۲- به ترتیب اعداد زوج ۲ تا n را در لیستی بنویس ۳- اگر باقی‌مانده ۳ یا ۹ بود، عدد ۲ را به انتهای لیست انتقال بده. ۴- به لیست اعداد فرد ۱ تا n را به ترتیب اضافه کن، اما اگر باقی‌مانده ۸ بود اعداد را دو به دو باهم عوض کند (مثلاً ۱و۳و۵و۷و۹ تبدیل به ۳و۱و۷و۵و۹ میشه) ۵-
کند (مثلاً ۱و۳و۵و۷و۹ تبدیل به ۳و۱و۷و۵و۹ میشه) ۵- اگر باقی‌مانده ۲ بود جای ۱ و۳ را با هم عوض کن و ۵ را به انتهای لیست ببر. ۶- اگر باقی‌مانده ۳ یا ۹ بود، اعداد ۱ و ۳ را به انتهای لیست ببر. ۷- حال با استفاده از لیست بدست آمده وزیرها در صفحه شطرنج چیده می‌شوند، به‌طوری‌که جای وزیر ستون اول، اولین عدد لیست، جای وزیر ستون دوم، دومین عدد لیست و... این الگوریتم یک راه حل برای حل این مسئله‌است، برای بدست آوردن همه حالات از روش‌های دیگری می‌توان استفاده کرد. روش حل مسئله ۱۲ راه حل یکتا دارد که با در نظرگیری تقارن و
۱۲ راه حل یکتا دارد که با در نظرگیری تقارن و چرخش به ۹۲ حالت قابل تبدیل است. روش‌های جستجوی محلی. می‌توان به مسئله ۸ وزیر به عنوان یک مسئله بهینه‌سازی نیز نگریست که در آن هدف بهینه کردن تعداد گاردهای جفت وزیرها می‌باشد. به عنوان مثال فرض کنید در صفحه شطرنج معمولی، ۸ وزیر را به دو روش زیر قرار دهیم: در روش چینش سمت چپ ۳ وزیر و در روش چینش سمت راست ۴ وزیر همدیگر را گارد می‌دهند. بنابراین روش چینش قبلی بهینه تر از روش چینش فعلی است. در واقع می‌توان مسئله بهینه‌سازی را به صورت زیر تعریف کرد. فرض کنید S مجموعه
را به صورت زیر تعریف کرد. فرض کنید S مجموعه همه جواب‌های ممکن برای مسئله باشد. در صورتی S* می‌تواند جواب مسئله باشد که به ازای همه جواب‌های موجود در S، S* بهینه تر از دیگر جواب‌ها باشد. در مسئله ۸ وزیر دیدیم که جوابی بهینه‌است که تعداد گاردهای جفت وزیر آن کمتر باشد. روش‌های جستجوی محلی همگی حالت‌های همسایه حالت فعلی را برای رسیدن به بهینه‌ترین جواب بررسی می‌کنند. از این رو وجود دو تابع در همه این روش‌های جستجو الزامی است. اولین تابع میزان بهینگی جواب مسئله ارزیابی می‌کند و تابع دوم یکی از حالت‌های همسایه
ارزیابی می‌کند و تابع دوم یکی از حالت‌های همسایه حالت فعلی را انتخاب می‌کند. نحوه پیاده‌سازی و طراحی الگوریتم برای انتخاب حالت همسایه در این روش‌های جستجو از اهمیت ویژه‌ای برخوردار است. به عنوان مثال برای مسئله ۸ وزیر می‌توان به شکل‌های زیر حالت‌های همسایگی را تولید کرد: ۱) دو وزیر به تصادف انتخاب شده و جای آن دو باهم عوض گردد. ۲) یکی از وزیرها به تصادف انتخاب شده و شماره سطر آن به تصادف تغییر کند. ۳) وزیری به تصادف انتخاب شده و یک خانه به سمت بالا یا پایین حرکت کند الگوریتم ژنتیک. می‌دانیم اگر دو وزیر در
حرکت کند الگوریتم ژنتیک. می‌دانیم اگر دو وزیر در یک ستون قرار گیرند قطعاً به جواب نخواهیم رسید. بنابراین قرار دادن دو وزیر در یک ستون باعث نا ممکن شدن جواب مسئله می‌شود. برای نمایش مسئله در کروموزوم‌ها از این ویژگی استفاده کرده و به صورت زیر عمل می‌کنیم: یک آرایه تک بعدی ایجاد می‌کنیم که به تعداد ستون‌های صفحه شطرنج عنصر دارد. هر عنصر از این آرایه نشان می‌دهد که وزیر در کدام سطر از آن ستون قرار دارد. به عنوان مثال اگر مسئله ۸ وزیر را در نظر بگیریم، آرایه تک بعدی باید دارای ۸ عنصر باشد. فرض کنید آرایه دارای
بعدی باید دارای ۸ عنصر باشد. فرض کنید آرایه دارای مقادیر زیر باشد: مقدار ۸ در اولین عنصر آرایه گویای این مطلب است که در ستون اول صفحه شطرنج وزیری در سطر هشتم قرار داده‌ایم. الگوریتم‌های ژنتیک ابتدا جمعیت اولیه‌ای تولید کرده و سپس سعی در بهبود بخشیدن این جمعیت دارند. برای مسئله n وزیر تولید جمعیت به صورت تصادفی خواهد بود. بدین صورت که وزیرها به‌طور تصادفی روی صفحه شطرنج قرار می‌دهیم. برای محاسبه میزان بهینگی جواب تعداد جفت وزیرهایی را که به هم گارد می‌دهند، محاسبه می‌کنیم. برای مسئله ۸ وزیر در بدترین حالت
محاسبه می‌کنیم. برای مسئله ۸ وزیر در بدترین حالت هر وزیر با همه وزیرهای دیگر گارد می‌دهد (فرض کنید همه وزیرها در یک سطر قرار گیرند). در این حالت حداکثر تعداد جفت وزیرهایی که به همدیگر گارد می‌دهند ۲۸ جفت است: در حالت کلی برای مسئله n وزیر حداکثر تعداد جفت وزیرهایی که به همدیگر گارد می‌دهند به صورت زیر محاسبه می‌شود:
الگوریتم دورگه یک مسئله را با ترکیب دو روش مختلف حل می‌کند، برای مثال شایسته سازی متغیر(، ، و غیره) و (، حذف متغیر، و غیره). الگوریتم‌های دورگه از خواص خوب روش‌های مختلف با اعمال آن‌ها بر مسایلی که می‌توانند آن‌ها به‌طور کارآمد حل کنند بهره‌برداری می‌کنند. مثلاً جستجو زمانی کارآمد است که مسئله راه حل‌های زیادی داشته باشد، در حالی که استنتاج در اثبات قابلیت رضایتمندی مسایلی که قیدهای زیادی دارند کارآمد است. استنتاج همبند چرخه ای /الگوریتم جستجوی همبند چرخه ای. این الگوریتم ترکیبی بر پایهٔ جستجو در مجموعه ای
این الگوریتم ترکیبی بر پایهٔ جستجو در مجموعه ای از متغیرها و استنتاج بر روی متغیرهای دیگر استوار است. به‌طور خاص، در جهت عکس پیمایش کردن، یا روش‌های دیگر جستجو روی تعدادی از متغیرها اعمال می‌شود؛ هرگاه یک گمارش جزئی روی این متغیرها یافت شود، استنتاج روی متغیرهای باقی‌مانده اعمال می‌شود تااطمینان حاصل کند که آیا این گمارش جزئی می‌تواند گسترش یابد تا یک راه حل را شکل بدهد. در بعضی از مسایل الگوریتم‌های کامل و کارآمد وجود دارند. مثلاً مسایلی که گراف‌های یگانه و دوگانه آن‌ها درخت‌ها و جنگل‌ها هستند در زمانی که
دوگانه آن‌ها درخت‌ها و جنگل‌ها هستند در زمانی که از درجهٔ چندجمله‌ای است می‌توانند حل شوند. این در انتخاب متغیرهایی که با جستجو بررسی شده‌اند مؤثر است. در واقع زمانی که متغیر بررسی می‌شود، می‌تواند به‌طور مؤثر از گراف حذف شود، در حالی که تمام قیود مرتبط با مقدارش را محدود می‌کند. به‌طور متناوب، یک متغیر بررسی شده می‌تواند با تعدادی متغیر مجزا جایگزین شود، یکی برای هر قید، همگی دارای دامنه ای با مقدار یکسان. این الگوریتم ترکیبی کارآمد است اگر، متغیرها طوری انتخاب شوند که دو برابر کردن یا حذف کردن آن‌ها
انتخاب شوند که دو برابر کردن یا حذف کردن آن‌ها مسئله را به نوعی تبدیل کند که به راحتی با استنتاج قابل حل باشد. خصوصاً اگر این متغیرها به شکل یک چرخهٔ همبند از گراف مسئله باشند، استنتاج کارآمد است زیرا باید مسئله ای را حل کند که گراف آن درخت است، یا به‌طور معمول تر، جنگل است. چنین الگوریتمی به شکل زیر است: find a cycle cutset of the graph of the problem run search on the variables of the cutset when a consistent partial assignment to all variables are found, replace each variable of the cutset with a new
replace each variable of the cutset with a new variable for each constraint; set the domains of these new variables to the value of the old variable in the partial assignment solve the problem using inference یک چرخهٔ همبند از گراف مسئله را پیدا کن عملیات جستجو را بر روی متغیرهای همبندی اجرا کن زمانی که یک واگذاری جزئی سازگار بر همه متغیرها یافت شد، هر متغیر همبندی را با یک متغیر جدید برای هر قید جایگزین کن؛ دامنه این متغیرهای جدید را مقدار متغیر قبلی در واگذاری جزئی قرار بده مسئله را با استفاده از استنتاج
جزئی قرار بده مسئله را با استفاده از استنتاج حل کن بازدهی این الگوریتم به دو عامل متضاد بستگی دارد. از یک طرف، هر چه همبندی کوچکتر باشد، زیرمسئله ای که با جستجو قرار است حل شود کوچکتر است؛ از آنجا که استنتاج روی درخت‌ها کارآمد است، جستجو بخشی است که بیشترین تأثیر را در بازدهی دارد. از طرف دیگر، پیدا کردن یک همبندی با کمترین سایز مسئلهٔ دشواری است. در نتیجه، یک چرخهٔ همبدی کوچک به جای کوچکترین آن استفاده می‌شود. راه دیگر کاهش دادن زمان اجرای جستجو این است که بار مسیولیت بیشتری در بخش استنتاج قرار داده شود.
بار مسیولیت بیشتری در بخش استنتاج قرار داده شود. خصوصاً، استنتاج می‌تواند به‌طور نسبی کارآمد باشد حتی اگر گراف مسئله یک جنگل نباشد بلکه، گرافی کوچکتراز آن با عرض القایی باشد. این با انجام جستجو روی مجموعه ای از متغیرهایی که چرخهٔ همبندی نیستند، ولی زمانی که حذف می‌شوند برای گراف پهنای عرضی با کران ب اجاد می‌کنند، استخراج می‌شود. به چنین دسته متغیرهایی یک ب-همبندی از مسئله گفته می‌شود. عرض استنتاجی یا القایی گراف بعد از این که مجموعه ای از متغیرها حذف شدند عرض استنتاجی تعدیل شده نامیده می‌شود. در نتیجه عرض
استنتاجی تعدیل شده نامیده می‌شود. در نتیجه عرض استنتاجی تعدیل شده متناسب با یک ب-همبندی همیشه ب است. عموماً پیدا کردن یک ب- همبندی با کمترین سایز سخت است. به هر حال، یک ب-همبندی با سایز غیر مینیمم در یک ترتیب ثابت از متغیرها به راحتی یافت می‌شود. به خصوص، چنین همبندیی، یک گراف با عرضی که کران آن ب است و متناسب با ترتیب مخصوص متغیرهاست، از خود به جا می‌گذارد. الگوریتم پیدا کردن چنین همبندیی با تقلید از روند پیدا کردن گراف القایی یک مسئله با توجه به ترتیب در نظر گرفته شده متغیرهای آن، ادامه می‌یابد (این روش
نظر گرفته شده متغیرهای آن، ادامه می‌یابد (این روش از آخرین گره به ترتیب تا اولین گره ادامه پیدا می‌کند، در حالی که بین هر جفت از گره‌های پدر آن گره‌ها که به هم متصل نیستند، یک یال اضافه می‌کند). هر گاه این روند گره ای با بیش از ب تا پدر یافت یا آن را ساخت، آن گره از گراف حذف شده و به همبندی اضافه می‌شود. گراف بدست آمده هیچ گره ای که پهنای آن بیشتر از ب باشد (تعداد پدرهای آن بیشتر از ب باشد) ندارد، و در نتیجه مجموعه گره‌های حذف شده یک ب-همبندی است. یک راه چاره برای استفاده از این الگوریتم این است که اجازه
برای استفاده از این الگوریتم این است که اجازه دهیم جستجو متغیرها را بررسی کند، ولی در هر قدم اطمینان حاصل کند که آیا گراف باقی‌مانده یک جنگل است، و اگر این چنین است استنتاج را بر روی آن اجرا کند. در واقع، به جای پیدا کردن مجموعه ای از متغیرها در ابتدای کار و استفاده کردن از آن‌ها فقط در طول جستجو، الگوریتم به عنوان یک جستجوی عادی شروع به کار می‌کند؛ در هر مرحله، اگر متغیرهای واگذار شده یک ب-همبندی از مسئله تشکیل دادند، استنتاج برای بررسی رضایتمندی اجرا می‌شود. این امکان‌پذیر است زیرا بررسی این که آیا
می‌شود. این امکان‌پذیر است زیرا بررسی این که آیا مجموعه گره‌های داده شده یک ب-همبندی برای یک ب ثابت است، مسئله ای از درجه چندجمله‌ای است. الگوریتم ترکیبی درخت تجزیه. یک الگوریتم ترکیبی جستجویی/استنتاجی دیگر بر پایه درخت تجزیه کار می‌کند. عموماً، یک مسئلهٔ ارضای محدودیت می‌تواند با ایجاد یک درخت تجزیه و سپس استفاده از یک الگوریتم تخصصی حل شود. چنین الگوریتمی‌اول بر پایه توزیع قیدها بر روی گره‌ها و سپس حل کردن زیر مسئله در هر گره بستگی دارد. این توزیع ایجاد قیدهای جدیدی که تأثیرات قیدهای یک گره بر گره اضافه
جدیدی که تأثیرات قیدهای یک گره بر گره اضافه شده را نشان می‌دهد، را شامل می‌شود. دقیقتر، اگر دو گره به هم متصل باشند، متغیرهای یکدیگر را به اشتراک می‌گذارند. ارزیابی‌های مجاز این متغیرها با توجه به قیدهای گره اول به ما می‌گوید که چگونه گره اول بر متغیرهای گره دوم اثر می‌گذارد. این الگوریتم با ایجاد قیدهای مورد قبول این ارزیابی‌ها و جا دادن این قیدها در گره دوم کار می‌کند. زمانی که قیدها از برگها تا ریشه منتشر شدند، تمام گره‌ها همه قیدهایی که با آن‌ها متناسب است را دربردارند. در نتیجه مسئله در هر گره قابل حل
را دربردارند. در نتیجه مسئله در هر گره قابل حل است. دسترسی به الگوریتم دورگه با استفاده از حذف متغیر برای ایجاد قیدهای جدیدی که در بین گره‌ها توزیع می‌شود، و یک الگوریتم جستجو (مانند ، ، جستجوی محلی) روی هر گره منفرد، امکان‌پذیر است.
ساحِل‌روبی به عمل جستجو در کناره‌های دریا برای یافتن اشیای سودمند یا قیمتی گفته می‌شود. این عمل در برخی کشورهای جهان هنوز رواج دارد. بیشتر ساحل‌روبی در نقاط بین جزر و مد (میان‌کشندی) سواحل انجام می‌شود و امروزه ساحل‌روبان برای جستجو از دستگاه فلزیاب نیز بهره می‌گیرند. پیشینه. ساحل‌روبی به خاطر تنگدستی افراد پدید آمد و فقیران با یافتن تکه‌های چوب در کنار دریا از آن به عنوان هیزم استفاده می‌کردند و از اشیای دیگر برای فروش یا استفاده شخصی بهره می‌بردند. در اقیانوس آرام جنوبی از دیرباز و به‌ویژه از زمان ورود
آرام جنوبی از دیرباز و به‌ویژه از زمان ورود کاشفان اسپانیایی شماری از کشتی‌شکستگان و دورافتادگان فراری به ساحل‌روبی روی آورده‌بودند، ولی شمار این افراد در سدهٔ نوزدهم بسیار بیشتر شد. گروهی از آنان محکومان انگلیسی بودند که به استرالیا فرستاده شده‌بودند و برای فرار از محکومیت گریخته و به زندگی فردی و ساحل‌روبی روی آورده‌بودند. ولی بیشتر ساحل‌روبان این نواحی را جاشوها و شکارچیان نهنگی تشکیل می‌دادند که از کشتی‌های خود پریده و به آب زده بودند. این جاشوها کسانی بودند که پس از رسیدن کشتی‌شان به تاهیتی یا جزایر
بودند که پس از رسیدن کشتی‌شان به تاهیتی یا جزایر مارکیزی تصمیم به بازنشستگی زودهنگام یا موقتی می‌گرفتند و از کشتی خود گریخته و به سواحل جزیره‌ها پناه می‌بردند. برآوردها نشان می‌دهد که در سال ۱۸۵۰ میلادی پیرامون ۲ هزار ساحل‌روب در جزایر پلی‌نزی و میکرونزی زندگی می‌کرده‌است. برخی از این ساحل‌روب‌ها به دادوستد میان قبیله‌های بومی سرگرم می‌شدند یا برای دریافت پاداش ناخداها به دنبال لو دادن دیگر ساحل‌روبان فراری بودند.
الگوریتم چندجمله‌ای ، در نظریه کدگذاری، کد چندجمله‌ای نوعی از کدهای خطی است که مجموعهٔ کد واژه‌های قابل قبول آن شامل آن دسته از چندجمله‌ای ها(معمولاً با طول ثابت)است که با یک چندجمله‌ای داده شده و ثابت (با طول ثابت به نام چندجمله‌ای مولد) قابل قسمت هستند. تعریف. عبارت چند جمله(GF(x ای را در نظر بگیرید که عناصر آن را ضرایب آن می‌گیریم. برای ساخت کدهای چندجمله‌ای، یک رشته از n ضریب an-1,an-2... ,a۰ را با چندجمله‌ای زیر مشخص می‌کنیم: an-1xn-1+an-2xn-2+... +a۰ اعداد صحیح و ثابت را در نظر بگیرید و فرض کنید که
اعداد صحیح و ثابت را در نظر بگیرید و فرض کنید که (g(x چندجمله‌ای ثابت از درجه‌ای m (به نام چندجمله‌ای مولد) باشد. کد چندجمله‌ای ای که با (g(x تولید می‌شود، کدی خواهد بود که کد واژه‌های آن قطعاً چندجمله‌ای‌هایی با درجهٔ کمتر از n بوده و بر (g(x بخش پذیر هستند(بدون باقی‌مانده). الگوریتم‌های چندجمله‌ای. در نظریه کدگذاری، کد چندجمله‌ای نوعی از کدهای خطی است که مجموعهٔ کد واژه‌های قابل قبول آن شامل آن دسته از چندجمله‌ای ها(معمولاً با طول ثابت)است که با یک چندجمله‌ای داده شده و ثابت (با طول ثابت به نام
یک چندجمله‌ای داده شده و ثابت (با طول ثابت به نام چندجمله‌ای مولد) قابل قسمت هستند. تعریف. عبارت چند جمله(GF(x ای را در نظر بگیرید که عناصر آن را ضرایب آن می‌گیریم. برای ساخت کدهای چندجمله‌ای، یک رشته از n ضریب an-1,an-2... ,a۰ را با چندجمله‌ای زیر مشخص می‌کنیم: an-1xn-1+an-2xn-2+... +a۰ اعداد صحیح و ثابت را در نظر بگیرید، و فرض کنید که(g(x چندجمله‌ای ثابت از درجه‌ای m (به نام چندجمله‌ای مولد) باشد. کد چندجمله‌ای ای که با (g(x تولید می‌شود، کدی خواهد بود که کد واژه‌های آن قطعاً چندجمله‌ای‌های با درجهٔ کمتر
کد واژه‌های آن قطعاً چندجمله‌ای‌های با درجهٔ کمتر از n بوده و بر (g(x بخش پذیر هستند(بدون باقی‌مانده). مثال. کد چندجمله‌ای روی {GF(2) = {0,1، باm=2,n=5 و چندجمله‌ای مولد g(x) = x2 + x + 1 را در نظر بگیرید.in کد شامل کد واژه‌های زیر است: x۲+x+1, x۳+x۲+x, x۳+۱ ,۰, x۴+x۳+x۲ , x۴+x۳+x+1 , ,x۴+x,x۴+x۲+۱ به‌طور مشابه می‌توان کد واژه‌ها را به صورت رشته‌هایی از ارقام دودویی نمایش داد: ۰۰۰۰۰٬۰۰۱۱۱٬۰۱۱۱۰٬۰۱۰۰۱ ۱۱۱۰۰٬۱۱۰۱۱٬۱۰۰۱۰٬۱۰۱۰۱ توجه کنید که هر کد چندجمله‌ای خود یک کد خطی نیز هست. پس هر ترکیب خطی از کد واژه‌های
یک کد خطی نیز هست. پس هر ترکیب خطی از کد واژه‌های ان نیز کد واژه خواهدبود. کد گذاری. در یک کد چندجمله‌ای روی(GF(q، با طول کد n و چندجمله‌ای مولد(q(x، دقیقاً formula_1 کد واژه وجود خواهد داشت. البته طبق تعریف(p(x یک کد واژه‌است اگر و فقط اگر formula_2، که در آن(q(x(خارج قسمت) از درجهٔ کمتر از formula_3 است. پس چون به تعداد formula_1 از این خارج قسمت‌ها وجود خواهد داشت، به همین تعداد نیز کد واژه‌های قابل قبول وجود دارد. بازی از مولفان مانند(Lidl &amp; Pilz, 1999) فقط تابدیلاتی formula_5 را به عنوان نسبت دادن
فقط تابدیلاتی formula_5 را به عنوان نسبت دادن داده واژه‌ها به کد واژه‌ها بر رسی می‌کنند. به هر حال بدی این روش این است که داده واژه به عنوان قسمتی از کد واژه ظاهر نمی‌شود. مثال. برای مثال بالا باformula_6, formula_7 و چندجمله‌ای مولدformula_8، انتصاب زیر را از داده واژه‌ها به کد واژه‌ها به دست می‌آوریم: رمز گشایی. یک پیغام حاوی خطا می‌تواند با یک کار بسیار سر راست شناسایی شود، به طوری که تقسیم چندجمله‌ای بر چندجمله‌ای مولد باقی‌ماندهٔ غیر صفر می‌دهد. بااین فرض که کد واژه فاقد خطاست، یک کد اصولی را می‌توان
فرض که کد واژه فاقد خطاست، یک کد اصولی را می‌توان به سادگی با برداشتن m رقم(مجموع مقابله‌ای) آن، رمز گشایی کرد. اگر خطایی وجود داشته باشد، ابتدا قبل از رمز گشایی کار تصحیح خطا باید انجام شود. برای کدهای چندجمله‌ای خاص، مثل کدهای BCH، الگوریتم‌های مفیدی برای رمز گشایی وجود دارد. ویژگی‌های کدهای چندجمله‌ای. مثل همهٔ کدهای دیجیتال، توانایی کدهای چندجمله‌ای در تشخیص و تصحیح خطا با حداقل فاصلهٔ همینگ آن کدتعیین می‌شود. از آنجایی که کدهای چندجمله‌ای نوعی کد خطی هستند، حد اقل فاصلهٔ همینگ آن‌ها برابر است باحداقل