فصل سوم

حل مسائل توسط جستجو

1. فصل اول هوش مصنوعی Artificial Intelligence
2. فصل دوم عامل های هوشمند
3. فصل سوم حل مسائل توسط جستجو
4. فصل چهارم روش‌های جستجو آگاهانه
5. فصل 5 تئوری بازی
6. فصل ششم عامل‌هاییکه به طور منطقی استدلال می‌‌کنند
7. فصل هفتم منطق مرتبه اول
8. فصل هشتم استنتاج در منطق مرتبه اول
9. فصل نهم برنامه‌ریزی
10. فصل دهم عدم قطعیت

 

 

 

یک نوع عامل هدفگرا، عامل حل مسئله نامیده می‌شود.

عامل‌های حل مسئله توسط یافتن ترتیب عملیات تصمیم می‌گیرند که چه انجام دهند تا آنها را به حالت‌های مطلوب سوق دهد.

عامل‌های حل مسئله

عامل‌های هوشمند به طریقی عمل می‌کنند که محیط مستقیماً به داخل دنباله حالت‌هایی وارد شود که معیار کارآرایی را افزایش می‌دهند.

عملیات به گونه‌ای ساده‌سازی می‌شوند که عامل قادر باشد تا هدفی را قبول کرده و به آن برسد.

الگوریتم جستجو مسئله‌ای را به عنوان ورودی دریافت نموده و راه‌حلی را به صورت دنباله عملیات بر می‌‌گرداند.

فاز اجرایی: مرحله‌ای است که در آن زمان، راه‌حلی‌ پیدا می‌شود و عملیات پیشنهادی می‌توانند انجام شوند.

به طور ساده برای طرح یک عامل مراحل «فرموله‌سازی، جستجو، اجرا» را در نظر می‌گیریم.

پس از فرموله‌سازی یک هدف و یک مسئله برای حل عامل،

1. رویه جستجویی را برای حل آن مسئله فراخوانی می‌کند.
2. از راه حل برای راهنمایی عملیاتش استفاده می‌کند و هرآنچه که راه حل پیشنهاد می‌کند را انجام می‌دهد.
3. آن مرحله را از دنباله حذف می‌کند.
4. زمانی که راه‌حل اجرا شد، عامل هدف جدیدی را پیدا می‌کند.

چهار نوع اساسی از مسائل وجود دارند:

• مسائل تک حالته (Single-state)
• مسائل چند حالته (Multiple-state)
• مسائل احتمالی (Contingency)
• مسائل اکتشافی (Exploration)

دانش و انواع مسئله دنیای مکش (جاروبرقی):

اگر دنیا حاوی دو محل باشد:

هر محل ممکن است که شامل خاک باشد و یا نباشد و عامل ممکن است که در یک محل یا دیگر محل‌ها باشد؛ که دارای هشت حالت متفاوت خواهد بود.

هدف تمیز کردن تمام خاک‌هاست که در اینجا معادل با مجموعه حالت‌ {8و 7} است.

مدل‌های مختلف برای مسئله جاروبرقی:

– مدل تک حالته:

حس‌گرهای عامل به آن اطلاعات کافی می‌دهند تا وضعیت دقیق مشخص شود. (دنیا قابل دسترسی است). عامل می‌تواند محاسبه کند که کدام وضعیت پس از هر دنباله از عملیات قرار خواهد گرفت.

– مدل چند حالته:

عامل تمام اثرهای عملیاتش را می‌داند اما دسترسی به حالت دنیا را محدود کرده است.

زمانی که دنیا تماماً قابل دسترسی نیست عامل باید در مورد مجموعه حالت‌هایی که ممکن است به آن برسد استدلال کند.

– مدل احتمالی:

با این مدل حل مسئله، حس‌گرهایی را در طول فاز اجرایی نیاز داریم. عامل اکنون باید تمام درخت عملیاتی را بر خلاف دنباله عملیاتی منفرد، محاسبه کند. که به طور کلی هر شاخه درخت، با یک امکان احتمالی که از آن ناشی می‌شود، بررسی می‌شود.

