نمونه سوالات هوش مصنوعی با پاسخ تشریحی

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

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

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

فیلم های رایگان آموزش هوش مصنوعی که به آنها نیاز دارید

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

هوش مصنوعی جلسه 1

هوش مصنوعی جلسه 2

هوش مصنوعی جلسه 3

هوش مصنوعی جلسه 4

نکته و تست هوش مصنوعی جلسه 1

جواب تشریحی هوش مصنوعی کنکور ارشد کامپیوتر 1403

نمایش بیشتر

نمایش کمتر

خرید فیلم های کامل هوش مصنوعی

فیلم درس هوش مصنوعی

۱۵٪ تخفیف

950,000 تومان 765,000 تومان

رامین رضوی

60 ساعت

خرید دوره

فیلم نکته و تست هوش مصنوعی

۱۵٪ تخفیف

800,000 تومان 680,000 تومان

رامین رضوی

۳۰ ساعت

خرید دوره

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

نمونه سوالات فصل الگوریتم های جستجوی ناآگاهانه درس هوش مصنوعی

دشوار روی یک توری n*n که هر خانه به چهار همسایه خود متصل است، خانه میانی را نقطه شروع جستجو و نقطه $\left(\circ \ ,\ \circ \right)$ در نظر می‌گیریم. گره هدف در موقعیت $\left(\mathrm{X\ ,\ Y}\right)$ است. در این گراف الگوریتم جستجوی A بدون تست تکراری بودن حالات، حداکثر $\left(\left({\mathrm{4}}^{\mathrm{X\ +\ Y\ +\ }\mathrm{1}}-\ \mathrm{1}\right)\ / \, \mathrm{3}\right)\mathrm{-}\mathrm{1}$ گره و الگوریتم جستجوی B با تست تکراری بودن حالات، حداکثر $\mathrm{2}\left(\mathrm{X\ +\ Y}\right)\left(\mathrm{X\ +\ Y\ +\ }\mathrm{1}\right)\ -\mathrm{1}$ گره را قبل از یافتن جواب بسط می‌دهند. کدام یک از گزینه‌های زیر در مورد این دو الگوریتم صحیح است؟ الگوریتم های جستجوی ناآگاهانه

1 A و B هر دو الگوریتم اول عمق (Depth first) هستند.

2 A و B هر دو الگوریتم اول پهنا (Breadth first) هستند.

3 A الگوریتم اول پهنا (Breadth first) و B الگوریتم اول عمق (Depth first) است.

4 A الگوریتم اول عمق (Depth first) و B الگوریتم اول پهنا (Breadth first) است.

گزینه 2 صحیح است.

(نکته : در این تست فرض شده است که تست در الگوریتم BFS در زمان بسط انجام می‌شود)

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

۱- جستجوی A بدون تست تکراری بودن حالات (درختی)

آ) BFS

در جستجو اول سطح در هر مرحله با توجه به اینکه هر گره چهار فرزند دارد، فاکتور انشعاب ۴ است (چون تکرار هم داریم) و در هر مرحله تعداد گره‌های ۴ برابر می‌شود و در صورتی که بدانیم هدف در خانه ‎‌ (x,y)است داریم : 

تعداد گره‌های بسط داده شده $=\mathrm{1\ +\ b\ +\ }b^{2\ }+\ ......+b^{d\ }-1\ =\ \frac{b^{d+1}\ -1}{b-1}\ \ \ \ -1\ =\ \frac{4^{x+y+1}-1\ }{3}\ -1$

نکته : 

 ۱- آخر برای کم کردن خود گره هدف است.

 از آن‌جایی که در هر مرحله به یکی از گره‌های مجاور می‌رویم و حرکت مورب نداریم می‌توان گفت d = x +y  می‌باشد.

 

ب) DFS

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

 

۲- جستجوی A با تست تکراری بودن حالات (گرافی)

آ) BFS

در این جستجو مطابق شکل زیر در هر مرحله یک دور به مربع اضافه می‌شود تا به هدف که در (x,y) قرار دارد برسیم. تعداد گره‌هایی که در هر مرحله بسط داده می‌شوند الگویی مطابق فرمول زیر دارند: 

تعداد گره‌های بسط داده شده =

$\mathrm{1+b+}2b+\dots \dots +\mathrm{bd\ -1}=1+4\left(1+2+\dots .+d\right)-1=1+\frac{4d\left(d+1\right)}{2}\ -1=2\left(x+y\right)\left(x+y+1\right)$

 

نکته : 

 ۱- آخر برای کم کردن خود گره هدف است.

 از آن‌جایی که در هر مرحله به یکی از گره‌های مجاور می‌رویم و حرکت مورب نداریم می‌توان گفت d = x +y می‌باشد.

 

ب) DFS

این روش در صورتی که تست تکراری بودن حالات را داشته باشیم در بدترین حالت همه گره‌های صفحه یعنی $n^2-1$ گره را بررسی می‌کند.

با توجه به صورت سوال و با توجه به مقادیر که در بالا بدست آوردیم بهترین گزینه برای این پاسخ این سوال گزینه دوم است.

متوسط محیط زیر با وضعیت شروع S و وضعیت هدف G را در نظر بگیرید. فرض کنید خانه‌های خاکستری مسدود هستند و نمی‌توان به آن‌ها وارد شد. همچنین در هر وضعیت چهار کنش بالا U، راست R، پایین D و چپ L با هزینه برابر قابل انجام هستند. اولویت انتخاب کنش‌ها هم در شرایط یکسان به ترتیب از راست به چپ D، R، U و L خواهد بود. اگر کنشی منجر به برخورد به خانه‌های مسدود یا دیوارها شود، عامل (agent) سر جایش می‌ماند. اگر جستجو گرافی (graph search) انجام شود، خانه A در شکل زیر چندمین گره برداشته شده از صف برای گسترش در روش‌های DFS و BFS خواهد بود؟ الگوریتم های جستجوی ناآگاهانه

	A
	S				G

1 2: DFS و 2: BFS

2 2: DFS و 6: BFS

3 6: DFS و 2: BFS

4 6: DFS و 6: BFS

گزینه 2 صحیح است.

شکل زیر را در نظر بگیرید :

روش BFS :

درخت حاصل از جستجو به این روش و ترتیب بسط گره‌ها در ادامه نمایش داده شده است. همان‌طور که در شکل زیر مشخص است پس از S تمامی فرزندان آن بسط داده می‌شوند و درنهایت نوبت به فرزندان گره C می‌رسد و گره A از فرزندان این گره چون کنش UP اولویت بیشتر دارد زودتر به صف اضافه شده و در نتیجه زودتر هم نوبت به بسط آن می‌رسد و به عنوان گره ۶ ام بسط داده می‌شود. 

روش DFS :

درخت حاصل از جستجو به این روش و ترتیب بسط گره‌ها در ادامه نمایش داده شده است. همان‌طور که در شکل زیر مشخص است پس از S فرزند اول آن یعنی C و پس از آن گره A بسط پیدا می‌کند و در واقع گره A به عنوان گره ۳ ام بسط داده می‌شود.

