تقلیل مسئله

تقلیل مسئله

اسلاید 1: تقليل مسئلهAlireza yousefpouryousefpour@shomal.ac.ir

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

اسلاید 3: براي حل مسئله بايد پارامترهاي زير مشخص شوند: مسئله اصلي: صورت مسئلهعملگر: توليد مسائل ديگر را از مسئله اصلي امکان پذير مي سازدمسائل ابتدايي: مسائلي که توسط عملگر ها قابل تجزيه نباشند و قابل حل باشندهزينه مسير: هزينه ثابت براي هر مرحلهمثال: مسئله اصلي مرتب سازي يک آرايه 7 عنصري به روش شکستنبراي حل دو روش Merge sort و Quick sort داريمفصل تقليل مسئله: گراف AND-OR - پارامترها

اسلاید 4: درخت جستجو:Sort( A[1..7] )Sort( A[1..4] )Sort( A[5..7] )Merge( A[1..4] , A[5..7])Partition( A[1..7],m )Sort( A[1..m-1] )Sort( A[m+1..7] )Merge-SortQuick-Sortمسائل ابتدايي :آرايه هاي تک عضويو مسائل Merge و Partitionگره ORگره ANDفصل تقليل مسئله: گراف AND-OR – درخت جستجو

اسلاید 5: استخراج پارامترها:1- مسئله اصلي: مرتب سازي يک آرايه A[L..U] به روش شکستن2- عملگرها:الف- عملگرهاي روشSort(A[L..U]) : R1 , R2 ب- عملگرهاي تجزيه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 - پارامترها

اسلاید 6: فرق دو گره: مسئله متناظر با گره Or در صورتي حل مي شود که حداقل يکي از گره هاي فرزند حل شودولي مسئله متناظر با گره And در صورتي حل مي شود که تمام گره هاي فرزند حل شود . پس از استخراج پارامترها از تعريف مسئله الگوريتم تقليل مسئله بايد ادغام به توليد فضاي جستجو نمايند که اين فضا گرافي است که هر گره آن متناظر با يک مسئله مي باشد .گره هاي موجود در گراف به دو دسته تقسيم مي شود .1-گره هاي OR 2-گره هاي AND -گره هاي OR : گره هايي که تحت تاثير عملگر روش قرار گرفتند-گره هاي AND : گره هايي که تحت تاثير عملگر تجزيه قرار گرفتندفصل تقليل مسئله: گراف AND-OR - پارامترها

اسلاید 7: 1- مسئله اصلي : Bird(x) (آيا x پرنده است يا نه؟)2- عملگرها:R1: bird(x) :: Fly(x) Has (x,beak)R2: bird(x) :: Fly(x) Has (x,wings)R3: bird(x) :: Has (x,beak) Has (x, wings)Fly(a) , Fly(l) , Has (c,wings) , Has(c,beak) , Has(a,wings) 3- مسائل ابتدايي : مثال ديگر :عملگر هاي روش Bird(x) : R1 , R2 , R3 عملگر هاي تجزيهفصل تقليل مسئله: گراف AND-OR - مثال

اسلاید 8: مسائل :bird(a)R3R2R1Fly(a)Has(a,beak)Fly(a)Has(a,wings)Has(a,beak)Has(a,wings) اگر مسئله اي تحت تاثير عملگر قرار نمي گيرد، مي بينيم که آيا جزء مسائل ابتدايي است، اگر بود حل شده است در غير اينصورت مسئله حل نشده استTrueFailTrueTrue 1- bird(a) 2- bird(c) 3- bird(f) در R1 چون قسمت دوم قابل حل نيست پس R1 قابل حل نيست فصل تقليل مسئله: گراف AND-OR – درخت جستجو

اسلاید 9: مجموعه گره هايي که در يک ساختار سلسله مراتبي قرار دارند و منجر به توليد پاسخ مسئله اصلي مي شود. درخت پاسخ ناميده مي شودجستجوي فضاي حالت  مسير پاسخ تقليل مسئله  درخت پاسخ مسئله حل پذير است که حداقل يک درخت پاسخ داشته باشد مسئله اي حل ناپذير است که نه قابل کاهش باشد(يعني عملگر روش را نتوانيم بر روي آن اعمال کنيم) و نه بر اساس مسائل ابتدايي حل شوددرخت پاسخ : bird(a)R2Fly(a)Has(a,wings)فصل تقليل مسئله: گراف AND-OR – درخت پاسخ