مدل اکتشافی:

عاملی که هیچ اطلاعاتی در مورد اثرات عملیاتش ندارد.

در این حالت، عامل باید تجربه کند و به تدریج کشف کند که چه عملیاتی باید انجام شود و چه وضعیت‌هایی وجود دارند. این روش یک نوع جستجو است.

اگر عامل نجات یابد، «نقشه‌ای» از محیط را یاد می‌گیرد که می‌تواند مسائل بعدی را حل کند.

مسائل و راه‌حل‌های خوب تعریف شده

مسئله: در واقع مجموعه‌ای از اطلاعات است که عامل از آنها برای تصمیم‌گیری در مورد اینکه چه کاری انجام دهد، استفاده می‌کند.

عناصر اولیه تعریف یک مسئله، وضعیتها  عملیات هستند.

برای تعریف یک مسئله موارد زیر نیاز داریم:

• وضعیت آغازین (initial state) که عامل خودش از بودن در آن آگاه است.
• مجموعه‌ای از عملیات ممکن، که برای عامل قابل دسترسی باشد.
• آزمون هدف (goal test)، که عامل می‌تواند در یک تعریف وضعیت منفرد آن را تقاضا کند تا تعیین گردد که آن حالت، وضعیت هدف است یا خیر.
• تابع هزینه مسیر، تابعی است که برای هر مسیر، هزینه‌ای را در نظر می‌گیرد؛ و با حرف g مشخص می‌شود.

هزینه یک سفر= مجموع هزینه‌های عملیات اختصاصی در طول مسیر

برای حل مسئله چند حالته، فقط به یک اصلاح جزئی نیاز داریم:

یک مسئله شامل:

• یک مجموعه حالت اولیه
• مجموعه‌ای از عملگرهای ویژه برای هر عمل به گونه‌ای که از هر وضعیت داده شده مجموعه‌ای حالات رسیده شده و یک آزمون هدف و تابع هزینه مسیر را معین کند.

یک عملگر:توسط اجتماع نتایج اعمال عملگر در هر وضعیت مجموعه، به کار برده می‌شود.

یک مسیر: مجموعه حالات را مرتبط می‌کند.

یک راه حل: مسیری است که به مجموعه‌ای از حالات که تمام آنها، وضعیت هدف هستند، سوق می‌دهند.

اندازه‌گیری کارایی حل مسئله:

کارایی یک جستجو، حداقل از سه طریق می‌تواند اندازه‌گیری شود:

• آیا این جستجو راه حلی پیدا می‌کند؟
• آیا راه حلی مناسبی است؟
• هزینه جستجو از نظر زمانی و حافظه مورد نیاز برای یافتن راه حل چیست؟

مجموع هزینه جستجو= هزینه مسیر + هزینه جستجو

عامل باید تصمیم بگیرد که چه منابعی را فدای جستجو و چه منابعی را صرف اجرا کند.

انتخاب حالات و عملیات

هنر واقعی حل مسئله، تصمیم‌گیری در مورد این است که چه چیزهایی در تعریف حالات و عملگرها باید به حساب آورده شوند و چه چیزهایی باید کنار گذاشته شوند.

انتزاع:

فرآیند حذف جزئیات از یک بارنمایی انتزاع (abstraction) نامیده می‌شود.

همانگونه که تعریف را خلاصه می‌کنیم می‌بایست عملیات را نیز خلاصه نمائیم.

انتزاع به این دلیل مفید است، که انجام هر کدام از عملیات آسانتر از مسئله اصلی است.

انتخاب یک انتزاع خوب از این رو شامل حذف تا حد ممکن می‌شود تا زمانی که عملیات خلاصه شده برای انجام آسان باشند.

مسائل نمونه: مسائل اسباب‌بازی

معمای 8:

معمای 8 نمونه‌ای است شامل یک صفحه 3*3 با 8 مربع شماره دار در یک صفحه خالی.