اعداد بدست آمده در هیچکدام از گزینه‌ها موجود نیستند اما می‌توان با اغماض گزینه دوم را بعنوان پاسخ سوال در نظر گرفت. 

نمونه سوالات فصل الگوریتم های جستجوی آگاهانه درس هوش مصنوعی

آسان می‌خواهیم با استفاده از روش جستجوی $A^*$  پاسخ بهینه‌ی (optimal) مسأله‌ای را بیابیم، با فرض اینکه هر یک از سه تابع ابتکاری $h_1$,$h_2$,$h_3$ برای این منظور قابل استفاده باشد، کدام یک از توابع ترکیبی زیر نیز برای یافتن حل بهینه‌ی مسأله قابل استفاده خواهد بود؟ الگوریتم های جستجوی آگاهانه

1 ${\mathrm{h}}_{\mathrm{1}}+{\mathrm{h}}_{\mathrm{2}}+{\mathrm{h}}_{\mathrm{3}}$

2 $\frac{{\mathrm{h}}_{\mathrm{1}}+{\mathrm{h}}_{\mathrm{2}}+{\mathrm{h}}_{\mathrm{3}}}{\mathrm{3}}$

3 ${\mathrm{h}}_{\mathrm{1}}\times {\mathrm{h}}_{\mathrm{2}}\times {\mathrm{h}}_{\mathrm{3}}$

4 $\sqrt{{\mathrm{h}}_{\mathrm{1}}\times {\mathrm{h}}_{\mathrm{2}}\times {\mathrm{h}}_{\mathrm{3}}}$

گزینه 2 صحیح است.

ابتدا دو نکته را یادآوری می‌کنیم :‌

۱- در روش جستجوی  A*  :

-  در حالت جستجوی درختی در صورتی که تابع هیوریستیک قابل قبول باشد،‌ الگوریتم A*  پاسخ بهینه را تضمین می‌کند .

-  در حالت جستجوی گرافی در صورتی که تابع هیوریستیک سازگار باشد،‌ الگوریتم A*  پاسخ بهینه را تضمین می‌کند.

۲- در صورتی که چند تابع هیوریستیک قابل قبول داشته باشیم، میانگین حسابی و هندسی، ‌max و min آن‌ها نیز قابل قبول هستند چرا که در این توابع نیز هیچگاه مقدار h(n) تخمین زده شده  برای یک گره بیشتر از مقدار اصلی هزینه مسیر آن گره تا گره هدف نمی‎‌شود. 

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

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

 

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

 

گزینه ۳ : مشابه گزینه یک این گزینه نیز قابل قبول نیست. 

 

گزینه ۴ : در این گزینه در صورتی که فرجه رادیکال به جای ۲ ،‌ ۳ در نظر گرفته می‌شد تابعی قابل قبول به دست می‌آمد.

 

 

متوسط در صورت استفاده از روش تپه‌نوردی از طریق تندترین شیب (Steepest ascend hill climbing) با توجه به شکل زیر کدام یک از گزینه‌های زیر صحیح‌تر است؟ اعداد روی یال‌ها هزینه واقعی هر یال و اعداد داخل هر گره هزینه تخمینی آن گره تا گره‌ی هدف است. (A گره‌ی شروع و H گره هدف است.) الگوریتم های جستجوی آگاهانه

1 جستجو به فلات برخورد خواهد کرد.

2 زمان حل مسئله کاهش خواهد یافت.

3 جستجو به ماکزیمم محلی برخورد خواهد کرد.

4 تغییری در مسیر حل مسئله صورت نمی‌گیرد.

گزینه 1 صحیح است.

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

 

 

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

متوسط در گراف زیر حاصل جستجو با روش $A^*$ کدام است؟ (نقطه شروع: S، اعداد روی یال‌ها و اعداد داخل گره‌ها هزینه تخمینی گره تا هدف است) الگوریتم های جستجوی آگاهانه

1 S-A-B-G1

2 S-A-E-G2

3 S-A-E-G1

4 S-A-B-D-G2

گزینه 4 صحیح است.

در این سوال، مسیر حاصل از جستجو با روش $A^\ast$ خواسته شده است و هم چنین در شکل دو هدف وجود دارد که مسیر بهینه رسیدن به G1 هزینه ۷ و مسیر بهینه رسیدن به G2 دارای هزینه ۶ است. در ابتدا بررسی می‌کنیم که آیا تابع هیوریستیک داده شده قابل قبول است یا نه چرا که در صورتی که قابل قبول باشد مسیر حاصل از جستجو  $A^\ast$ همان مسیر بهینه است. از آن جایی که مسیر رسیدن به G2 هزینه کمتری دارد و  $A^\ast$ در صورت قابل قبول بودن این مسیر را برمی‌گرداند، هزینه مسیر واقعی را با توجه به هدف G2 محاسبه می‌کنیم که در شکل زیر مشخص شده‌اند. با مقایسه مقادیر هیوریستیک با مقادیر واقعی می‌بینیم که تابع هیوریستیک داده شده قابل قبول است پس  $A^\ast$ همان مسیر بهینه را که در شکل زیر مشخص شده است برمی‌گرداند.

روش دیگر حل سوال این بود که به صورت مستقیم الگورتیم $A^\ast$ را روی شکل اجرا کنیم که در شکل زیر درخت حاصل از آن نشان داده شده است (عدد ها ترتیب بررسی گره‌ها را نشان می‌دهند).

دشوار فرض کنید فضای جستجویی دارای پنج گره D ،C ،B ،A و  Eباشد. جدول زیر فواصل واقعی این گره‌ها را از هم نشان می‌دهد. (وجود عدد در هر خانه جدول نشان‌دهندۀ این است که از گره مربوط به سطر به سمت گره مربوط به ستون مسیری به طول عدد وجود دارد.) اگر گره A گره شروع، گره E گره هدف و تابع h تابع مکاشفه‌ای تخمین فاصله گره تا هدف باشد، کدام یک از گزینه‌های زیر صحیح است؟ الگوریتم های جستجوی آگاهانه

E	D	C	B	A
	2	8	10		A
2		2		10	B
6	2			8	C
9		2		2	D
	9	6	2		E

1 اگر h(c)=5 ، h(B)=1 و h(D)=8 ، آنگاه تابع h یک تابع یکنواخت (monotonic) و قابل قبول (admissible) است.

2 اگر h(c)=6 ، h(B)=3 و h(D)=9 ، آنگاه تابع h یک تابع یکنواخت (monotonic) و قابل قبول (admissible) است.

3 اگر h(c)=5 ، h(B)=1 و h(D)=8 ، آنگاه تابع h یک تابع یکنواخت (monotonic) نیست ولی قابل قبول (admissible) است.

4 اگر h(c)=3 ، h(B)=3 و h(D)=8 ، آنگاه تابع h یک تابع یکنواخت (monotonic) است ولی قابل قبول (admissible) نیست.

گزینه 3 صحیح است.

ابتدا گرافی که نشان‌دهنده فواصل داده شده در جدول است را رسم می‌کنیم سپس به بررسی گزینه‌ها می‌پردازیم هم چنین می‌دانیم که یک هیوریستیک قابل قبول است اگر شرط $h \le h \ast$ برای همه گره‌های آن برقرار باشد.

