سه شنبه 29 خرداد 1397 | Tuesday 19 th of June 2018 صفحه اصلی گروه الکترونیکی کامپیوتر
3-10- روش های جستجوی حل مسئله

روش­های جستجو

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

روش­های تجزیه و تحلیل:

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

الگوریتم:

روش­های تحلیلی ممکن است از الگوریتم­ها برای افزایش کارایی در جستجو استفاده کنند. یک الگوریتم یک فرایند جستجوی مرحله به مرحله، برای بدست اوردن راه­حل بهینه است.

جستجوی نااگاهانه:

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

جستجوی هیوریستیک:

برای بیشتر کاربردها، امکان دارد بتوانیم قوانینی پیدا کنیم، که راهنمایی برای فرایند جستجو باشند و مقداری از محاسبات ضروری را کاهش دهند. این کار با روش­های جستجوی هیوریستیک که در این بخش توضیح    می­دهیم، امکان­پذیر است.

برنامه­ نویسی هیوریستیک:

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

هیوریستیک­ها قوانین تصمیم­گیری هستند،که اینکه چطور یک مسئله باید حل شود، را کنترل می کنند. جستجوی با هیوریستیک یک روال مرحله به مرحله (مثل الگوریتم) است که انقدر تکرار می­شود تا بتواند     راه­حل مطلوب را بیابد. این جستجو بسیار سریعتر و کم هزینه­تر از جستجوی نااگاهانه است، بعلاوه اینکه        راه­حل بدست امده می­تواند خیلی به راه­حل بهینه نزدیک باشد.  تصمیم­گیرنده­ها از هیوریستیک­ها یا قوانین به دلایل زیادی استفاده می­کنند برخی از انها نسبت به بقیه منطقی­تر هستند. مثلا تصمیم­گیرنده اگر بهترین روش را برای حل ان مسئله نشناسد و یا اینکه روش­های بهینه­سازی هنوز توسعه نیافته باشند، ممکن است از یک هیوریستیک استفاده کند. یک تصمیم­گیرنده ممکن است نتواند همه اطلاعات ضروری را بدست اورد و یا هزینه بدست اوردن اطلاعات و یا توسعه یک مدل پیچیده ممکن است خیلی زیاد باشد.
گرچه که هیوریستیک­ها در ابتدا برای حل مسائل نیمه­ساخت­یافته و غیرساخت­یافته به کار برده شدند، اما        می­توانند در مسائل ساخت­یافته پیچیده نیز برای بدست اوردن راه­حل مطلوب، بسیار سریعتر و کم هزینه­تر از الگوریتم­های بهینه­سازی، به کار روند. هیوریستیک­ها می­توانند وابسته به مقدار باشند، بنابراین می­توانند نقش مهمی را در سیستم پشتیبان تصمیم­گیری  مبتنی بر مدل، بازی کنند، به این صورت که می­توان یک هیوریستیک را در حل مسائل برنامه­نویسی عددی پیچیده به کار برد. همچنین هیوریستیک­ها می­توانند کیفی باشند، که در این صورت می­توانند نقش مهمی در بدست اوردن دانش برای سیستم­های خبره، داشته باشند.

شبیه­ سازی:

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

خصوصیات مهم  شبیه­سازی:

شبیه­سازی به طور محض، یک نوع مدل نیست. مدل­ها به طور کلی واقعیات را نمایش می­دهند. ولی        شبیه­سازی انها را تقلید می­کند. شبیه­سازی یک روش برای ازمایش­های هدایت شده است، بنابراین مقادیر خاص از متغیرهای تصمیم یا کنترل­ناپذیر را در مدل تست می­کند و تاثیر انها را در متغیرهای خروجی مشاهده می­کند. شبیه­سازی یک روش برای بدست اوردن راه­حل بهینه نیست در عوض یک مدل شبیه­سازی، خصوصیات یک سیستم خاص را در شرایط متفاوت توصیف  یا پیش­بینی می­کند. یک مرتبه مقادیر خصوصیات محاسبه شده و می­توان بهترین را از بین پیشنهادهای مختلف، انتخاب کرد. معمولا شبیه­سازی برای اینکه بتواند یک ارزیابی از همه تاثیرات اعمال معین را بدست اورد، یک ازمایش را چندین مرتبه تکرار می­کند. برای بیشتر وضعیت­ها یک شبیه­ساز کامپیوتری مناسب است. بالاخره شبیه­سازی هنگامی استفاده می­شود که مسئله پیچیده­تر از ان است که با روش­های بهینه­سازی عددی بررسی شود و پیچیدگی به این معنی است که مسئله نمی­تواند برای بهینه­سازی فرمول­بندی شود.

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

Compatability by:
آخرین به روز رسانی سایت: سه شنبه, 22 اسفند 1391 - 00:26