هر مربع که مجاور خانه خالی است. می‌تواند به درون آن خانه برود. هدف رسیدن به ساختاری است که در سمت راست شکل نشان داده شده است. نکته مهم این است که بجای اینکه بگوییم «مربع شماره 4 را به داخل فضای خالی حرکت بده» بهتر است بگوییم «فضای خالی جایش را با مربع سمت چپش عوض کند.»

 

 

 

 

 

 

 

 

 

حالت‌ها: توصیف وضعیت مکان هر 8 مربع را در یکی از 6 خانه صفحه مشخص می‌کند. برای کارایی بیشتر، بهتر است که فضاهای خالی نیز ذکر شود.

عملگر‌ها: فضای خالی به چپ، راست، بالا و پائین حرکت کند.

آزمون هدف: وضعیت با ساختار هدف مطابقت می‌کند.

هزینه مسیر: هر قدم ارزش 1 دارد، بنابراین هزینه مسیر همان طول مسیر است.

مسئله 8 وزیر:

هدف از مسئله 8 وزیر، قرار دادن 8 وزیر بر روی صفحه شطرنج به صورتی است که هیچ وزیری نتواند به دیگری حمله کند.

دو نوع بیان ریاضی اصلی وجود دارد بیان افزایشی که با جایگزینی وزیرها، به صورت یکی یکی کار می‌کند و دیگری بیان وضعیت کامل که با تمام 8  وزیر روی صفحه شروع می‌کند و آنها را حرکت می‌دهد.

در  این فرمول ما 64 امکان داریم.

بنابراین ما تست هدف و هزینه مسیر را به صورت زیر خواهیم داشت:

آزمون هدف: 8  وزیر روی صفحه، که با هم برخورد ندارند.

هزینه مسیر: صفر.

حالات: ترتیب از صفر تا 8 وزیر بدون هیچ برخورد.

عملگرها: یک وزیر را در خالی‌ترین ستون سمت چپ جایگزین کنید که هیچ برخوردی با بقیه نداشته باشد.

Cryptarithmetic :

در مسائل کریپتاریتمتیک، حروف به جای ارقام می‌نشینند و هدف یافتن جایگزینی از اعداد برای حروف است که مجموع نتیجه از نظر ریاضی درست باشد. معمولاً هر حرف باید به جای یک رقم مختلف بنشینند.

مثال:

 

 

 

یک فرمول ساده:

حالات: یک معمای Cryptarithmetic با چند حروف جایگزین شده توسط ارقام.

عملگرها: وقوع یک حروف را با یک رقم جایگزین کنید که قبلاً در معما ظاهر نشده باشد.

آزمون هدف: معما فقط شامل ارقام است و یک مجموع صحیح را بر می‌گرداند.

هزینه مسیر: صفر- تمام راه حل‌های صحیح است.

می‌خواهیم که از تبدیل جایگزینی‌های مشابه اجتناب کنیم:

• قبول یک ترتیب ثابت مانند ترتیب الفبایی.
• هر کدام که بیشترین محدودیت جایگزینی را دارد، انتخاب کنیم؛ یعنی حرفی که کمترین امکان مجاز را دارند، محدودیت‌های معما را می‌دهد.

دنیای مکش:

مسئله تک حالته: عامل از جای خودش اطلاع دارد و تمام مکان‌های آلوده را می‌شناسد و دستگاه مکنده ما درست کار می‌کند.

حالات: یکی از 8 حالت نشان داده شده.

عملگرها: حرکت به چپ، حرکت به راست، عمل مکش.

آزمون هدف: هیچ خاکی در چهار گوش‌ها نباشد.

هزینه مسیر: هر عمل ارزش 1 دارد.

مسئله چند حالته: عامل دارای حسگر نمی‌باشد.

مجموعه وضعیت‌ها : زیر مجموعه‌ای از حالات.

عملگرها: حرکت به چپ، حرکت به راست، عمل مکش.