گزینه ۱ : در این گزینه h(C)=5, h(B)=1 , h(D)=8  داده شده است از طرفی با توجه به گراف بالا h*(C)=6, h*(B)=2 و h*(D)=8 می‌باشد پس شرط قابل قبول بودن برای این هیوریستیک برقرار است اما این هیوریستیک شرط سازگاری را ندارد چرا که برای مثال h(D) > h(C) + c(D,C) = h(C) + 2 می‌باشد پس این گزینه نادرست است.

گزینه ۲ : در این گزینه h(C)=6, h(B)=3 , h(D)=9  داده شده است مطابق گزینه قبل h*(C)=6, h*(B)=2 و h*(D)=8 می‌باشد پس شرط قابل قبول بودن برای این هیوریستیک برقرار نیست و در مورد سازگاری آن به دلیل اینکه داریم  h(D) > h(C) + c(D,C) = h(C) + 2 این هیوریستیک ناسازگار است و این گزینه نیز نادرست است.

گزینه ۳ : در این گزینه h(C)=5, h(B)=1 , h(D)=8  داده شده است و شرط قابل قبول بودن برای این هیوریستیک برقرار است اما همان‌طور که در گزینه یک اشاره شد این هیوریستیک ناسازگار است پس این گزینه که فقط به قابل قبول بودن این تابع اشاره می‌کند درست است.

گزینه ۴ : در این گزینه h(C)=3, h(B)=3 , h(D)=8  داده شده است از طرفی می‌دانیم در صورتی که یک تابع هیوریستیک یکنواخت باشد پس حتما قابل قبول هم هست اما در صورت سوال اشاره شده است که قابل قبول نیست در نتیجه این گزینه نادرست می‌شود.

نکته : در هیچکدام از گزینه ها به h(A) اشاره نشده است و در این سوال فرض کردیم که هیوریستیک این گره درست و موجب قابل قبول نشدن یا ناسازگاری نمی‌شود.

متوسط در جستجوی ${A}^*$ در صورت استفاده از کدام تابع مکاشفه‌ای تضمین پیدا کردن جواب بهینه وجود دارد؟  الگوریتم های جستجوی آگاهانه

1 $f_1(n)$

2 $f_2(n)$

3 $f_2(n) + f_1(n)$

4 $\frac{f_1(n) + f_2(n)}{2}$

گزینه 4 صحیح است.

در روش جستجوی A*  :

  در حالت جستجوی درختی در صورتی که تابع هیوریستیک قابل قبول باشد،‌ الگوریتم A*  پاسخ بهینه را تضمین می‌کند .

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

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

گزینه ۱ : این تابع که در شکل با رنگ قرمز نشان‌داده شده است خاصیت قابل قبول بودن (یعنی $\forall m \ f(n) \le f *(n)$) را ندارد چرا که در بعضی از قسمت‌ها از خط آبی که نشان‌دهنده مقدار واقعی $(f*(n))$ است بالاتر رفته است. 

گزینه ۲ : این تابع که با خط مشکی نمایش داده شده است نیز خاصیت قابل قبول بودن را ندارد چرا که در بعضی از قسمت‌ها از خط آبی که نشان‌دهنده مقدار واقعی یعنی $f*(n)$ است بالاتر رفته است.

گزینه ۳ : هر کدام از توابع $f_1(n)$ و $f_2(n)$ به تنهایی قابل قبول نیستند در نتیجه جمع آن‌ها نیز نمی‌تواند قابل قبول باشد (البته چون در این حالت مقدار برد توابع مثبت است توانستیم چنین نتیجه‌ای بگیریم)

گزینه ۴ : تابع این گزینه به صورت حدودی معادل خط سبز رنگ نشان داده شده در شکل زیر است. همان‌طور که مشاهده می‌کنید در تمامی حالات این خط از خط آبی که نشان‌دهنده مقدار واقعی یعنی $f*(n)$ است کمتر است در نتیجه می‌توان گفت این تابع قابل قبول است.

دشوار درخت جستجوی زیر داده شده است. گره A، وضعیت اولیه می‌باشد. وضعیت‌های جواب نیز با مربع‌های نقطه‌چین نشان شده‌اند. اعداد روی یال‌ها هزینه استفاده از آن مسیر (یال) را نشان می‌دهد. اعداد داخل هر گره نیز تخمین فاصله تا هدف را مشخص می‌کند. اگر برای جستجو از روش ${IDA}^*$ استفاده شود، میزان حد آستانه که جهت انتخاب گره‌ها، هنگام ورود به صف در نظر گرفته می‌شود پس از گرفتن مقدار اولیه، چندبار تغییر می‌کند؟ الگوریتم های جستجوی آگاهانه

1 0

2 1

3 2

4 3

گزینه 3 صحیح است.

یادآوری روش IDA* و نکات مربوط به آن :

روش IDA* روشی مشابه A* است که در جهت بهبود وضعیت مرتبه حافظه A* ارائه شده است و از ایده جستجو عمقی تکرار شونده استفاده می‎‌کند. پس مصرف حافظه این روش نسبتا خوب است و از آن‌جا که برمبنای A* و جستجو عمقی تکرار شونده است کامل نیز می‌باشد و کارایی خوبی دارد چرا که مرتبه زمانی آن مشابه A* است. در این روش درخت جستجو به صورت تکراری از ریشه تا زمانی که مقدار تمام گره ها از cutoff بیشتر شود به صورت عمقی ساخته می‎شود (به عبارتی همه گره هایی که f(n) آن‌ها از cutoff کمتر است به صورت پیش ترتیب بررسی می‌شوند). سپس در هر تکرار مقدار cutoff به کوچکترین مقدار f(n) گره های موجود در گراف بروزرسانی می‌شود تا جایی که به هدف برسیم. این روش از آن‌جا که در هر مرحله کل درخت جستجو از ابتدا می‎سازد، دوباره کاری دارد که یکی از نقطه ضعف های آن محسوب می‌شود.

در مرحله اول cutoff = 50 در نظر گرفته می‌شود و درخت زیر بدست ‌می‌آید:

در مرحله بعدی cutoff به کمترین مقدار f(n) یعنی ۶۰ تنظیم می‌شود :

 

از آنجایی که هنوز به هدف نرسیدم بازهم الگوریتم را ادامه می‌دهیم و در مرحله بعدی cutoff به کمترین مقدار f(n) یعنی ۶۱ تنظیم می‌شود و در این مرحله گره M بسط داده شده و به هدف می‌رسیم. پس به جز تنظیم اولیه cutoff به مقدار 50 ، دوبار مقدار cutoff تغییر کرد و جواب گزینه سوم می‌باشد.

متوسط در درخت تصمیم‌گیری زیر با استفاده از جستجوی $A^*$ کدام گزینه شماره گره‌های مورد بررسی را مشخص می‌کند؟ توجه کنید که هزینه هر گره در کنار شماره آن و هزینه هر شاخه روی آن نوشته شده است. (در هر گره اولین عدد شماره گره و دومین عدد هزینه می‌باشد.) الگوریتم های جستجوی آگاهانه

