تقليل مسئله

صفحه 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 

Alireza yousefpour yousefpour@shomal.ac.ir فصل تقليل مسئله: تقليل مسئله گراف AND-OR ()Problem Reduction نوع خاصي از حل مسئله است که در اين روش سعي مي شود مسئله اصلي را با استفاده از مسائل ديگر حل کنند و نهايتا تمام مسائل را با استفاده از مسائلي که بالفاصله قابل حل هستند ،حل کنند اين تجزيه يا تقليل منجر به ايجاد شاخه هايي خواهد شد که به آنها شاخه ANDمي گوييم. به عنوان مثال : خريد يک تلويزيون بدست آوردن تلويزيون کسب مقدار پول دزديدن يک تلويزيون فصل تقليل مسئله: گراف AND-OR -پارامترها براي حل مسئله بايد پارامترهاي زير مشخص شوند: ‏مسئله اصلي :صورت مسئله ‏عملگر :توليد مسائل ديگر را از مسئله اصلي امکان پذير مي سازد ‏مسائل ابتدايي :مسائلي که توسط عملگر ها قابل تجزيه نباشند و قابل حل باشند ‏هزينه مسير :هزينه ثابت; براي هر مرحله مثال :مسئله اصلي مرتب سازي يک آرايه 7عنصري به روش شکستن براي حل دو روش Merge sortو Quick sortداريم – درخت جست;جو AND-OR گراف :فصل تقليل مسئله Sort( A[1..7] ) OR گره rt o S rge e M گره AND Sort Sort ( A[1..4] ) ( A[5..7] ) Merge ( A[1..4] , A[5..7]) Qui ck :درخت جستجو -So rt Partition Sort Sort ( A[1..7],m ) ( A[1..m-1] ) ( A[m+1..7] ) Partition وMerge آرايه هاي تک عضوي و مسائل: مسائل ابتدايي فصل تقليل مسئله: استخراج پارامترها: گراف AND-OR -پارامترها -1مسئله اصلي :مرتب سازي يک آرايه ] A[L..Uبه روش شکستن ‏Sort(A[L..U]) : R1 , R2 -2عملگرها :الف -عملگرهاي روش ب -عملگرهاي تجزيه R1 : 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 ) R2 : Sort(A[L..U]) :: Partition( A[L..U],m ) ]Sort( A[L..m-1 ) ]Sort( A[m+1..U -3مسائل ابتدايي: Partitionو Mergeو ) ]Sort( A[L..L -4هزينه مسير :فرض هزينه هر عمليات يکسان و برابر يک خواهد بود فصل تقليل مسئله: گراف AND-OR -پارامترها پس از استخراج پارامترها از تعريف مسئله الگوريتم تقليل مسئله بايد ادغام به توليد فضاي جستجو نمايند که اين فضا گرافي است که هر گره آن متناظر با يک مسئله مي باشد . گره هاي موجود در گراف به دو دسته تقسيم مي شود . -1گره هاي -OR 2گره هاي AND گره هاي : ORگره هايي که تحت تاثير عملگر روش قرار گرفتندگره هاي : ANDگره هايي که تحت تاثير عملگر تجزيه قرار گرفتندفرق دو گره :مسئله متناظر با گره Orدر صورتي حل مي شود که حداقل يکي از گره هاي فرزند حل شود ولي مسئله متناظر با گره Andدر صورتي حل مي شود که تمام گره هاي فرزند حل شود .  مثال- AND-OR گراف :فصل تقليل مسئله : مثال ديگر ) پرنده است يا نه؟x (آياBird(x) : مسئله اصلي-1 Bird(x) : R1 , R2 , R1: bird(x) :: Fly(x) Has (x,beak) عملگر هاي روشR عملگر هاي تجزيه3 - : عملگرها-2 R2: bird(x) :: Fly(x) Has (x,wings) R3: bird(x) :: Has (x,beak) Has (x, wings) : مسائل ابتدايي-3 Fly(a) , Fly(l) , Has (c,wings) , Has(c,beak) , Has(a,wings) فصل تقليل مسئله: مسائل : گراف AND-OR 3- bird(f) -1 – درخت جست;جو )bird(a )2- bird(c )bird(a ‏R 3 )Has(a,wings )Has(a,beak ‏R1 ‏R 2 )Fly(a) Has(a,wings ‏True ‏True )Fly(a) Has(a,beak ‏Fail ‏True اگر مسئله اي تحت تاثير عملگر قرار نمي گيرد ،مي بينيم که آيا جزء مسائل ابتدايي است ،اگر بود حل شده است در غير اينصورت مسئله حل نشده است در R1چون قسمت دوم قابل حل نيست پس R1قابل حل نيست فصل تقليل مسئله: گراف AND-OR – درخت پاسخ درخت پاسخ : مجموعه گره هايي که در يک ساختار سلسله مراتبي قرار دارند و منجر به توليد پاسخ مسئله اصلي مي شود .درخت پاسخ ناميده مي شود ‏جستجوي فضاي حالت مسير پاسخ درخت پاسخ تقليل مسئله  )bird(a ‏R 2 مسئله حل پذير است که حداقل يک درخت پاسخ داشته باشد )Fly(a) Has(a,wings مسئله اي حل ناپذير است که نه قابل کاهش باشد و نه (يعني عملگر روش را نتوانيم بر روي آن اعمال کنيم) بر اساس مسائل ابتدايي حل شود فصل تقليل مسئله: گراف AND-OR – مسيرهاي حل پذيري مسير هاي حل پذيري : ميتوان يک ارتباط حل پذيري بين مسائل متناظر با گره هاي درخت ايجاد نمود که اين رابطه مي تواند از چپ به راست و از پايين به باال باشد و به نحوي مي توان اين ارتباط را در درخت تقليل مسئله نمايش داد که اين مسير را اصطالحاً مسير حل پذيري ‏P گويند. به همين ترتيب ادامه مي يابد تا گراف کامل شود فصل تقليل مسئله: گراف AND-OR – مسيرهاي حل پذيري مسير هاي حل پذيري : ميتوان يک ارتباط حل پذيري بين مسائل متناظر با گره هاي درخت ايجاد نمود که اين رابطه مي تواند از چپ به راست و از پايين به باال باشد و به نحوي مي توان اين ارتباط را در درخت تقليل مسئله نمايش داد که اين مسير را اصطالحاً مسير حل پذيري ‏P گويند. شش مسير حل پذيري م;س;ي;ر; ح;ل; پ;ذ;ي;ر;ي; م;ت;ع;د;د; م;ن;ج;ر; ب;ه; ت;و;ل;ي;د; د;ر;خ;ت; پ;ا;س;خ; م;ي; ش;و;د; . فصل تقليل مسئله: گراف AND-OR – الگوريتم توضيح :الگوريتم تقليل مسئله با استفاده از روابط حل پذيري به تدريج مسير هاي پاسخ را توليد مي کند. تا جايي که به اولين مسير پاسخ برسيم و در آنجا تمام مسائل موجود در اين مسير حل شده باشد ،آنگاه الگوريتم متوقف مي شود و درخت پاسخ را به کاربر ارائه دهد . الگوريتم تقليل مسئله براي هر مسئله جهت توليد گراف جستجو به شکل زير عمل مي کند: -1تحت تاثير عملگر قرار مي گيرد . مسئله اي که تحت تاثير عملگر قرار مي گيرد عملگر را اعمال کرده و گره هاي جديد توليد مي شود و مسير حل پذيري را نيز ايجاد مي کند . - 2تحت تاثير عملگر قرار نمي گيرد و جزء مسائل ابتدايي است . در اين صورت اگر در مسير حل پذيري سطوح ديگري براساس مسائل حل شده حل مي شوند آنگاه بايد آن مسئله را حل شده در نظر بگيريم و منتظر ارائه درخت پاسخ باشيم. - 3تحت تاثير عملگر قرار نمي گيرد و جزء مسائل ابتدايي نيست . در اين صورت مسئله حل ناپذير است و اگر در مسير پاسخ سطوح باالتر بر اساس اين مسئله حل ناپذير مي شوند بايد وضعيت آن ها را نيز مشخص کرد . فصل تقليل مسئله: پاسخ گراف –AND-ORپيدا نمودن بهترين درخت بهترين درخت پاسخ : کم هزينه ترين درخت پاسخ براي پيدا کردن درخت بهينه در گراف AND-ORبايد الگوريتم *Aتغييراتي يابد که به اين الگوريتم *AOمي گويند. بهترين راه حل استفاده از hجهت کاهش فضاي جستجو يک نمونه از hدر عملگر تجزيه استفاده مي شود ترتيب بررسي عملگر هاي تجزيه در گراف )Brother(x,y) :: male(x )Mother(z,x )Mother(z,y فصل تقليل مسئله: پاسخ گراف –AND-ORپيدا نمودن بهترين درخت هزينه درخت پاسخ: براساس هزينه هاي حل مسائل ابتدايي موجود در درخت پاسخ محاسبه مي شود ‏فرض گراف تقليل مسئله بطور کامل توليد شده است ‏هزينه حل مسائل ابتدايي در ابتدا قطعاً معلوم اند . ‏هزينه مسائل حل ناپذير را در نظر مي گيريم . ‏هزينه گره هاي باالتر گره : Orحداقل هزينه هاي فرزند گره : And: Sumمجموع هزينه هاي فرزند يا :Maxحداکثر هزينه هاي فرزند فصل تقليل مسئله: پاسخ گراف –AND-ORپيدا نمودن بهترين درخت کم هزينه ترين درخت پاسخ مثال اول : ‏P بهترين درخت پاسخ 3 5 از بين سه درخت پاسخ 3 5 5 0 2 3 2 7 2 5 1 0 4 5 2 5 5 2 0 1 5 3 0 فصل تقليل مسئله: پاسخ گراف –AND-ORپيدا نمودن بهترين درخت کم هزينه ترين درخت پاسخ مثال دوم : ‏A بهترين درخت پاسخ ()9 ‏D ‏C ‏B 5 4 3 هزينه عملگرها يک مي باشد فصل تقليل مسئله: پاسخ گراف –AND-ORپيدا نمودن بهترين درخت کم هزينه ترين درخت پاسخ مثال سوم : ‏A ‏D 38 27 بهترين درخت پاسخ ‏C ‏B 17 9 ‏J ‏I ‏H ‏G ‏F ‏E 10 15 4 3 10 5 هزينه عملگرها يک مي باشد