آزمون هدف: تمام حالات در مجموعه حالت‌ها فاقد خاک باشند.

هزینه مسیر: هر عمل هزینه 1 دارد.

مسئله کشیش‌ها و آدمخوارها:

سه کشیش و سه آدم خوار در یک طرف رودخانه قرار دارند و هم چنین قایقی که قادر است یک یا دو نفر را حمل کند. راهی را بیابید که هر نفر به سمت دیگر رودخانه برود، بدون آنکه تعداد کشیش‌ها در یکجا کمتر از آدم خوارها شود.

حالات: یک حالت شامل یک دنباله مرتب شده از عدد است که تعداد کشیش‌ها، تعداد آدمخوارها و محل قایق در ساحلی از رودخانه که از آنجا مسئله شروع شده را نمایش می‌دهد.

عملگرها: از هر حالت، عملگرهای ممکن یک کشیش، یک آدمخوار، دو کشیش، دو آدمخوار، یا یکی از هر کدام را در قایق جا می‌دهند.

آزمون هدف: رسیدن به حالت(0و 0 و 0).

هزینه مسیر: تعداد دفعات عبور از رودخانه.

مسائل دنیای واقعی

مسیریابی:

الگوریتم‌های مسیر یابی کاربردهای زیادی دراند، مانند مسیریابی در شبکه‌های کامپیوتری، سیستم‌های خودکار مسافرتی و سیستم‌های برنامه‌نویسی مسافرتی هوایی.

مسائل فروشنده دوره گرد و تور :

مسئله فروشنده دوره گرد مسئله مشهوری است که در آن هر شهر حداقل یکبار باید ملاقات شود هدف یافتن کوتاهترین مسیر است.

علاوه بر مکان عامل، هر حالت باید مجموعه شهرهایی را که عامل ملاقات کرده، نگه دارد.

علاوه بر برنامه‌ریزی صفر برای فروشنده دوره‌گرد، این الگوریتم‌ها برای اعمالی نظیر برنامه‌ریزی حرکات مته خوردکار سوراخ‌کننده برد مدار استفاده می‌شود.

طرح VISI :

ابزار طراحی کمکی کامپیوتری در هر فازی از پردازش استفاده می‌شود دو وظیفه بسیار مشکل عبارتند از:

Channel routing

Cell layout

که بعد از اینکه ارتباطات و اتصالات مدار کامل شد، این دو قسمت انجام می‌شوند.

هدف طراحی مداری روی تراشه است که کمترین مساحت و طول اتصالات و بیشترین سرعت را داشته باشد.

هدف قرار دادن سلول‌ها روی تراشه به گونه‌ای است که آنها روی هم قرار نگیرند و بنابراین فضایی نیز برای سیم‌های ارتباطی وجود دارد که باید بین سلول‌ها قرار گیرند.

کانال‌یابی، مسیر ویژه‌ای را برای هر سیم که از فواصل بین سلول‌ها استفاده می‌کند، پیدا می‌کند.

هدایت ربات:

یک ربات می‌تواند در یک فضای پیوسته با یک مجموعه نامحدودی از حالات و عملیات ممکن حرکت کند.

ربات‌های واقعی باید قابلیت تصحیح اشتباهات را در خواندن حسگرها و کنترل موتور داشته باشند.

خط تولید خودکار:

در مسائل سرهم‌بندی، مشکل یافتن قانونی است که تکه‌های چند شیئی را جمع کند. اگر ترتیب نادرست انتخاب شود، راهی نیست که بتوان قسمت‌های بعدی را بدون از نو انجام دادن قسمت‌های قبلی، اضافه کرد.

کنترل یک مرحله در دنباله، یک مسئله جستجوی پیچیده هندسی است که ارتباط نزدیکی با هدایت ربات دارد. از این رو تولید مابعدهای مجاز گران‌ترین قسمت دنباله سرهم‌بندی است و استفاده از الگوریتم‌های آگاهانه برای کاهش جستجو، ضروری است.