1 1, 2 , 3 , 4 , 5 , 6 , 12 , 13 , 14

2 1 , 2 , 3 , 7 , 8 , 9 , 19 , 20

3 1, 2 , 3 , 7 , 8 , 9 , 17 , 18 , 19 , 20

4 1 , 2 , 3 , 7 , 8 , 9 , 4 , 5 , 6 , 12 , 13 , 14

در جست‌وجوی A* اولویت جست‌وجو با گره‌ای است که مجموع هزینه کمترین مسیر طی شده تا آن گره و هزینه تخمین زده تا گره هدف برای آن کمترین باشد، این مجموع را برای گره i با $f_i$ نشان می‌دهیم. 

اگر تابع heuristic در اینجا admissible بود (فاصله تخمین زده از فاصله واقعی بیشتر نباشد.) می‌توانستیم به راحتی با پیدا کردن f گره‌هایی که مقدارشان کمتر از فاصله رسیدن تا گره بهینه است جواب را بیابیم. اما در اینجا چنین چیزی برقرار نیست (چرا؟) بنابراین چاره‌ای نداریم جزء اینکه براساس الگوریتم جلو رفته و گره‌های مشاهده شده را بدست آوریم.

 

در ابتدا گره ۱ جست‌وجو می‌شود.

$f_2=2+4.5=6.5,\ f_3=1+4=5$

 

تا الان کوچکترین ۳ است بنابراین گره ۳ جست‌وجو می‌شود. (با جست‌وجوی ۳، سه گره زیر دیده می‌شوند.)

$f_7=1+1+5=7,\ $

$f_8=1+2+4.5=7.5,$

$f_9=1+3+4=8$

 

پس از آن گره ۲ جست‌وجو می‌شود. (به مقادیر f دقت کنید همیشه کوچکترین انتخاب می‌شود.)

$f_4=2+2+4.5=8.5,$

$f_5=2+1+4=7$

$f_6=2+1+5=8$

پس از گره ۲ دو گره ۵ و ۷ بیشترین اولویت را دارند، فرض کنید ابتدا گره ۵ جست‌وجو می‌شود. با اینکار ۳ گره زیر دیده می‌شوند:

$f_{12}=2+1+1+4=8$

$f_{13}=2+1+2=5$

$f_{14}=2+1+1$

گره بعدی برای جست‌وجو دیگر ۷ نیست بلکه گره ۱۳ است که گره هدف می‌باشد و جست‌وجو به پایان می‌رسد.

کل گره‌های بررسی شده تا زمان یافتن گره هدف: (گره‌هایی که f آن‌ها حساب شد)

$1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8,\ 9,\ 12,\ 13,\ 14$

بنابراین جواب صحیح گزینه ۴ می‌باشد.

 

توجه: حال فرض کنید در بالا به جای اینکه ابتدا ۵ چک شود گره ۷ ‌جست‌وجو شود. با اینکار ۲ گره زیر دیده می‌شوند:

$f_{15}=1+1+2+4=8$

$f_{16}=1+1+2+5=9$

 

با توجه به این اعداد اولویت بعدی همان گره ۵ می‌باشد. که مشابه بالا پیش رفته و به گره هدف ۱۳ می‌رسد.

 

اگر گره ۷ زودتر از ۵ جست‌وجو می‌شد باید گزینه‌ای با مشاهدات زیر در سؤال می‌بود:

$1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8,\ 9,\ 12,\ 13,\ 14,\ 15,\ 16$

 

اما در اینجا نیست بنابراین گزینه صحیح همان گزینه ۴ است.

نمونه سوالات فصل بازی های رقابتی درس هوش مصنوعی

متوسط در جستجوی خصمانه با هرس آلفا – بتا، مقدار آلفا در حین جستجو در یک گره max برابر با 5 شده است. کدام‌یک از گزاره‌های زیر درست است؟ بازی های رقابتی

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

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

3  آلفا، پس از این، همواره کوچکتر از 5 خواهد بود.

4 آلفا، پس از این، همواره بزرگتر از 5 خواهد بود.

در کل هرس آلفا-بتا به صورت زیر رخ می‌دهد:

$\square$ -  جست‌وجو در هر یک از فرزندان گره‌های max زمانی متوقف می‌شود که مقدار آن گره کمتر از مقدار فعلی گره max که با آلفا آن را حفظ می‌کنیم شود.

$\square$ -  جست‌وجو در هر یک از فرزندان گره‌های min زمانی متوقف می‌شود که مقدار آن گره بیشتر از مقدار فعلی گره min که با بتا آن را حفظ می‌کنیم شود.

با توجه به این توضیحات مشخص است که گزینه ۱ صحیح است.

بررسی دقیق‌تر گزینه‌ها:

 

گزینه ۱:

گره‌های فرزند یک گره max، گره‌های min هستند و این گره‌ها هر گاه جوابی کمتر از مقدار آلفا (که در اینجا ۵ هست) گرفتند با ادامه جست‌وجو در آن‌ها مقدارشان بیشتر نشده و حتی ممکن است کمتر شود، بنابراین جست‌وجو در آن‌ها برای گره max فایده‌ای نداشته و بهترین کار توقف جست‌وجو در آن گره است (کاری که هرس آلفا-بتا انجام می‌دهد).

 

بنابراین این گزینه درست است.

 

گزینه ۲:

فرض کنید یکی از گره‌های min که فرزند گره max مورد نظر ما است مقداری بیشتر از ۵ گرفت و ما جست‌وجو را برای آن متوقف کردیم. حال گره max ما (اگر مقدار بیشتری نیابد) آن گره را برای هدف بعدی انتخاب می‌کند و مقدار خود را مقدار آن گره قرار می‌دهد، این در حالی است که ممکن است مقدار واقعی آن گره min (که از جست‌وجوی کامل آن بدست می‌آید.) کمتر از ۵ باشد. در آن صورت انتخاب ما غیر بهینه بوده و این خلاف بهینه بودن الگوریتم هرس آلفا-بتا است.

 

گزینه ۳ و ۴:

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

برای این دو گزینه می‌توان مثال نقض زیر را آورد: (به دو گره max که نوه‌های ریشه هستند دقت کنید اینجا ریشه ۱۰ است ولی دو نوه آن هم آلفا کوچکتر و هم بزرگتر دارند.)

 

آسان با استفاد از روش هرس $\alpha-\beta$ کدام‌یک از گره‌های درخت زیر جست‌وجو نخواهد شد؟ بازی های رقابتی

1  M , K

2 K , M , O    

3 K , G , N , O

4 E , J , K , G , N , O

در اینجا با هرس G، O و N نیز هرس می­‌شود.

دشوار فرض کنید در درخت زیر، مقادیر گره‌­های برگ متمایز هستند. احتمال اینکه گره f هرس نشود چقدر است؟ بازی های رقابتی

1  20 درصد

2 25 درصد    

3 40 درصد

4  50 درصد

