تقليل مسئله

صفحه 1:


صفحه 2:
فصل تقلیل مسئله: ری ‎AND-OR‏ ‏تقلیل مسئله ‎(Problew Reduction)‏ نوع خاصي از حل مسئله است که در لین روش سعي مي شود مسئله اصلي را با استفاده از مسائل دیگر حل کنند و نهایتا تمام مسائل را با استفاده از مسائلي که بلافاصله قابل حل هستند . حل کنند ؟ این تجزیه ‎L‏ تقلیل منجر به ایجاد شاخه هایی خواهد شد که به آنها به عنوان مثال : 

صفحه 3:
فصل تقلیل مسئله: کراف :۸۷-01 .پرستسه براي حل مسئله باید پارامترهاي زیر مشخص شوند: > مسئله اصلي: صورت مسئله >عملكر: توليد مسائل ديكر را از مسئله اصلي امكان يذير مي سازد > مسائل ابتدايي: مسائلي كه توسط عملكر ها قابل تجزيه نباشند و قابل حل باشند * هزینه مسیر: هزینه ثابت براي هر مرهله مثال: مسئله اصلي مرتب سازي یک آرایه 7 عنصري به روش شکستن palo Quick sort 9 Dery sort (35) ‏براي حل دو‎ 

صفحه 4:
فصل تقلیل مسئله: کراف ۸7۷12-017 -درتت مسب Gor ۵10.2[ ( درخت جستجو: که 0 (Gort Gon Derge (Perth Gort Gon (@[0..8])(@.7]) ۵ (@[0./P xe) (B[C..0-] ) ( Bler4./°] ) ‏(زم..مزم‎ مسائل ابتدايي : آرايه هاي تك عضوي و سائل ۳۹۲:() و ۳9۵۰) 

صفحه 5:
فصل تقلیل مسئله: کراف :۸۷-01 .پرستسه استخراج بارامترها: 1 - مسئله اصلي: مرتب سازي یک آرایه [60../]() به روش شکستن 2- عملگرها: : 9[ : Sort (A[L..U]) :: M=(L+U)/2 Sort( A[L..m] ) Sort( A[m+1..U] ) Merg( A[L..m], A[m+1..U] ) : Sort(A[L..U]) :: Partition( A[L..U],m ) Sort( A[L..m-1] ) Sort( A[m+1..U] ( Gon(@..L]) Derye Portion ‏مسائل ابتدايي:‎ -3 ee 

صفحه 6:
فصل تقلیل مسئله: کراف :۸۷-01 .پرستسه پس از استخراج پارامترها از تعریف مسئله الگوریتم تقلیل مسئله باید ادغام به تولید فضاي جستجو نمایند که این فضا گرافي است که هر گره آن متناظر با یک گره هاي موجود در گراف به دو دسته تقسیم مي شود . 1-گره هاي 6 ٩26)-گره‏ هاي ‎OOO‏ ‏گره هايي که تحت تاثیر عملگر روش قرار گرفتند گره هايي که تحت تاثیر عملگر تجزیه قرار گرفتند فرق دو گره: مسئله متناظر با گره ۳() در صورتي حل مي شود که يكي از گره هاي فرزند حل شود ولي مسئله متناظر با گره () در صورتي حل مي شود که گره ها فرزند حل شود . 

صفحه 7:
فصل تقلیل مسئله: کراف ۸0۷۵-01 .سر 1- مسئله اصلي : ‎Bird(x)‏ (آیا ۷ پرنده است یانه؟) 2- عملكرها: - عملكر هاي روش 1 3 : ‎Bird(x)‏ : bird(x) :: Fly(x) —_— ‘ ۳۷ Has (x,beak) ‏هاي تجزیه‎ : bird(x) :: Fly(x) Has (x,wings) : bird(x) :: Has (x,beak) Has (x, wings) ۹ : ‏مسائل ابتدايي‎ -3 RN I) Has (c,wings) Has(c,beak) AAO 

صفحه 8:
فصل تقلیل مسئله: کراف ۸7۷12-017 -درتت مسب مسائل ‎bird(a) ©- bird(e) O- bP) -1 :‏ بام بام اما راکسا رما نا ‎Pha) Wer(abeck)‏ ‎True Fail True True‏ ۳ اگر مسئله اي تحت تاثیر عملگر قرار نمي گیرد. مي بینیم که آيا جزء مسائل ابتدایی است. اگر بود حل شده است در غیر اینصورت مسئله حل نشده است © در ,؟] چون قسمت دوم قابل حل نیست يس 1 