جستجو برای راه‌حل:

نگهداری و گسترش یک مجموعه از دنباله‌های راه حل ناتمام.

جستجوی حالت‌های موجود و یافتن راه‌حل بنا بر اصل جستجو.

تولید دنباله‌های عمل:

فرایند گسترش حالت: فرایندی که از طریق تولید مجموعه جدیدی از حالات، عملگرها در حالت جاری را به کار گرفته، و نتیجتاً حالت هدف را در مجموعه وارد می‌کند.

اصل جستجو: انتخاب یک حالت و کنار گذاشتن بقیه برای بعد، زمانی که اولین انتخاب به حل مسئله منجر نشود.

ریشه درخت جستجو: یک گره جستجو است که با حالت اولیه مطابقت دارد.

گره‌های برگی درخت: حالاتی هستند که دارای فرزندی در درخت نیستند.

ساختارهای داده برای درخت‌های جستجو:

گره به عنوان یک ساختار داده با پنج قسمت به شرح زیر است:

• وضعیتی که گره در فضای حالات دارا می‌باشند.
• گره‌ای که در جستجوی درخت، گره جدیدی را تولید کرده است (گره والد).
• عملگری که برای تولید گره به کار رفته است.
• تعداد گره‌های مسیر، از ریشه تا گره موردنظر (عمق گره).
• هزینه مسیر، از حالت اولیه تا گره.

تفاوت بین گره‌ها و حالت‌ها:

گره‌ها عمق و والد دارند؛ در صورتی که حالت‌ها شامل چنین چیزهایی نیستند.

استراتژی جستجو:

استراتژی‌ها باید دارای 4 معیار زیر باشند:

• کامل بودن
• پیچیدگی زمانی
• پیچیدگی فضا
• بهینگی

ما 6 استراتژی را بررسی خواهیم کرد:

• جستجوی سطحی
• جستجوی با هزینه یکسان
• جستجوی عمقی
• جستجوی عمقی محدود شده
• جستجوی عمیق‌کننده تکراری
• جستجوی دوطرفه
• جستجوی سطحی:
• در این استراتژی که بسیار سیستماتیک است، ابتدا گره ریشه، و سپس تمام گره‌های دیگر گسترش داده می‌شوند.
• به عبارت کلی‌تر، تمام گره‌های عمیق d، قبل از گره‌های عمیق d+1 گسترش داده می‌شوند.
• مزایا:
• جستجوی سطحی، کامل و بهینه می‌باشد زیرا هزینه مسیر، یک تابع کاهش‌نیابنده از عمق گره است.
• معایب:
• مرتبه زمانی O(bd) می باشد که نمایی است.
• نیاز به حافظه زیاد.

جستجوی با هزینه یکسان:

در این استراتژی، در شرایط عمومی، اولین راه حل، ارزان‌ترین راه نیز هست.

اگر هزینه مسیر توسط تابع g(n) اندازه‌گیری شود، در این صورت جستجوی سطحی همان جستجوی با هزینه یکسان است با:

g(n)=DEPTH(n)

جستجوی عمقی:

این استراتژی، یکی از گره‌ها را در پائین‌ترین سطح درخت بسط می‌دهد؛ اما اگر به نتیجه نرسید، به سراغ گره‌هایی در سطوح کم عمیق‌تر می‌رود.

مزایا:

این جستجو، نیاز به حافظه نسبتاً کمی فقط برای ذخیره مسیر واحدی از ریشه به یک گره برگی، و گره‌های باقی‌مانده بسط داده نشده دارد.

پیچیدگی زمانی O(bm) می‌باشد. به طوریکه b فاکتور انشعاب فضای حالت، و m حداکثر عمق درخت باشد.

معایب:

اگر مسیری را اشتباه طی کند، هنگام پائین رفتن گیر می‌کند.

جستجوی عمقی نه کامل و نه بهینه است.

در درخت‌های با عمق نامحدود و بزرگ این استراتژی کار نمی‌کند.