اسلاید 10: ميتوان يک ارتباط حل پذيري بين مسائل متناظر با گره هاي درخت ايجاد نمود که اين رابطه مي تواند از چپ به راست و از پايين به بالا باشد و به نحوي مي توان اين ارتباط را در درخت تقليل مسئله نمايش داد که اين مسير را اصطلاحاً مسير حل پذيري گويند.Pمسير هاي حل پذيري :به همين ترتيب ادامه مي يابد تا گراف کامل شودفصل تقليل مسئله: گراف AND-OR – مسيرهاي حل پذيري

اسلاید 11: مسير حل پذيري متعدد منجر به توليد درخت پاسخ مي شود .Pشش مسير حل پذيريفصل تقليل مسئله: گراف AND-OR – مسيرهاي حل پذيري ميتوان يک ارتباط حل پذيري بين مسائل متناظر با گره هاي درخت ايجاد نمود که اين رابطه مي تواند از چپ به راست و از پايين به بالا باشد و به نحوي مي توان اين ارتباط را در درخت تقليل مسئله نمايش داد که اين مسير را اصطلاحاً مسير حل پذيري گويند.مسير هاي حل پذيري :

اسلاید 12: توضيح : الگوريتم تقليل مسئله با استفاده از روابط حل پذيري به تدريج مسير هاي پاسخ را توليد مي کند.تا جايي که به اولين مسير پاسخ برسيم و در آنجا تمام مسائل موجود در اين مسير حل شده باشد ، آنگاه الگوريتم متوقف مي شود و درخت پاسخ را به کاربر ارائه دهد .3-تحت تاثير عملگر قرار نمي گيرد و جزء مسائل ابتدايي نيست .الگوريتم تقليل مسئله براي هر مسئله جهت توليد گراف جستجو به شکل زير عمل مي کند:1-تحت تاثير عملگر قرار مي گيرد .مسئله اي که تحت تاثير عملگر قرار مي گيرد عملگر را اعمال کرده و گره هاي جديد توليد مي شود و مسير حل پذيري را نيز ايجاد مي کند .2-تحت تاثير عملگر قرار نمي گيرد و جزء مسائل ابتدايي است .در اين صورت اگر در مسير حل پذيري سطوح ديگري براساس مسائل حل شده حل مي شوند آنگاه بايد آن مسئله را حل شده در نظر بگيريم و منتظر ارائه درخت پاسخ باشيم.در اين صورت مسئله حل ناپذير است و اگر در مسير پاسخ سطوح بالاتر بر اساس اين مسئله حل ناپذير مي شوند بايد وضعيت آن ها را نيز مشخص کرد .فصل تقليل مسئله: گراف AND-OR – الگوريتم

اسلاید 13: براي پيدا کردن درخت بهينه در گراف AND-OR بايد الگوريتم A* تغييراتي يابد که به اين الگوريتم AO* مي گويند.کم هزينه ترين درخت پاسخBrother(x,y) :: male(x) Mother(z,x) Mother(z,y)بهترين درخت پاسخ : بهترين راه حل استفاده از h جهت کاهش فضاي جستجويک نمونه از h در عملگر تجزيه استفاده مي شود ترتيب بررسي عملگر هاي تجزيه در گراف فصل تقليل مسئله: گراف AND-OR–پيدا نمودن بهترين درخت پاسخ

اسلاید 14: فرض گراف تقليل مسئله بطور کامل توليد شده استهزينه حل مسائل ابتدايي در ابتدا قطعاً معلوم اند .هزينه مسائل حل ناپذير را  در نظر مي گيريم .هزينه درخت پاسخ:براساس هزينه هاي حل مسائل ابتدايي موجود در درخت پاسخ محاسبه مي شودهزينه گره هاي بالاترگره Or : حداقل هزينه هاي فرزند گره And: Sum : مجموع هزينه هاي فرزند يا Max: حداکثر هزينه هاي فرزندفصل تقليل مسئله: گراف AND-OR–پيدا نمودن بهترين درخت پاسخ

اسلاید 15: P3015205102723252545355035کم هزينه ترين درخت پاسخبهترين درخت پاسخاز بين سه درخت پاسخمثال اول :فصل تقليل مسئله: گراف AND-OR–پيدا نمودن بهترين درخت پاسخ

اسلاید 16: ABCD345(9)کم هزينه ترين درخت پاسخمثال دوم : هزينه عملگرها يک مي باشدبهترين درخت پاسخفصل تقليل مسئله: گراف AND-OR–پيدا نمودن بهترين درخت پاسخ

اسلاید 17: ABCD38EFGHIJ17927510341510کم هزينه ترين درخت پاسخمثال سوم : هزينه عملگرها يک مي باشدبهترين درخت پاسخفصل تقليل مسئله: گراف AND-OR–پيدا نمودن بهترين درخت پاسخ