در صورتی که $min(a,b)$ از $min(c,d,e)$ کوچک‌تر باشد، f هرس نمی‌­شود. یعنی اگر $min(a,b,c,d,e)$ برابر a يا b باشد، f هرس نمی‌­شود. احتمال اینکه هریک از اعداد a یا b از چهار عدد دیگر کمتر باشد ۲۰ درصد است. در نتیجه احتمال هرس نشدن f برابر ۴۰ درصد خواهد بود.

نحوه محاسبه احتمال اینکه a کوچکترین باشد (برای b نیز به همین صورت است):

۵ عدد داریم تعداد کل ترتیب‌هایی که برای دنباله مرتب شده این عدد‌ها وجود دارد برابر !5 است.

تعداد کل ترتیب‌هایی که برای دنباله مرتب شده این عدد‌ها وجود دارد که عدد a کوچکترین باشد برابر !۴ است.

بنابراین احتمال اینکه a کوچکترین باشد برابر است با:

$\frac{4!}{5!}=\frac{1}{5}=20\%$

دشوار در درخت بازی زیر کدام یک از گزینه‌ها محدوده مناسبی برای مقادیر مثبت x و y تعیین می‌کند به‌طوری که شاخه‌های علامت‌زده شده در هرس آلفا_بتا، هرس شوند؟ بازی های رقابتی

1  به ازای هیچ مقداری از x و y شاخه‌های علامت‌زده شده حذف نخواهند شد.

2 $\mathrm{\forall }\mathrm{x\ ,\ y\ \ \ \ \ \ \ \ \ \ \ }\mathrm{\circ }\mathrm{\ \lt\ x\ }\mathrm{\le }\mathrm{\ }\mathrm{3}\mathrm{\ ,\ }\mathrm{\circ }\mathrm{\ \lt\ y\ }\mathrm{\le }\mathrm{\ }\mathrm{3}$   

3 $\mathrm{\forall }\mathrm{x\ ,\ y\ \ \ \ \ \ \ }\mathrm{\ \ \ \ }\mathrm{6}\mathrm{-}\mathrm{x}\mathrm{-}\mathrm{y\ \gt\ }\mathrm{\circ }$

4  $\mathrm{\forall }\mathrm{x\ ,\ y\ \ \ \ \ \ \ \ \ \ \ x\ \lt\ }\mathrm{5}\mathrm{\ ,\ y\ \gt\ }\mathrm{7}$ 

گزینه 4 صحیح است.

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

در ابتدای کار چون نمی‌دانیم که کدامیک از مقادیر x,y بزرگتر است برای مقدار آلفا متناظر با شاخه سمت چپ max(x,y) را در نظر می‌گیریم. مقدار بتا گره پدر آن را نیز با این مقدار جایگذاری می‌کنیم. پس از آن به شاخه بعدی می‌رویم و در مرحله ابتدایی آلفا برابر با ۳ می‌شود. در اینجا شرط هرس برای هرس گره ۷ برقرار نشده است پس 3<max(x,y) بوده است. پس از بررسی شاخه ۷ مقدار آلفا پدر آن برابر با ۷ می‌شود. از طرفی چون نمی‌دانیم کدام یک از مقادیر 7 یا max(x,y) کوچک‌تر است که آن را بعنوان بتا پدرشان انتخاب کنیم از min آنها استفاده می‌کنیم. در مرحله بعد پس از بررسی گره ۱۱ شرط هرس برقرار شده است چرا که گره ۱۲ حذف شده است. پس می‌توان نتیجه گرفت که $11 \ge min (7,max(x,y))$ است. در مرحله بعدی بتا گره min همان $min(7, max(x,y))$ می‌ماند چرا که ۱۱ از ۷ کوچک‌تر است. در مرحله بعد همین مقدار را برای آلفا ریشه در نظرگرفته و به بررسی زیر شاخه سمت راست ریشه می‌پردازیم.

در سمت راست پس از بررسی زیر شاخه اول مقدار ۶ بعنوان آلفا گره max تنظیم می‌شود. در این مرحله با توجه به اینکه هر دو زیر درخت سمت راست هرس شده‌اند پس شرط هرس برقرار شده بوده است یعنی $6 \le min (7,max(x,y))$ و در کل باتوجه به بازه‌های بدست آمده باید گزینه مناسب را انتخاب کنیم.

$6 \le min(7,max(x,y)) \le 11 \\ \ \ \ \ \ \ \ \ \ max(x,y) \gt 3$

$x \ge 6 \ \text{یا }\ y \ge 6$

که با توجه به عبارت بالا فقط گزینه ۴ که $y \gt 7$ منطبق بر بازه بالا است و می‌تواند پاسخ سوال باشد.

نمونه سوالات فصل ارضای محدودیت درس هوش مصنوعی

آسان در یک مسئله می‌خواهیم نقشه را با سه رنگ (R)Red، (G)Green و Blue (B) رنگ‌آمیزی کنیم طوری که هیچ دو کشوری که با هم مرز مشترک دارند هم‌رنگ نشوند. اطلاعات نقشه را به‌صورت گراف محدودیت زیر نمایش داده‌ایم (وجود لبه بین دو گره نشانه وجود مرز مشترک بین دو کشور مربوط به گره‌هاست.) بر اساس هیوریستیک‌های عمده مسائل CSP کدام گزینه زیر ترتیب بهتری برای دو کشوری که اول انتخاب می‌شوند است؟ مسائل ارضای محدودیت

1 A-2 , C-1

2 F-2 , C-1

3 B-2 , G-1

4 F-2 , G-1

گزینه 1 صحیح است.

از جمله هیوریستیک‌هایی که برای مسائل CPS بکار می‌روند می‌توان به MRV‌ (انتخاب متغیری از بین متغیرهای بدون مقدار که کمترین دامنه مجاز را دارد) و Degree (متغیری که درجه بیشتری دارد و بیشترین محدودیت را به متغیرهای مقداردهی نشده اعمال می‌کند) اشاره کرد که MRV بر Degree الویت دارد. در گراف داده شده نیز از آن‌جایی که برای انتخاب اولین گره همه گره‌ها هر رنگی می‌توانند داشته باشند، MRV به هیچ گره‌ای الویت نمی‌دهد و پس از آن گره C با استفاده از هیوریستیک Degree انتخاب می‌شود پس از انتخاب C و انتساب یک رنگ به آن، از دامنه هر کدام از گره‌های A, B, E, D یک حالت کم می‌شود. در مرحله بعد برای انتخاب گره، MRV یکی از گره‌های A, B, E, D که حالت‌های مجاز کمتری نسبت به بقیه دارند را پیشنهاد می‌دهد که از بین این‌ گره‌ها Degree  نیز چون هر کدام از آن‌ها دو محدودیت را به متغیرهای مقداردهی نشده اعمال می‌کند یکی را به تصادف انتخاب می‌کند و پاسخ گزینه ۱ می‌شود.

دشوار در یک مسئله رنگ‌آمیزی نقشه به شکل مقابل می‌خواهیم هیچ دو کشور همسایه‌ای هم‌رنگ نباشند و کشورهای E ،D ،C ،B ،A و M به یکی از سه رنگ قرمز، سبز و آبی رنگ شوند. فرض کنید در میانه یک جستجوی ارضای محدودیت (CSP) برای این مسئله، به کشور A رنگ قرمز و به کشور C رنگ آبی را نسبت داده باشیم. حال اگر بخواهیم به کشور M رنگ قرمز را نسبت دهیم، کدام تست زیر بروز تناقض و نیاز به عقب‌گرد را پیش‌بینی می‌کند؟ مسائل ارضای محدودیت