جستجوی عمقی محدود شده:

این استراتژی، برای رهایی از دامی که جستجوی عمقی در آن گرفتار می‌شد،  از یک برش استفاده می‌کند.

جستجوی عمقی محدود شده کامل است اما بهینه نیست.

زمان و پیچیدگی فضای جستجوی عمقی محدودشده، مشابه جستجوی عمقی است. این جستجو پیچیدگی زمانی O(bL) و فضای O(bL) را خواهد داشت، که L محدوده عمق است.

در یک درخت جستجوی نمایی، تقریباً تمام گره‌ها در سطح پائین هستند، بنابراین موردی ندارد که سطوح بالایی چندین مرتبه بسط داده شوند. تعداد بسط‌ها در یک جستجوی عمقی محدود شده با عمق d و فاکتور انشعاب b به قرار زیر است:

1+b+b2+…+bd-2+bd-1+bd

جستجوی عمیق‌کننده تکراری:

قسمت دشوار جستجوی عمقی محدود شده، انتخاب یک محدوده خوب است.

اگر محدوده عمق بهتری را پیدا کنیم، این محدوده، ما را به سوی جستجوی کاراتری سوق می‌دهد. اما برای بیشتر مسائل، محدوده عمقی مناسب را تا زمانی که مسئله حل نشده است، نمی‌شناسیم.

جستجوی عمیق‌کننده تکراری استراتژی است که نظریه انتخاب بهترین محدوده عمقی، توسط امتحان تمام محدوده مسیرهای ممکن را یادآوری می‌کند.

مزایا:

ترکیبی از مزایای جستجوی سطحی و عمقی را دارد.

این جستجو مانند جستجوی سطحی کامل و بهینه است، اما فقط مزیت درخواست حافظه اندک را از جستجوی عمقی دارد.

مرتبه بسط حالات مشابه جستجوی سطحی است، به جز اینکه بعضی حالات چند بار بسط داده می‌شوند.

در جستجوی عمیق‌کننده تکراری، گره‌های سطوح پائینی یک بار بسط داده می‌شوند، آنهایی که یک سطح بالاتر قرار دارند دوبار بسط داده می‌شوند و الی‌آخر تا به ریشه درخت جستجو برسد، که d+1 بار بسط داده می‌شوند.

بنابراین مجموع دفعات بسط در این جستجو عبارتست از:

(d+1)1+(d)b+(d-1)b2+…+3bd-2+2bd-1+1bd

پیچیدگی زمانی این جستجو هنوز O(bd) است، و پیچیدگی فضا O(bd) است.

در حالت کلی، عمیق‌کننده تکراری، روش جستجوی برتری است؛ زمانی که فضای جستجوی بزرگی وجود دارد و عمق راه حل نیز مجهول است.

جستجوی دوطرفه:

ایده جستجوی دوطرفه در واقع شبیه‌سازی جستجویی به سمت جلو از حالت اولیه و به سمت عقب از هدف است و زمانی که این دو جستجو به هم برسند، متوقف می‌شود.

برای پیاده‌سازی الگوریتم سؤالات زیر باید پاسخ داده شوند:

1- سؤال اصلی این است که، جستجو از سمت هدف به چه معنی است؟ ماقبل‌های (predeccessors) یک گره n را گره‌هایی درنظر می‌گیریم که n مابعد (successor) آنها باشد. جستجو به سمت عقب بدین معناست که تولید ماقبل‌ها از گره هدف آغاز شود.

2- زمانی که تمام عملگرها، قابل وارونه‌شدن باشند، مجموعه ماقبل‌ها و مابعدها یکسان هستند.

3- چه کار می‌توان کرد زمانی که هدف‌های متفاوتی وجود داشته باشد؟ اگر لیست صریحی از حالت‌های هدف وجود داشته باشد، می‌توانیم یک تابع ماقبل برای مجموعه حالت تقاضا کنیم در حالیکه تابع مابعد یا (جانشین) در جستجوی مسائل چندوضعیته به کار می‌رود.

