تحقیقی که در رابطه با حل مسئله با استفاده از جستجو و ارتباط ان با درس پشتیبانی تصمیم گیر رو که انجام دادم در مطلب زیر گذاشتم:
فهرست مطالب
عنوان صفحه
فصل سوم : حل مسئله از طریق جستجو
مقدمه........................................................................... 5
عامل های حل مسئله.......................................................... 7
انواع مسئله .....................................................................9
فرموله کردن مسئله............................................11
اندازه گیری کارایی حل مسئله...............................................15
استراتژی جستجوی ناآگاهانه ..............................................18
جستجوی آگاهانه هیورستیک ...............................................23
منابع و ماخذ :
فهرست منابع غیر فارسی ..........................................
1. Artificial Intelligence - Introduction : AI Course Lecture 1- 6, notes, slides www.myreaders.info/ HYPERLINK "http://www.myreaders.info/" , RC Chakraborty, e-mail rcchak@gmail.com HYPERLINK "mailto:rcchak@gmail.com" , June 01, 2010 www.myreaders.info/html/artificial_intelligence.html
2. Artificial Intelligence, Problem Solving and Search, of Russell & Norvig.
3. Introduction to Arti_cial Intelligence, Problem Solving and Search, Bernhard Beckert, UNIVERSITÄT KOBLENZ-LANDAU
4. Artificial Intelligence, Authors : David Poole,Alan Mackworth
مقدمه
در فصل مربوط به عامل های هوشمند در کتاب هوش مصنوعی ، مفصل به انواع عامل ها پرداخته شده است و همانطور که می دانیم ، ساده ترین عاملها از نوع واکنشی می باشند که به ازای یک مسیر مشخص و از قبل تعیین شده و همچنین به ازای یک فعالیت مشخص داده شده عمل می
کنند.
در این میان یکسری عاملها به نام عاملهای سودمند می باشند که به راحتی نمی توانند عملکرد داشته باشند و مانند عاملهای ساده فعالیت و مسیر راه مشخص و واضح نمی باشد. برای فعالیت این نوع عاملها نیاز به درک و پیداکردن نقشه و مسیر و کسب دانش می باشد.
به طور کلی هدف و ماهیت اصلی این عاملها این است که ویژگی هایی داشته باشند که به وسیله آن ، به بهترین شرایط مطلوب دست بیابند.
حل مسئله از طریق جستجو
در این فصل قصد بر این است که یکی از انواع عاملها به نام عاملهای مبتنی بر هدف ، توصیف گردد. این نوع از عامل به نمایندگی از کلیه عامل ها انتخاب شده است ، زیرا تمامی شرایط و ویژگیها ی پیچیده عاملها را تحت پوشش قرار می دهد.
یعنی علاوه موارد ساخت یافته و مشخص و قابل مشاهده، با استفاده از الگوریتم های حل مسئله کلیه موارد را تحت پوشش قرار می دهد.
در این بخش قصد بر این است که مبحث حل مسئله را با توضیحات دقیق ، همراه با عناصر تشکیل دهنده و مرتبط با آن را شرح بدهیم . که در خروجی شامل مسئله و راه حل می باشد.
در این رابطه مثالهای متعدد و در طی آن الگوریتم های زیادی جهت جستجو که در نهایت منجر به حل مسدله شود ، مطرح می گردد. تا بتوان از طریق آنها انواع مسائل گوناگون را حل نمود.
در ادامه بحث به الگوریتم های از نوع ناآگاهانه می پردازیم . که در این الگوریتم ها هیچ گونه اطلاعاتی در مورد مسئله نداریم.
اگر با استفاده از یکسری از الگوریتم های ناآگاهانه می توان یکسری از مسائل را حل نمود ولی به طور کلی باید گفت که همیشه جوابگو مسائل نبوده و خیلی نمی توانند به نتیجه مطلوب رسیده و موثر عمل نمایند.
اما در مقایسه یکسری الگوریتم ها از نوع آگاهانه می باشند که با پیاده سازی آنها به خوبی می توان راه حل ارائه نمود و مسائل را حل کرد.
عامل های حل مسئله
هدف از عملکرد این نوع از عامل ها این است که کارایی و بازدهی را افزایش دهند. با توجه به مطالبی که در مبحث عاملهای هوشمند وجود دارد ، این دسته از عامل ها را این طور می توان معرفی نمود که با مشخص نمودن هدف و حرکت در جهت رسیدن به آن مانند شلیک به هدف حرکت و عمل می کنند.
در ابتدا باید در رابطه با چرا و چگونگی عمل یک عامل بحث نماییم.
جهت روشنتر شدن موضوع ، این بحث را با ارائه مثالی توضیح می دهیم.
مثال گذراندن ایام تعطیلات در رومانی
در این مثال عامل قصد دارد در مورد چگونگی طی مسیر و رسیدن به مقصد ، که با یکسری پیچیدگی جهت این مسئله است ،
اطلاعات و دانش کسب کنئ و منجر به تصمیم گیری درست شود.
در این حالت فرض ما بر این است که عامل یک بلیط غیر قابل بازگشت هوایی است و در طی روز به صورت متوالی توزیع و به فروش می رسد.
جهت درک بیشتر مسئله ، نیاز است که با مفاهیم و فرضهای زیر آشنا بشویم :
در حالت کلی حل مسئله بر 2 نوع می باشد :
1. Offline
2. Online
Offline
در این حالت ، کلیه عملیات و کارهای لازم جهت حل مسئله بیشتر از طریق کامل کردن دانش و اطلاعات در زمینه مسئله مطرح شده انجام می پذیرد.
Online
در این نوع از حل مسئله ، ما هیچ دانش و اطلاعاتی در رابطه با مسئله مطرح شده نداریم .
مثال گفته شده (مسافرت در رومانی ) در بالا را از طریق روش Offline تشریح می کنیم .
سناریو : گذراندن ایام تعطیلات در رومانی .
در حال حاضر در شهر آراد هستیم و قصد داریم به سمت بخارست ، فردا پرواز کنیم.
هدف : رسیدن به بخارست
فرمول مسئله ، شامل آیتم های زیر می باشد :
1. وضعیت ها : شامل شهرهای مختلف می باشد.
2. فعالیت ها : که همان عمل حرکت بین شهرها است.
راه حل : گذر کردن به صورت متوالی شهرهایی از قبیل : آراد ، سیبیو ، فگارس و در نهایت بخارست که هدف و مقصد می باشد.
انواع مسئله
1. مسئله با وضعیت تکی (مفرد)
2. مسئله با وضعیت چندتایی
3. مسئله تصادفی ( احتمالی )
مسئله با وضعیت تکی (مفرد)
شامل آیتم و ویژگی های زیر می باشد:
a. قابل مشاهده ( حداقل وضعیت اولیه یا فرض )
b. قطعی
c. ایستا
d. گسسته
مسئله با وضعیت چندتایی ( دسته جمعی )
a. تا حدی قابل مشاهده ( با فرض و و ضعیت اولیه غیر قابل مشتاهده )
b. قطعی
c. ایستا
d. گسسته
مسئله تصادفی ( احتمالی )
a. تا حدی قابل مشاهده ( با فرض و وضعیت اولیه غیر قابل مشاهده )
b. غیر قطعی
مثال : مکنده – جارو برقی
برای حالت مسئله با وضعیت تکی :
a. شروع در مرحله 5
b. راه حل : ] سمت راست ، مکش [
برای حالت مسئله با وضعیت چند تایی :
a. شروع در مرحله : { 1، 2، 3، 4، 5، 6، 7، 8}
b. راه حل : ] سمت راست ، مکش ، سمت چپ ، مکش [
راست {2، 4 ، 6،8}
مکش { 4 ، 8}
چپ {3، 7 }
مکش {7}
برای حالت حل مسئله با وضعیت تصادفی ( احتمالی )
a. طبق قانون مورفی مکش می تواند یک فرش تمیز را کثیف کند.
b. سنسور مکانی : کثیف بودن و یا تنها در محل غیر کثیف بودن
c. شروع در مرحله : {1، 3}
d. راه حل : ] مکش ، راست ، مکش [
مکش { 7 ، 5}
راست { 6،8}
مکش { 8 ، 6}
بهبود ( بهینه سازی ) : ] اگر کثیف بود ، راست ، مکش[
فرموله کردن مسئله – وضعیت تکی
جهت فرموله کردن یک مسئله نیاز می باشد که با یکسری آیتم ها روبو شویم.
فرموله کردن مسئله را مثال مربوط به مسافرت در رومانی را در این قسمت پیاده سازی و نشان می دهیم:
1. حالت یا فرض اولیه
مثال آراد
2. مشخص کردن تابع Successor (فعالیت ) :
مثال :
S(arad ) = {< go city0, city0> ,<go city1, city1> , <go city2 , city2> }
S / N = { 1, s(1), s(s(1)),… } مجموعه اعداد طبیعی
S(x) = X + 1
S(0) = 1
3. سنجش آزمون ( هدف )
X= تست آشکار - بخارست
Not Dirt(X) - تست مجازی (نا آشکار)
4. هزینه مسیر ( اختیاری )
مثال : سرجمع ( مجموع ) فاصله و گامهای طی شده و یا در واقع فعالیت های اجرا شده و غیره را شامل می شود.
راه حل
بعد از مشخص شدن اجزای یک مسئله ( 4 مورد ذکر شده )، نوبت به راه حل جهت حل کردن مسئله می رسد.
در واقع این مرحله شامل طی کردن به صورت ترتیبی و متوالی از فعالیت ها می باشد . که از حالت اولیه شروع شده و به حالت هدف منتهی می شود.
انتخاب فضای حالت
به صورت انتزاعی ( مجزا)
در ئنیای واقعی با یکسری از مسائل روبرو هستیم که پیچیده تر از مورد هایی است که به صورت مثال ذکر می گردد و در این شرایط نیاز است که یک فضای حالت انتزاعی را در نظر بگیریم .
فضا انتزاعی
در واقع در نظر گرفتن حالت های واقعی را شامل می شود.
عملگر انتزاعی
شامل ترکیبی از پیچیده ترین عملیات واقعی می باشد.
به طور مثال ، در مورد ذکر شده مسافرت ، رفتن از آراد به زریند :
شامل مجموعه ای پیچیده از مسیرهای امکان پذیر می باشد که بایستی مشخص گردد .( برای رسیدن به هدف که همان زریند می باشد.)
راه حل انتزاعی
شامل مجموعه ای از مسیرهای واقعی می باشد که در دنیای واقعی وجود دارد.
مثال 8 – پازل :
در این مثال در ابتدا اجزای اصلی مسئله را مشخص می کنیم.
1. حالتها : مکان یا فضاهایی برای قرار گرفتن اعداد صحیح در یک فضای مشخص
2. فعالیتها (Actions (: در واقع شامل مجموعه ای از حالات ممکن ، براساس وضعیت پیش آمده می باشد.
که می تواند بالا ، پایین ، چپ و راست باشد.
3. آزمون هدف : بررسی اینکه آیا حالت یا مکان فعلی هدف است یا خیر؟
4. هزینه مسیر : در نظر گرفتن مقدار 1 به ازای هر گام یا حرکت
که مسئله مربوطه شامل تعداد حالات زیر جهت حل مسئله می باشد:
9!/2=181, 440
که به تعداد حالات مربوطه ، حالت قابل دسترس و امکان پذیر وجود دارد که به ازای یکی از این حالات مسئله قابل حل خواهد بود.
در واقع می توان گفت مثال 8- پازل ، نمونه مشهوری که تقریبا در پیاده سازی کلیه الگوریتم های جستجو کاربرد دارد.
مثال رنگ آمیزی نقشه
صورت مسئله : یک نقشه وجود دارد که شامل تعدادی نقاط و ناحیه های رنگی می باشد . مسئله این است که به ازای هر محدوده مشخص شده ، رنگ متناظر به خودش مرا اختصاص بدهیم .
و انتظار ما این است که که دقیقا در هر ناحیه یا برش از نقشه ، رنگ مخصوص خودش را اختصاص دهیم .
راه حل :
جهت مدل کردن مسئله مربوط به رنگ آمیزی نقشه
a. به هربخش یا برش متفاوت که با مرز از هم جدا می شوند ، برچسب متناظر و متفاوت با سایر محدوده ها را می زنیم.
(قرار گرفتن رنگ متناظر در هر حوزه)
b. مشخص کردن محدوده و مرز بین هر 2 برچسب متفاوت کنار هم .
c. در نظر گرفتن کل نقشه با 4 رنگ
d. در نظر گرفتن قاعده استفاده از 4 رنگ ، که این 4 رنگ برای رنگی کردن و رنگ شدن کل نقشه کافی می باشد..
به این ترتیب که بین هر مرز مشترک بین 2 بخش مجاور ، از رنگ متفاوت استفاده گردد.
اندازه گیری کارایی حل مسئله
قبل از صحبت در رابطه با طراحی الگوریتم های جستجو ، نیاز داریم که در مورد معیار هایی که در بحث طراحی الگوریتم مطرح است صحبت کنیم. و در این زمینه اطلاعاتی رو کسب نماییم.
به طور کلی ، 4 مورد زیر در اندازه گیری کارایی یک الگوریتم به ما کمک می کنند :
1. کامل بودن
این مورد در واقع پاسخ به این سوال است ، که آیا تضمین جهت انجام کامل پروژه و حل مسئله ( که منجر به حل مسئله می شود ) وجود دارد یا خیر ؟
2. بهینه بودن
این مورد در واقع پاسخ به این سوال است ، که آیا برای حل این مسئله از راه حل بهینه استفاده شده است یا خیر ؟
3. پیچیدگی زمانی
مدت زمان حل مسئله چقدر است؟
4. پیچیدگی فضا
برای جسجوی جهت رسیدن به هدف ، چقدر فضا ( حافظه ) مورد نیاز می باشد.
پیچیدگی زمانی و پیچیدگی از نوع فضا ، همیشه به عنوان معیار هایی هستند که نیاز داریم در حل مسائل متفاوت و متنوع آن را لحاظ کنیم .
در علم کامپیوتر میزان اندازه فضای حالت گراف برابر است با :
V + E
که در واقع V ، نودهای گراف می باشد و E به عنوان یالهای گراف در نظر گرفته می شود.
ما زمانی از گراف استفاده می کنیم که ورودی های مسئله و ساختار آن مشخص و واضح باشد . مانند نقشه رومانی که فرض و هدف و مسیر مشخص بود.
به طور کلی گرافها در فضای حالت شامل یکسری فعالیت ها و نقل و انتقالها می باشند که ، در بحث گراف 3 مفهوم و مورد زیر وجود دارد:
1. B : فاکتور انشعاب نام دارد و ماکزیموم و بیشینه تعداد کمان عبوری از یک نود می باشد که از طریق آنها به نودهای دیگر اشاره می شود.(حدکثر تعداد یال های عبوری از یک نود )
2. D: عمق سطحی ترین نود هدف می باشد.( در واقع شامل تعداد گامهایی است که در طول مسیر از ریشه به سمت اولین هدف طی می شود.)
3. M: ماکزیموم طول مسیر طی شده در فضای حالت می باشد.
استراتژی
جستجوی ناآگاهانه
در صورتی که مسئله طوری باشد که گراف و هدف مربوطه مشخص است . ولی مسیر انتخاب شده برای رسیدن به هدف مشخص نشده است ، این روش از استراژی کاربرد پیدا می کند که به استراتژی جستجوی آگاهانه می گوییم.
وظیفه این روش از جستجو این است که مسیر طی شده از گره آغازین تا هدف را مشخص نماید.
استراتزی های مختلفی جهت چگونه به دست آوردن مسیر طی شده از گره شروع تا هدف وجود دارد . که در این قسمت 6 استراتژی الگوریتم جستجو از نوع آگاهانه معرفی می گردد.
به طور کلی در این نوع از الگوریتم ها ، جستجو تا زمانی ادامه دارد که به هدف برسیم و گزارش موفقیت صادر گردد.
1. جستجوی سطح اول (Breadth-first search)
2. جستجو با هزینه یکسان (Uniform-cost search)
3. جستجوی عمق اول (Depth-first search)
4. جسجو با عمق محدود شده (Depth-limited search)
5. جستجو عمیق کننده تکراری (Iterative deepening depth-first search)
6. جستجوی دو طرفه (Bidirectional search)
مقایسه یا سنجش برتری الگوریتم ها
الگوریتم های شامل الگوریتم جستجو، می توانند براساس معیارهای نام برده در زیر مقایسه گردند:
1. زمان طی شده
2. فضای حافظه استفاده شده
3. کیفیت و دقت و صحت سنجی نتایج به دست آمده ( بهینگی)
جستجوی عمق اول
در این روش از جستجو ، در حاشیه و یا ریشه مانند Last – in –first- out در پشته عمل می کند و در یک زمان عناصر به پشته اضافه می شوند و در هر زمان آخرین عنصری که به لیست اضافه شده است ، انتخاب می گردد.
در صورتی که انتخاب شده هدف باشد ، جسجو پایان یافته و در غیر این صورت طبق همین روال در حاشیه برای گسترش ، نود ها انتخاب می شوند.
ویژگی های جستجوی عمق اول
1. کامل بودن : نمی باشد ، در صورتی که دچار درخت با عمق بی نهایت شود و در حالی که هدف در شاخه دیگری باشد.
2. پیچیدگی زمانی: از مرتبه o (B ^m) می باشد.
3. پیچیدگی فضا : از مرتبه O(b ^M) می باشد.
4. بهینگی : بهینه نمی باشد.
جستجوی سطح اول
این روش شامل پیمایش سطحی ترین گره انتخاب شده می باشد.
پیاده سازی: به صورت صف FIFO انجام می گردد تا در نهایت به هدف دست یابد.
ویژگی های جستجوی سطح اول
1. کامل بودن :
بله در صورتی که فاکتور انشعاب محدود و میزان مشخصی داشته باشد.
2. پیچیدگی زمانی :
=B1+b+b^2+b^3+…+b^d = (b^d-1) = o(b^d+1)
3. بهینه بودن :
بله در صورتی که هزینه هر گام 1 باشد. ولی به طور کلی بهینه نمی باشد.
4. پیچیدگی فضا : زیاد است.
O(b^d)
جستجوی هزینه یکسان
توسعه و پیمایش هر گره بر مبنای کم هزینه ترین نود می باتشد.
پیاده سازی: به ترتیب صف وارد شده پیمایش می شود با این شرط که در مسیر طی شده ،هزینه مسیر را نیز در نظر می گیرد.
در صورتی که هزینه تمامی مراتحل با هم برابر باشد ، مانند جستجوی بهتر اول عمل می کند.
ویژگی های جستجوی هزینه یکسان
1. کامل بودن :
بله در صورتی که هزینه مسیر بیش از اپسیلون باشد.
2. زمانی :
3. در صورتی که g ( هطینه هر مسیر از گره شروع تا گره موجود ) کوچکتر از هزینه بهینه در نظر گرفته شده باشد.
O(b ^ [c*/€]
که C* هزینه راه حل بهینه می باشد.
4. بهینگی :
بله
، در صورتی که نودهای پیمایش شده افزایش یابند به طوری که کاهش تابع G(n) را به همراه داشته باشد.
g(SUccessor(n)) > g (n)
جستجوی عمیق کننده تکراری
در واقع همان روش جستجوی عمق اول می باشد ، با این شرط که عمق محدود شده است . در این روش جستجو با افزایش عمق جستجو ادامه می یابد.
1. کامل بودن
بله مانند جستجوی بهتر اول می باشد.
2. بهینگی:
بله مانند جستجوی بهتر اول می باشد.
3. پیچیدگی فضا :
O(bd)
4. زمانی :
O(b)^d
به طور کلی این روش از جستجو زمانی که فضای زیادی برای جستجو نیاز باشد و یا اینکه اطلاعی از عمق قرار گرفته هدف نداشته باشیم ، کاربرد دارد.
N(IDS) = 50 + 400 + 3, 000 + 20, 000 + 100, 000 = 123, 450
N(BFS) = 10 + 100 + 1, 000 + 10, 000 + 100, 000 + 999, 990 = 1, 111, 100
جستجوی دو طرفه
در این روش از جستجو ، جسجو از 2 سمت می باشد. به این ترتیب که یک جستجو از گره اغازین (حالت اولیه ) شروع می شود و جستجوی دیگر از سمت گره هدف به سمت گره آغازین می باشد.
در صورتی که هنگام جسجو از 2 سمت به یک گره مشترک برسند ، مسیر طی شده به عنوان مسیر بهینه در نظر گرفته می شود.
جستجوی آگاهانه هیورستیک
در این روش از جستجو ، برخلاف جستجوی ناآگاهانه ما اظلاعاتی در مورد مسئله ئاریم که به مراتب این اطلاعات خیلی بیشتر از روش ناآگاهانه می باشد.
در این روش در هر مرحله از جستجو جهت گسترش ، گره ای در حاشیه انتخاب می شود که بیشترین امتیاز یا در واقع ارزش را داشته باشد.
انواع روشهای جستجوی آگاهانه
1. جستجوی بهتر اول حریصانه
2. A*
3. جستجوی هیورستیک با فضای محدود شده (MA*)
جستجوی بهتر اول حریصانه
در این روش از جستجو شامل یک درخت می باشد که همان گراف است. با این تفاوت که در این روش از آنجا که آگاهانه است ، شامل یک تابع ارزیابی می باشد .
در این روش از جستجو می توان با براورد کردن هزینه ، گره با کمترین هزینه را انتخاب نمود.
در صورتی که هزینه تمام گامها و در واقع نود ها یکی باشند ، مانند جسجو با هزینه یکسان عمل می کند.
به طور کلی می توان گفت که تابع ارزیابی F مشخص کننده روش جستجو می باشد .
مانند حالات و شرایطی که از جستجوهای ناآگاهانه مانند Bfs و dfsو .. استفاده می کنیم.
الگوریتم جستجو در این روش شامل تابع هیورستیک می باشد که به صورت زیر نشان داده می شود:
h(n) : هزینه تخمینی از گره آغازین به گره هدف می باشد.
به عنوان مثال ، در مثال رومانی که قبلا ذکر گردید، یک مسیر مستقیم از آراد به بخارست ، تخمین هزینه کن و ارزان می باشد.
در صورتی که گره n همان گره هدف باشد ، h(n) = 0 می باشد.
جستجوی اگاهانه A* ( کم کردن هزینه تخمین زده شده)
این روش در واقع همان روش جستجو بهتر اول می باشد و علاوه بر ویژگی جستجوی بهتر اول شامل تابع G(n) نیز می باشد.
f(n) = g(n) + h(n)
h(n) : هزینه تخمینی مسیر از گره n به گره پایانی یا هدف می باشد.
g(n): هزینه مسیر طی شده از گره اغازین تا گره فعلی است.
در واقع این الگوریتم جستجو همان جستجوی ناآگاهانه با هزینه یکسان می باشد . با این تفاوت که به جز تابع h(n) ، در روش A* تابع G(n) را نیز داریم.
اگر h(n) برابر 0 باشد ، جستجو هزینه یکسان با a* برابر است.
از لحاظ معیار بهینگی بایستی گفته که ، روش A* بهینه می باشد.
به طور کلی در روشهای اگاهانه ، فضای حالت می تواند به صورت درخت جستجو و یا به شکل گراف باشد.
نوع بهینگی روش a* به نوع فضای حالت در نظر گرفته شده بستگی دارد :
1. اگر جسجو درختی باشد :تابع h(n) قابل قبول است.
2. اگر جستجو گراف باشد: تابع h(n) سازگار و پایدار است.
هرچه ما بتوانیم در جستجوی آگاهانه ، تخمینهای بیشتری از نقاط داشته باشیم، بهینگی جستجوی ما از ارزش بیشتری برخوردار خواهد بود و تخمین هزینه ما به واقعیت نزدیکتر می شود، تا سریعتر و با هزینه کمتر به هدف دست یابیم.
همانطور که گفتیم ، تابع h(n) شامل هزینه تخمین زده شده برای رسیدن گره n به گره هدف می باشد . حال در صورتی که نقطه ای علاوه بر n یافت شود که قبل از گره هدف قرار گرفته است و تا قسمتی از مسیر هزینه آن را نیز ( n’ تا هدف ) داشته باشیم ، به طبع تخمین هزینه نزدیکتر به هزینه واقعی را خواهیم زد.
f(n) = g(n) + h(n)
h(n’) = C(n,a,n’)
که در واقع a ، هزینه پیمایش از گره n به گره n’ می باشد.