1 forward checking

2 path consistency

3 node consistency

4 تناقضی کشف نخواهد شد.

گزینه 2 صحیح است.

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

	A	B	C	D	M	E
Initial domains	$R \ \ G\ \ B$	$R \ \ G\ \ B$	$R \ \ G\ \ B$	$R \ \ G\ \ B$	$R \ \ G\ \ B$	$R \ \ G\ \ B$
After A =red	$R$	$\ \ \ G\ \ B$	$\ \ \ G\ \ B$	$R \ \ G\ \ B$	$R \ \ G\ \ B$	$\ \ \ G\ \ B$
After C =blue	$R$	$\ \ \ G\ \ B$	$B$	$R \ \ G\ \ $	$R \ \ G\ \ B$	$\ \ \ G\ \ B$
After M =red	$R$	$\ \ \ G\ \ B$	$B$	$\ G\ \ $	$R$	$\ \ \ G\ \ B$

گزینه ۲: سازگاری مسیر به این معنی است که اگر برای دو متغیر مقدار مجاز و معتبر وجود داشته باشد برای متغیر سوم نیز حداقل یک مقدار مجاز و معتبر وجود دارد پس اگر در گراف به ازای هر سه متغیر نکته بالا برقرار باشد می‌توان گفت سازگاری مسیر داریم. در گراف محدودیت حاصل از این مسئله پس از مقداردهی به گره‎‌های A  و C  و M مطابق صورت سوال دامنه‌های هر سه متغیر B, E, D به‌صورت {B, G}  می‌‌شود که در این حالت می‌بینیم که سازگاری مسیر وجود ندارد و توانستیم با استفاده از این روش تناقض در مسئله را پیدا کنیم .(در این حالت از آن‌جایی که سه متغیر B, E, D به صورت مثلث بهم وابسته‌اند هرگونه مقداردهی به دو تا از آن‌ها باعث تهی شدن دامنه سومی و در نتیجه ناسازگاری مسیر می‌شود)

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

گزینه ۴: این گزینه نادرست است چرا‌که دیدیم با استفاده از path consistency می‌توان تناقض را یافت.

دشوار می‌خواهیم گراف زیر را با سه رنگ رنگ‌آمیزی نماییم. هیچ دو رنگ مشابهی نمی‌توانند کنار یکدیگر باشند. اگر مقدار NT = red و V = red باشد، آنگاه این ناسازگاری با کدام‌یک از روش‌های زیر قابل تشخیص است؟ مسائل ارضای محدودیت

1 Forward checking

2 Arc-consistency

3 Path-consistency

4 موارد 3 و 2

گزینه 3 صحیح است.

یادآوری :

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

Path consistency : سازگاری مسیر به این معنی است که اگر برای دو متغیر مقدار مجاز و معتبر وجود داشته باشد برای متغیر سوم نیز حداقل یک مقدار مجاز و معتبر وجود دارد پس اگر در گراف به ازای هر سه متغیر نکته بالا برقرار باشد می‌توان گفت سازگاری مسیر داریم.

Arc Consistency : همان سازگاری کمان است که در این روش با هر مقداردهی به متغیرها دامنه مقادیر همه متغیرهای بدون مقدار که دارای محدودیت با متغیر مقداردهی شده می باشند بررسی و بروزرسانی می‌شوند. در این حالت در صورتی که به دامنه تهی برای یکی از متغیرها برسیم ناسازگاری رخ می‌دهد.

در این سوال با اعمال Forward checking می‌توان به شکل بالا رسید که همان‌طور که مشاهده می‌شود دامنه‌ی هیچ متغیر تهی نشده است .

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

اما ناسازگاری مسیر در گراف داده شده برقرار نیست چرا که به ازای سه متغیر {SA, Q, NSW} برای هر دو متغیر امکان مقداردهی معتبر وجود دارد اما امکان مقداردهی برای متغیر سوم نیست و این امر باعث ناسازگاری مسیر می‌شود.

 

توجه: در سؤال اصلی کنکور، صورت سوال NT = red و V = green است که نادرست است و هیچکدام از روش‌های ذکر شده در گزینه‌ها امکان تشخیص این ناسازگاری را ندارند زیرا با این رنگ‌ها می‌توان یک ترکیب درست برای تمام متغیرها یافت، (این تست کنکور از دفترچه حذف شده است.) در اینجا (برای تمرین) فرضیات سوال را به NT = red و V = red تغییر داده‌ایم تا بتوان به حل سوال پرداخت.

دشوار مسأله ارضای محدودیت (Constraint Satisfaction) رنگ کردن نقشه زیر را درنظر بگیرید. فرض کنید می‌خواهیم این نقشه را با تنها یک رنگ، رنگ‌آمیزی کنیم (شهرهای مجاور نباید هم‌رنگ باشند). با این فرض، گراف محدودیت (Constraint Graph) این مسأله به ازای چه مقدار (مقادیر) K، دارای خاصیت K-Consistency است؟ مسائل ارضای محدودیت

1 فقط $\mathrm{K\ =\ \circ}$

2 فقط k = 1  

3 k = 1 و k = 2

4 k = 1 و k = 3

گزینه 4 صحیح است.

ابتدا به تعریف سازگاریk- می‌پردازیم. این سازگاری در واقع مشابه بسط سازگاری مسیر (path consistency) می‌باشد که برای تعداد متغیر بیشتری تعریف می‌شود. در یک مسئله ارضا محدودیت گفته می‌شود که سازگاری-k برقرار است اگر به ازای هر k-1 متغیر از cps مقدار سازگار وجود داشته باشد آنگاه حداقل یک مقدار مجاز و معتبر برای k امین متغیر cps نیز وجود داشته باشد. 

1- consistent : همان سازگاری نود است که محدودیت‌هایی یکانی را بررسی می‌کند به این معنی است که آیا بدون توجه به سایر نودها مقداری وجود دارد که به هر نود نسبت دهیم.

2- consistent : همان سازگاری کمان است که در این روش با هر مقداردهی به متغیرها دامنه مقادیر همه متغیرهای بدون مقدار که دارای محدودیت با متغیر مقداردهی شده می باشند بررسی و بروزرسانی می‌شوند. در این حالت در صورتی که به دامنه تهی برای یکی از متغیرها برسیم ناسازگاری رخ می‌دهد.

3- consistent : همان سازگاری مسیر است که بیان می‌کند اگر برای دو متغیر مقدار مجاز و معتبر وجود داشته باشد برای متغیر سوم نیز حداقل یک مقدار مجاز و معتبر وجود دارد پس اگر در گراف به ازای هر سه متغیر نکته بالا برقرار باشد می‌توان گفت سازگاری مسیر داریم.

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