4- باید یک راه موثر برای کنترل هر گره جدید وجود داشته باشد تا متوجه شویم که آیا این گره قبلاً در درخت جستجو توسط جستجوی طرف دیگر، ظاهر شده است یا خیر.

5- نیاز داریم که تصمیم بگیریم که چه نوع جستجویی در هر نیمه قصد انجام دارد.

مقایسه استراتژی‌های جستجو:

ارزیابی استراتژی‌های جستجو. b فاکتور انشعاب، d عمل پاسخ، m ماکزیمم عمق درخت جستجو، l محدودیت عمق است.

 

 اجتناب از حالات تکراری:

برای مسائل زیادی، حالات تکراری غیرقابل اجتناب هستند. این شامل تمام مسائلی می‌شود که عملگرها قابل وارونه شدن باشند، مانند مسائل مسیریابی و کشیش‌ها و آدمخوارها.

سه راه برای حل مشکل حالات تکراری برای مقابله با افزایش مرتبه و سرریزی فشار کار کامپیوتر وجود دارد:

به حالتی که هم اکنون از آن آمده‌اید، برنگردید. داشتن تابع بسط (یا مجموعه عملگرها) از تولید مابعدهایی که مشابه حالتی هستند که در آنجا نیز والدین این گره‌ها وجود دارند، جلوگیری می‌کند.

1. از ایجاد مسیرهای دوار بپرهیزید. داشتن تابع بسط (یا مجموعه عملگرها) از تولید مابعدهای یک گره که مشابه اجداد آن گره است، جلوگیری می‌کند.
2. حالتی را که قبلاً تولید شده است، مجدداً تولید نکنید. این مسئله باعث می‌شود که هر حالت در حافظه نگهداری شود، پیچیدگی فضایی O(bd) داشته باشد. بهتر است که به O(s) توجه کنید که s تعداد کل حالات در فضای حالت ورودی است.

جستجوی ارضاء محدودیت (Constraint Satisfaction Problem):

نوع خاصی از مسئله است که CSP، حالات توسط مقادیر مجموعه‌ای از متغیرها تعریف می‌شوند و آزمون هدف مجموعه‌ای از محدودیت‌ها را به آنها اختصاص می‌دهد که متغیر ملزم به پیروی از آنها هستند.

CSPها می‌توانند توسط الگوریتم‌های جستجوی geneal-purpose حل شوند، اما به علت ساختار خاص آنها، الگوریتم‌هایی صرفاً برای CSPهایی طرح می‌شوند که از الگوریتم‌های عمومی کارآیی بهتری دارند.

محدودیت‌ها به گونه‌های مختلفی ظاهر می‌شوند.

• محدودیت‌های یکتا
• محدودیت‌های دودویی
• محدودیت‌های مطلق
• محدودیت‌های اولویت‌دار
• در CSPهای گسسته که دامنه‌های آن محدود هستند، محدودیت‌ها می‌توانند به سادگی توسط شمردن ترکیبات مجاز مقادیر نمایش داده شوند.
• با استفاده از یک شماره‌گذاری، هر CSP گسسته می‌تواند به یک CSP دودویی تبدیل شود.

چطور یک الگوریتم جستجوی همه منظوره را در یک CSP به کار ببریم.:

در حالتی که تمام متغیرها، تعیین نشده‌اند:

عملگرها مقداری را به یک متغیر از مجموعه‌ مقادیر ممکن، نسبت می‌دهند.

آزمون هدف تمام متغیرها کنترل می‌کند که آیا مقدار گرفته‌اند و تمام محدودیت‌ها از بین رفته‌اند یا خیر.

• توجه کنید که حداکثر عمق درخت جستجو در n و تعداد متغیرها و تمام راه‌حل‌ها در عمق n  هستند.
• جستجوی عمقی روی یک CSP زمان جستجو را تلف می‌کند زمانی که محدودیت‌ها قبلاً مختلف شده باشند.