الگوریتم ناآگاهانه
| پیشنهاد شده است که این مقاله با جستجوی جامع ادغام شود. (بحث) |
| این مقاله نیازمند تمیزکاری است. لطفاً تا جای امکان آنرا از نظر املا، انشا، چیدمان و درستی بهتر کنید، سپس این برچسب را بردارید. محتویات این مقاله ممکن است غیر قابل اعتماد و نادرست یا جانبدارانه باشد یا قوانین حقوق پدیدآورندگان را نقض کرده باشد. |
| این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. |
یک روش جستجو ناآگاهانه یا غیر مطلع یا کور است اگر اطلاعات اضافی در بارهٔ نودهایی که هنوز بیان و بسط داده نشده‌اند نداشته باشد تا بتواند تصمیم بگیرد که ابتدا کدام نود را بررسی نماید به عبارت دیگر روش‌های جستجویی که از مکاشفه استفاده نمی‌کنند کورند.
روش‌های جستجوی ناآگاهانه‌ای که در زیر می‌آیند عبارتند از:
جستجوی اول سطح (جستجوی سطحی) Breadth-first Searchویرایش
| پیشنهاد شده است که این مقاله با الگوریتم جستجوی اول سطح ادغام شود. (بحث) |
در این روش ابتدا node ریشه گسترش می‌یابد. اگر ریشه جواب مسئله بود الگوریتم پایان می‌پذیرد در غیر اینصورت فرزندان ریشه گسترش می‌یابند. حال به صورت سطحی در بین فرزندان ریشه بررسی می‌کنیم که آیا به جواب رسیده‌ایم یا خیر؟ اگر در این سطح به جواب نرسیم تمام گره‌هایی که توسط ریشه تولید شده‌اند خودشان گسترش می‌یابند و سطح بعدی را تشکیل می‌دهند. در هر سطح جستجو برای جواب انجام می‌گیرد تا نهایتاً به جواب برسیم.
- الگوریتم
- یک صف خالی ایجاد کن و حالت اولیه را در آن قرار بده
- اگر فهرست خالی است جواب نداریم در غیر این صورت عنصر سر صف را بخوان
- اگر عنصر خوانده شده جواب است مسیر را به عنوان جواب برگردان
- در غیر این صورت عنصر خوانده شده را از صف خارج کن و فرزندان آن را در صورت وجود
و ملاقات نشدن در انتهای صف قرار بده و به مرحله ۲ برو
- ویژگی‌ها
- اگر راه حلی وجود داشته باشد جستجوی اول سطح ضمانت می‌کند که حتماً آن را بیابد (شرط کامل بودن)
- اگر چندین راه حل وجود داشته باشد جستجوی اول سطح ضمانت می‌کند که کم
عمق‌ترین جواب را مشخص کند (بهینه بودن)
- معایب
پیچیدگی زمانی و فضایی زیادی دارد
روش جستجوی اول عمق Depth-first Searchویرایش
| پیشنهاد شده است که این مقاله با الگوریتم جستجوی عمق اول ادغام شود. (بحث) |
در این روش همیشه یکی از گره‌هایی که در پایین‌ترین عمق قرار دارد بسط داده می‌شود و این کار را آن قدر ادامه می‌دهیم تا به جواب برسیم در صورت رسیدن به بن‌بست مسیر دیگری انتخاب می‌شود (Backtracking) این استراتژی جستجو را می‌توان به وسیله صف پیاده‌سازی کرد که همیشه حالات جستجو شده جدید در جلوی صف قرار می‌گیرد.
- الگوریتم
- صف خالی ایجاد کن و نود اولیه را در آن قرار بده.
- اگر صف خالی است مسئله جواب ندارد در غیر این صورت عنصر سر صف را بخوان.
- اگر عنصر خوانده شده جواب است مسیر را به عنوان جواب برگردان.
- در غیر این صورت عنصر سر صف را خارج کن (ازpop stack کن) و فرزندان آن را در
صورت رویت نشدن به ابتدای صف اضافه کن (Push) و به مرحله ۲ برو.
- ویژگی‌ها
- نیاز به حافظه کمی دارد چرا که نیاز به ذخیره مسیر واحدی از ریشه به یک گره برگی دارد به علاوه برخی گره‌های بست داده نشده. جستجوی عمقی چون فضای کمی را به دنبال جواب می‌گردد پس شانس خوبی برای یافتن جواب دارد برای مسائلی که راه حل زیادی دارد جستجوی اول عمق سریع تر از جستجوی اول سطح عمل می‌کند. جستجوی اول عمق ممکن است، هنگام پایین رفتن در یک مسیر اشتباه گیر کند این مسئله در مسائل عمیق و نامحدود بیشتر بروز می‌کند و ممکن است هیچ‌گاه الگوریتم به جواب نرسد یا راه حلی را که پیدا می‌کند طولانی‌تر از راه حل بهینه باشد. پس جستجوی اول عمق نه کامل
است و نه بهینه.
- اگر نرخ شاخه شدن b بوده و M عمق جواب باشد٬داریم:
مقدار مصرف حافظه: (S(b.M
پیچیدگی زمانی در بدترین حالت: b به توان M
جستجو با هزینهٔ یکسان uniform cost searchویرایش
| پیشنهاد شده است که این مقاله با جستجو با هزینه یکسان ادغام شود. (بحث) |
جستجوی با هزینهٔ یکسان را از آن جهت که در هر لحظه کم هزینه‌ترین گره را گسترش می‌دهد، نه می‌توان در رده روش‌های جستجوی عمقی دانست، نه می‌توان آن را یک روش جستجوی سطحی تلقی کرد. در این روش جستجو هر گره هزینه مصرف شده از ریشه تا گره فعلی را در خود نگه می‌دارد. هنگامی که می‌خواهیم فرزندان گره گسترش نیافته‌ای را تولید کنیم، گرهی از درخت برای گسترش انتخاب می‌شود که کم هزینه‌ترین گره در میان گره‌های گسترش نیافته باشد.
- الگوریتم
- یک صف خالی اولویت دار ایجاد کن و حالت اولیه را در آن قرار بده.
- اگر فهرست خالی است جواب نداریم در غیر این صورت عنصر سر صف را بخوان.
- اگر عنصر خوانده شده جواب است مسیر را به عنوان جواب برگردان.
- در غیر این صورت عنصر خوانده شده را از صف خارج کن و فرزندان آن را در صورت وجود و ملاقات نشدن براساس اولویت در صف قرار بده. در این روش اگر به جواب برسیم اولین جواب ارزانترین جواب است.
- ویژگی‌ها
- زمانی که شرایط عمومی برقرار باشد اولین راه حل پاسخ ضمانت می‌کند که ارزانترین راه می‌باشد. اگر بعضی از عملگرها هزینه منفی داشته باشند باید جستجویی از تمام گره‌ها صورت گیرد، تا راه حل بهینه پیدا شود (در صورتی این راه حل بهینه است که هزینهٔ منفی نداشته باشیم).
- پیچیدگی زمانی و فضا مانند جستجوی اول سطح است.
روش جستجوی عمقی محدود شده Depth-Limited Searchویرایش
| پیشنهاد شده است که این مقاله با الگوریتم جستجوی عمق محدودشده ادغام شود. (بحث) |
مهمترین مشکل روش جستجوی عمقی را که در برخی از مسائل با آن مواجه خواهیم بود، قرار گرفتن این روش جستجو در حلقه بینهایت می‌باشد که این روش از به دام افتادن جستجوی عمقی توسط به‌کارگیری یک برش روی عمیق‌ترین مسیر جلوگیری می‌کند یعنی جستجو را از یک حداکثر عمق بیشتر ادامه نمی‌دهیم و مقدار آن توسط طراح مشخص می‌گردد. این الگوریتم زمانی مناسب است که ما حدود فاصله اولیه از جواب را می‌دانیم و تعداد جواب برای مسئله وجود داشته باشد.
- الگوریتم
- یک صف خالی ایجاد کند و حالت اولیه را در آن قرار بده.
- اگر صف خالی است مسئله جواب ندارد وگرنه عنصر سر صف را بخوان.
- اگر عنصر خوانده شده جواب است مسیر را به عنوان جواب اعلام کن.
- عنصر خوانده شده را از صف خارج کن.
- اگر عمق عنصر خوانده شده کوچکتر از L است به مرحله ۶ برو و در غیر این صورت به مرحله ۲ برو.
- فرزندان عنصر خوانده شده را در جلوی صف قرار بده (در stack) و به مرحله ۲ برو.
- ویژگی
جستجوی عمقی محدود شده به شرطی که عمق انتخابی خیلی کوچک نباشد کامل است اما بهینه نیست پیچیدگی زمانی و پیچیدگی فضا مانند روش اول عمق است.
جستجوی عمیق کننده تکراری Iterative-deepening searchویرایش
| پیشنهاد شده است که این مقاله با جستجوی عمق اول عمیقکننده تکراری ادغام شود. (بحث) |
این جستجو از مزایای هر دو روش اول سطح و اول عمق استفاده می‌نماید. این روش برای رفع مشکل انتخاب مقدار عمق مناسب در روش قبلی به وجود آمده‌است در این روش محدوده عمقی مناسب توسط امتحان نمودن تمامی محدوده عمق‌ها به دست می‌آید ابتدا عمق صفر سپس عمق یک و الی آخر. در هر عمق، به روش اول عمل عمق جستجو را انجام می‌دهیم اگر به جواب نرسیدیم آنگاه عمق را افزایش داده و از اول جستجو را به روش اول عمق ادامه می‌دهیم.
- ویژگی‌ها
- این روش مزایای جستجوی عمقی و سطحی را با هم ترکیب می‌کند.
- این روش هم کامل است و هم بهینه
- از نظر حافظه مصرفی همانند جستجوی اول عمق بوده و برابر S(b.d) است.
- در این روش چون در هر مرتبه مجدد از ریشه شروع م یکنیم و دوباره تمام درخت را بسط می‌دهیم پس گره‌هایی که در پایین‌ترین سطح هستند یک بار بسط داده می‌شوند آن‌هایی که در یک سطح بالاترند دو بار بسط داده می‌شوند و گره ریشه d+1 بار بسط داده می‌شود.
- پیچیدگی زمانی این جستجو برابر است با (b به توان M) O که نشان می‌دهد زمان بیشتری نسبت به روش‌های قبل تلف می‌شود.
- در حالت کلی زمانی این الگوریتم مفید است که فضای جستجوی بزرگی وجود داشته باشد و عمق راه نیز مجهول باشد. این روش در چنین شرایطی نسبت به روش‌های قبل برتری دارد.
جستجوی دو طرفهویرایش
| پیشنهاد شده است که این مقاله با جستجوی دوجهته ادغام شود. (بحث) |
ایده این روش، جستجوی هم‌زمان از حالت شروع به هدف یا به سمت جلو و از حالت نهایی به سمت عقب می‌باشد و وقتی به یک حالت مشترک رسیدیم این مسیر جواب خواهد بود
- ویژگی‌ها
- اگر فاکتور انشعاب در دو طرف b باشد وراه حلی در عمق b وجود داشته باشد این راه حل با زمان اجرای (b به توان d/2) o پیدا خواهد شد زیرا در هر دو جهت نیمی از راه را می‌پیماید
- پیچیدگی فضای این روش جستجو نیز (b به توان d/2)است.
- معایب
این الگوریتم برای مواقعی که چندین هدف داریم یا هدف تعریف مشخصی ندارد مانند بازی شطرنج جواب نمی‌دهد.
منابعویرایش
- کتاب هوش مصنوعی، نوشتهٔ بن کوپین، مترجم: میرزایی و داورپناه