برای اینکه مسئله ۱-سازگار باشد نیاز است که بدون توجه به سایر نودها مقداری وجود داشته باشد که به هر نود نسبت دهیم و با توجه به اینکه در این حالت هر کدام از متغیرها یک رنگ را در دامنه خود دارند این سازگاری برقرار است. 

برای بررسی ۲-سازگار بودن مسئله ابتدا به گره A تنها رنگ مسئله را نسبت می‌دهیم در این صورت با توجه به اینکه گره A با گره‌های ‌B و C مجاور است این رنگ از دامنه این متغیر حذف می‌شود و دامنه این متغیرها تهی می‌شوند پس این سازگاری نقض می‌شود و این مسئله ۲-سازگار نیست. 

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

(نکته : در منطق گزاره‌ای داشتیم $p \rightarrow q$ برقرار است اگر p نادرست باشد یا p درست و q هم درست باشد. در این مسئله حالت اول برقرار شده است)

متوسط در حل یک مسئله ارضای قیود با استفاده از روش جستجوی Backtracking، که در آن AC3 در هر گره اجرا می‌شود، کدام‌یک از موارد زیر درست است؟ مسائل ارضای محدودیت

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

2 در یک بار اجرای الگوریتم AC3 همه یال‌های گراف قیود حداکثر d بار پردازش می‌شود که d اندازه دامنه مقادیر متغیرها است.

3 درصورتی‌که در یک مرحله از اجرای الگوریتم، مجموعه پاسخ‌های مجاز همه متغیرها غیرتهی باشد، مسئله حتماً پاسخ دارد.

4 درصورتی‌که پس از اجرای AC3 یک مقدار مجاز از یک متغیر حذف شد، پاسخ نهایی الگوریتم جستجو، حتماً آن مقدار را به متغیر مذکور نسبت نخواهد داد.

گزینه 2 صحیح است. الگوریتم backtracking به همراه AC3 در حل مسائل CSP استفاده می‌شود. 

 

نحوه عملکرد الگوریتم:

 

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

 

بررسی گزینه‌ها:

 

گزینه ۱:

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

 

مثال: در این مثال باید رنگ‌ها را برای ۳ ناحیه جوری مشخص کنیم که رنگ هر ناحیه متفاوت باشد. دامنه رنگ‌های هر ناحیه داخل آن نوشته شده است.

اگر الگوریتم داده شده را از ناحیه سمت چپ شروع کنیم و این الگوریتم ابتدا رنگ آبی و یا سبز را برای این ناحیه در نظر بگیرد، مشخص است که با اجرای الگوریتم AC3 حتما دامنه یکی از ناحیه‌ها تهی می‌شود، ولی از روی دامنه ناحیه‌ها معلوم است که این مسئله جواب دارد.

 

 

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

 

گزینه ۲:

این گزینه درست است، زیرا هر ارتباط میان دو گره یکبار در ابتدای اجرای AC3 چک می‌شود و یکبار هم به ازای هرباری که یک مقدار از دامنه متغیر حذف می‌شود البته این در صورتی است که حذف آن مقدار دامنه متغیر را تهی نکند، بنابراین اگر یک متغیر d عضو در دامنه ابتدایی خود داشته باشد با حذف همه آن‌ها d-1 بار پردازش صورت می‌گیرد که بهمراه بار اول پردازش در مجموع d پردازش صورت می‌گیرد.

 

گزینه ۳:

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

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

 

بنابراین این گزینه نادرست است.

 

به مثال ساده زیر توجه کنید:

مثال: ۳ متغیر داریم که هر کدام دامنه‌ای از اعداد دارد، هدف انتخاب یک عدد برای هر متغیر است به گونه‌ای که جمع اعداد انتخابی کمتر از ۱۰ شود.

۳ متغیر و دامنه‌هایشان:

$A=\left\{6,\ 7\right\},\ B=\left\{2\right\},\ C=\left\{3\right\}$

 

حال اگر الگوریتم داده شده از متغیر A شروع کرده و ابتدا عدد ۶ را انتخاب کند با اجرای الگوریتم AC3 دامنه‌ها به صورت زیر می‌شوند: (زیرا AC3 تنها محدودیت را هر بار بین دو متغیر چک می‌کند و همانطور که می‌بینید شرط با چک کردن دو به دو برقرار است.)

 

$A=\left\{6\right\},\ B=\left\{2\right\},\ C=\{3\}$

 

در این مرحله پس از AC3 دامنه متغیرها همگی غیر تهی شدند ولی مشخص است که مسئله در کل جواب ندارد.

 

گزینه ۴:

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

بنابراین این گزینه نادرست است.

دشوار در مسئله CSP با چهار متغیر $\mathrm{X}_\mathrm{4}$، $\mathrm{X}_\mathrm{3}$، $\mathrm{X}_\mathrm{2}$، $\mathrm{X}_\mathrm{1}$ و گراف محدودیت (که هر لینک آن محدودیت یکسان نبودن مقدار متغیرهای دو سر آن لینک را نشان می‌دهد) مشخص شده است. دامنه‌ی متغیرها هم کنار آن‌ها نشان داده شده است. بعد از اعمال AC3 دامنه‌ی متغیرها به چه صورت درمی‌آید؟ مسائل ارضای محدودیت

1 $\begin{matrix}\begin{matrix}\mathrm{D}_{\mathrm{X}_\mathrm{1}}=\ \left\{\ \right\}\ \ \ \ \ \ \ \ \ \\\mathrm{D}_{\mathrm{X}_\mathrm{2}}=\ \left\{\mathrm{a,\ b,\ c}\right\}\\\end{matrix}\\\mathrm{D}_{\mathrm{X}_\mathrm{3}}=\ \left\{\mathrm{a,\ b,\ c}\right\}\\\mathrm{D}_{\mathrm{X}_\mathrm{4}}=\ \left\{\mathrm{a,\ b,\ c}\right\}\\\end{matrix}$

2 $\begin{matrix}\begin{matrix}\mathrm{D}_{\mathrm{X}_\mathrm{1}}=\ \left\{\mathrm{b}\right\}\ \ \ \\\mathrm{D}_{\mathrm{X}_\mathrm{2}}=\ \left\{\mathrm{a,\ c}\right\}\\\end{matrix}\\\mathrm{D}_{\mathrm{X}_\mathrm{3}}=\ \left\{\mathrm{a,\ c}\right\}\\\mathrm{D}_{\mathrm{X}_\mathrm{4}}=\ \left\{\mathrm{b}\right\}\ \ \ \\\end{matrix}$    

3 $\begin{matrix}\begin{matrix}\mathrm{D}_{\mathrm{X}_\mathrm{1}}=\ \left\{\mathrm{b}\right\}\ \ \ \ \ \ \ \ \\\mathrm{D}_{\mathrm{X}_\mathrm{2}}=\ \left\{\mathrm{a,\ c}\right\}\ \ \ \ \\\end{matrix}\\\mathrm{D}_{\mathrm{X}_\mathrm{3}}=\ \left\{\mathrm{a,\ c}\right\}\ \ \ \ \\\mathrm{D}_{\mathrm{X}_\mathrm{4}}=\ \left\{\mathrm{a,\ b,\ c}\right\}\\\end{matrix}$