صفحه 9:
فصل تقلیل مسئله: کراف ‎guy cay-AND-OR‏ درخت پاسخ : مجموعه گره هايي که در یک ساختار سلسله مراتبي قرار دارند و منجر به تولید پاسخ مستله اصلي مي شود. درخت پاسخ نامیده مي شود («)لسا جستجوي فضاي حالت . سس رس تقلیل مسئله درخت پاسخ كا مسئله حل پذیر است که حداقل یک درخت ياسخ داشته باشد الل لا مسئله اي حل نايذير است كه نه قابل كاهش باشد (يعني عملكر روش را نتوانيم بر روي آن اعمال كنيم) ون بر اساس مسائل ابتدايي حل شود 

صفحه 10:
فصل تقليل مسئّله: _كراف 410719-01 -مسيرهي مل بسي مسير هاي حل يذيري : ميتوان يك ارتباط حل يذيري بين مسائل متناظر با كره هاي درخت ايجاد نمود كه اين رابطه مي تواند از جب به راست و از يايين به بالا باشد و به نحوي مي توان اين ارتباط را در درخت تقليل مسئله نمليش داد كه لين مسير را اصطلاحاً مسير حل يذيري ‎>in ۲‏ كر هم ۲ ‏سه ‏به همين ترتيب ادامه مي يابد تا كراف كامل شود 

صفحه 11:
فصل تقليل مسئّله: _كراف 410719-01 -مسيرهي مل بسي مسير هاي حل پذيري : میتوان یک ارتباط حل پذيري بین مسائل متناظر با گره هاي درخت ایجاد نمود که این رابطه مي تولند از چپ به راست و از يايين به بالا باشد و به نحوي مي توان این ارتباط را در درخت تقلیل مستلهنمیش داد که لن مسیر را صطلاحاً مسیر حل پذيري 

صفحه 12:
فصل تقلیل مسئله: رای ۸۷0-0 - ,مره توضیح : الگوریتم تقلیل مسئله با استفاده از روابط حل پذيري به تدریج مسیر هاي پاسخ را تولید مي کند. ۱ تا جايي که به اولین مسیر پاسخ برسیم و در آنجا تمام مسائل موجود در این مسیر حل شده باشد » آنگاه الگوریتم متوقف مي شود و درخت پاسخ را به کاربر ارائه دهد . الگوریتم تقلیل مسئله براي هر مسئله جست تولید گراف جستجو به شکل زیر عمل مي كقد: [-تمت تاثیر عملگر قرار مي گیرد . 2-تمت تاثیر عملگر قرار نمي گیرد و جزء مسائل ابتدايي است . 3-تمت تاثیر عملگر قرار نمي گیرد و جزء ‎a‏ 

صفحه 13:
فصل تقليل مسئّله: كراف 11717-018يين نمودن بمتريه درفت ب : بهترین درخت پاسخ : براي پیدا کردن درخت بهینه در گراف 6060-068 بايد الكوريتم 69 تغييراتي یابد که به اين الگوریتم 606" ي گویند. بهترین راه حل استفاده از ۱۱ جهت کاهش فضاي جستجو یک نمونه از (] در عملگر تجزیه استفاده می شود ترتیب بررسي عملگر هاي تجزیه در گراف : male(x) Mother(z,x) oo.” 

صفحه 14:
فصل تقليل مسئّله: كراف 11717-018يين نمودن بمتريه درفت و هزینه درخت پاسخ: براساس هزینه هاي حل مسائل ايتدايي موجود در درخت پاسخ محاسبه مي شود گره ‎ :0۲‏ حداقل هزینه هاي فرزند گره 0۲۳ا5] :۵۲۱0 : مجموع هزینه هاي فرزند پا (۷/3: حداکثر هزینه هاي فرزند 

صفحه 15:
مثال اول : كم هزينه تقليل مسئّله: كراف 11717-018يين نمودن بمتريه درفت ‎a]‏ ترین درخت ۷ فصل 

صفحه 16:
فصل ‎auty ona by AND-OR oh 5 ius Glas‏ درفت کم هزینه ترین درخت پاسخ مثال دوم : 

صفحه 17:
رفت بهترين درا ‎eee‏ ‏ید ‏مستُله؛ كراف 117-01# تقليل فصل پا ترین در 5