تکنیک های پایه ی جستجو

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


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

تکنیک های پایه جستجو.JPG

Rule 1

IF you purchase meat - P1

THEN you should server red wine - C1

با مشاهده Rule 1 و گراف بالا مشاهده می‌شود Ruleها به نوعی ارتباط بین گره‌ها در یک درخت را بیان می‌کنند. به این درخت‌ها ، درخت‌های شبکه استنتاج یا Inference network می‌گویند. پس هر کدام از یال‌ها بیانگر یک Rule می‌باشد.

جستجوی عمقی ((Depth First Search(DFS)

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

Depth first search.JPG

مزایای جستجوی عمقی

1. اگر راه‌حلی موجود باشد یافتن آن را تضمین می‌نماید.

2. سریع در مساله عمیق و جزیی می‌شود.

3. بر روی یک راه‌حل خاص تمرکز می‌کند ، سوالات مرتبطی پرسیده می‌شود.

معایب جستجوی عمقی

1. به دلیل ناآگاهی و جستجوی کورکورانه ، زمان‌بر است.

2. برای مسائل با فضاهای بزرگ نامناسب است.

3. برای مسائلی که راه‌حل‌های آنها سطحی است ، کارایی ندارد.

جستجوی سطحی ((Breadth First Search (BFS)

Breadth first search.JPG

مزایای جستجوی سطحی

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

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

معایب جستجوی سطحی

1. ناآگاهانه است ، زیرا در آن تابع تخمین H استفاده نمی‌شود.

2. زمان‌بر است.

3. برای مسائل با فضای بزرگ کاربرد ندارد.

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

جستجوی اول بهترین

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

موارد کاربرد قواعد Heuristic

1. مرتب کردن اهداف

2. مرتب سازی فرض‌ها

3. استفاده از قاعده‌ها یا Meta Rules

4. استفاده از قواعد با اولویت

5. استفاده از ضریب اطمینان (CF)

مزایای جستجوی اول بهترین

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

2. مدلسازی استنتاج انسان گونه

معایب جستجوی اول بهترین

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