4 خروجی بستگی به ترتیب گذاشتن آرک‌ها در صف دارد.

گزینه 3 صحیح است.

الگوریتم AC-3 معروف‌ترین الگوریتم سازگاری کمان است که می‌تواند در زمان پیش پردازش یا اجرا اعمال شود. روش کار این الگوریتم در حالت پیش پردازش به این صورت است که در مرحله اول همه کمان‌های مسئله در یک صف قرار می‌گیرند و سپس تا زمانی که صف خالی نشده است موارد زیر را اجرا می‌کنیم :

یک یال از صف برداشته ($x \rightarrow y$) و مقادیر دامنه x که باعث ناسازگاری کمان می‌شوند از دامنه x حذف شده و همه کمان‌هایی که به x وارد می‌شوند مجددا به صف اضافه می‌شوند.

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

در مسئله داده شده ، این الگوریتم را در حالت پیش پردازش اجرا می‌کنیم. ابتدا کمان $x_2 \rightarrow x_1$ را در نظر می‌گیریم. در این حالت فقط مقدار b از دامنه $x_2$ است که باعث ناسازگاری می‌شود پس این مقدار را از دامنه $x_2$ حذف می‌کنیم. پس از آن کمان $x_3 \rightarrow x_1$ را بررسی می‌کنیم. در این حالت نیز مشابه حالت قبلی فقط مقدار b از دامنه $x_3$ حذف می‌شود. در مرحله بعد با بررسی کمان $x_3 \rightarrow x_2$ هیچ مقدار حذف نمی‌شود چرا که به ازای هر مقداردهی به یک سر این یال مقدار معتبری برای سر دیگر این یال وجود دارد. یال‌های $x_3 \rightarrow x_4$ و $x_2 \rightarrow x_4$ نیز به همین دلیل باعث حذف هیچ مقداری از دامنه متغیرها نمی‌شوند. مقدارهای باقی‌مانده برای هر کدام از متغیرها با توجه به توضیحات بالا معادل گزینه سوم می‌باشد. 

نمونه سوالات فصل منطق گزاره ای درس هوش مصنوعی

متوسط فرض کنید در یک پایگاه دانش داشته باشیم: منطق گزاره‌ای

$\mathrm{\neg }\mathrm{C\ }\mathrm{\Rightarrow }\mathrm{\ \neg K}$

 $\mathrm{C\ }\mathrm{\Rightarrow }\mathrm{\ A\ }\mathrm{\vee }\mathrm{\ }\mathrm{B}$

$\mathrm{B\ }\mathrm{\Rightarrow }\mathrm{\ R\ }\mathrm{\vee }\mathrm{\ C}$

$\mathrm{K\ }\mathrm{\wedge }\mathrm{\ \neg M}$

 کدام‌یک از جملات زیر با استفاده از Resolution از این پایگاه قابل استنتاج نیست؟

1 $\mathrm{A\ }\mathrm{\vee }\mathrm{\ }\mathrm{R}$

2 $\mathrm{A\ }\mathrm{\vee }\mathrm{\ }\mathrm{B}$   

3 $\mathrm{A\ }\mathrm{\vee }\mathrm{\ }\mathrm{K}$

4  $True$ 

گزینه 1 صحیح است.

ابتدا جملات را به فرم CNF تبدیل می‌کنیم.

$C \vee \neg K$
$\neg C \vee A \vee B$
$\neg B \vee R \vee C$
$K$
$\neg M$

 

گزینه ۱: این گزینه از روی پایگاه دانش داده شده قابل استنتاج نیست.

گزینه ۲: درخت استنتاج عبارت متناظر با این گزینه در شکل زیر نشان داده شده است.

گزینه ۳ : از آن‌جایی که طبق پایگاه دانش K همواره درست است پس or آن با هر عبارت دیگری نیز همواره درست است.

گزینه ۴ : پایگاه دانش نتیجه می‌دهد True نیز عبارتی همواره درست است.

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

نمونه سوالات فصل عدم قطعیت درس هوش مصنوعی

آسان برای شبکه بیزین (Bayesian network) روبه‌رو، احتمال P(A, B, C, D, E) برابر کدام است؟ عدم قطعیت

1 $\mathrm{P}\left(\mathrm{C}\middle|\mathrm{A\ ,\ B}\right)\mathrm{P}\left(\mathrm{E} \middle|\mathrm{B\ ,\ C}\right)P\left(\mathrm{D} \middle|\mathrm{C}\right)$

2 $\mathrm{P}\left(\mathrm{C}\middle|\mathrm{D\ ,\ E}\right)P\left(\mathrm{B} \middle|\mathrm{C\ ,\ E}\right)\mathrm{P}\left(\mathrm{A} \middle|\mathrm{C}\right)$  

3 $\mathrm{P}\left(\mathrm{A}\right)\mathrm{P}\left(\mathrm{B}\right)\mathrm{P}\left(\mathrm{C} \middle|\mathrm{A\ ,\ B}\right)\mathrm{P}\left(\mathrm{D} \middle|\mathrm{C}\right)P\left(\mathrm{E} \middle|\mathrm{C\ ,\ B}\right)$

4 $\mathrm{P}\left(\mathrm{D}\right)\mathrm{P}\left(\mathrm{E}\right)\mathrm{P}\left(\mathrm{C} \middle|\mathrm{D\ ,\ E}\right)\mathrm{P}\left(\mathrm{B} \middle|\mathrm{C\ ,\ E}\right)P\left(\mathrm{A} \middle|\mathrm{C}\right)$

گزینه 3 صحیح است.

برای بدست آوردن توزیع توأم از روی شبکه بیزین باید از احتمال هر متغیر به شرط پدرانش استفاده کنیم. متغیرهای A و B به هیچ متغیر دیگری وابسته نیستند (پدر ندارند) پس هر کدام از آن‌ها را به صورت P(A) و P(B) در نظر می‌گیریم. برای متغیر C احتمال آن به شرط پدرانش را به صورت P(C|A,B) و برای E و D به صورت P(D|C) و P(E|B,C) در نظر گرفته و حاصلضرب این احتمال‌ها معادل با توزیع توأم متغیرها می‌شود.

$\mathrm{P(A,\ B,\ C,\ D,\ E)}\mathrm{\ =\ }\mathrm{P}\mathrm{(}\mathrm{A}\mathrm{)}\mathrm{P}\mathrm{(}\mathrm{B}\mathrm{)}\mathrm{P}\mathrm{(}\mathrm{C}\mathrm{|}\mathrm{A}~,\mathrm{B}\mathrm{)}\mathrm{P}\mathrm{(}\mathrm{D}\mathrm{|}\mathrm{C}\mathrm{)}\mathrm{P}\mathrm{(}\mathrm{E}\mathrm{|}\mathrm{C}~,\mathrm{B}\mathrm{)}$

نمونه سوالات فصل برنامه ریزی درس هوش مصنوعی

مطالب مرتبط

همه مقالات

مدیریت حافظه در سیستم عامل

تست های نظریه زبان ها و ماشین ها

تست های ریاضیات گسسته کنکور ارشد کامپیوتر

دوره نکته و تست درس سیگنال ها و سیستم ها