برنامه نویسی پویا

برنامه نویسی پویا

اسلاید 1: کوئیز از جلسه قبل)در کامپیوتری برای ضرب استراسن فرایند تقسیم نمونه‌‌ای به اندازه n به نمونه‌های کوچکتر، بارگذاری در پشته، فراخوانی از آن، جمع‌ها و تفریق‌ها همگی 12n2 μs طول می‌کشد. چنانچه با الگوریتم استانداردی n3 μs ضرب دو ماتریس با ابعاد n × n طول بکشد، حد آستانه‌ای بیابید که بهتر است از الگوریتم استاندارد به جای الگوریتم استراسن استفاده کنیم. آیا در این حل حد آستانه واحدی وجود دارد؟2

اسلاید 2: برنامه نویسی پویا (Dynamic Programming)یادآوری: روش تقسیم و حل برای محاسبه جمله n ام فیبوناجیروش تقسیم و حل، روشی بالا به پایین است. این روش در مسائلی مانند مرتب سازی ادغامی جواب می‌دهد چراکه نمونه‌های کوچکتر به مرتبط نیستند.ولی در محاسبه جمله nام فیبوناجی، نمونه‌ها کوچکتر به هم مرتبطند3

اسلاید 3: برنامه نویسی پویابرنامه نویسی پویا از این نظر که نمونه به نمونه‌های کوچکتر تقسیم می‌شود، مشابه روش تقسیم و حل است ولی1- ابتدا نمونه‌های کوچکتر را حل می‌کنیم2- نتایج را ذخیره می‌کنیم و 3- بعدا هرگاه به آنها نیاز شد به جای محاسبه مجدد تنها آنها را بازیابی می‌کنیمبنابراین روشی پایین به بالا است4

اسلاید 4: برنامه نویسی پویامراحل بسط یک الگوریتم برنامه نویسی پویا:1- ارائه یک ویژگی بازگشتی برای نمونه‌ای از مسئله2- حل مسئله به شیوه پایین به بالا با حل نمونه‌های کوچکتر5

اسلاید 5: الف) ضریب دوجمله‌ای6

اسلاید 6: الف) ضریب دوجمله‌ایحل با استفاده از روش تقسیم‌وحل:function [result]=binCoef(n,k) if (k==0 || k==n) result=1; else result=binCoef(n-1,k-1)+binCoef(n-1,k); endend7

اسلاید 7: الف) ضریب دوجمله‌ایهمانند محاسبه جمله nام فیبوناجی، این الگوریتم نیز کارایی کمی دارد.مثلا binCoef(n-1,k-1) و binCoef(n-1,k) هر دو نیاز به نتیجه binCoef(n-2,k-1) دارند و این نمونه در هر فراخوانی بازگشتی به صورت جداگانه محاسبه می‌شود.8

اسلاید 8: الف) ضریب دوجمله‌ایحل با روش پویا:1- یک ویژگی بازگشتی ایجاد می‌کنیم2- مسئله را به صورت پایین به بالا حل می‌کنیم ...9

اسلاید 9: الف) ضریب دوجمله‌ایحل با روش پویا:1- یک ویژگی بازگشتی ایجاد می‌کنیم2- مسئله را به صورت.... پایین به بالا حل می‌کنیم:10

اسلاید 10: الف) ضریب دوجمله‌ایحل با روش پویا:function [result]=binCoef2(n,k) for i=0:n for j=0:min([i k]) if ((j==0)||(j==i)) B(i,j)=1; else B(i,j)=B(i-1,j-1)+B(i-1,j); end end end result=B(n,k);end11تمرین: تابع فوق را به گونه‌ای تغییر دهید که اجرای آن در Matlab صحیح باشد

اسلاید 11: الف) ضریب دوجمله‌ایپیچیدگی محاسباتی و مرتبه آن:for i=1:n for j=1:min([i k]) endend12

اسلاید 12: الف) ضریب دوجمله‌ایتمرین: مسئله ضریب دو جمله‌ای را با برنامه‌نویسی پویا با آرایه یک بعدی حل کنید13

اسلاید 13: کوئیز از جلسه قبل)برای یافتن ضریب kام دوجمله‌ای رابطه زیر برقرار است.الف) ویژگی بازگشتی ارائه دهید که ضریب kام با روش برنامه نویسی پویا بدست آید.ب) تابع متناظر با ویژگی بازگشتی در بخش الف را بنویسید14

اسلاید 14: مسائل بهینه سازیدر ریاضیات و علوم کامپیوتر مساله بهینه‌سازی به صورت زیر تعریف می‌شود:مساله‌ای است که در آن به دنبال یافتن بهترین راه حل در بین...تمامی راه حل‌های ممکن هستیم.این مسائل باتوجه متغیرهای موثر در حل مسئله به دو گروه زیر تقسیم می‌شوند:متغیرهای پیوسته مساله بهینه‌سازی پیوستهمتغیرهای گسستهمساله بهینه‌سازی ترکیبی 15

اسلاید 15: مسائل بهینه سازیمساله بهینه‌سازی پیوستهفرم استاندارد این مسائل به صورت زیر است:که ...تابع هدفی است که می‌خواهیم xای را برایش بیابیم که آن را کمینه کند.محدودیت‌هایی هستند که به صورت عدم تساوی بیان می‌شوند.محدودیت‌هایی هستند که به صورت تساوی بیان می‌گردند.16

اسلاید 16: مسائل بهینه سازیمسائل بهینه‌سازی ترکیبیمانند ....مساله یافتن کوتاه‌ترین مسیر بین دو شهراین مسائل به صورت چهارتایی (I, f, m, g) بیان می‌شوند که ....I مجموعه نمونه‌ها است مانند ...مجموعه شهرها به صورت دوبه‌دوxای که عضو I است را در نظر بگیرید مانند ... (یزد و کرمانشاه)f(x) مجموعه راه حل‌های ممکن برای این x است مانند ...مسیرهای مختلف جاده‌ای بین این دو شهر17

اسلاید 17: مسائل بهینه سازیمسائل بهینه‌سازی ترکیبی (I, f, m, g)فرض کنید که y، یکی از راه حل‌های ممکن باشد مانند... یزد-ابرکوه-اصفهان-بروجرد-کنگاور-کرمانشاهm(x,y) تابعی است که اندازه y به ازای x که معمولا عددی مثبت است را برمی‌گرداند.g، تابع هدف است که معمولا یا min و یا max است.هدف در این مسائل بهینه‌سازی آن است تا ....برای هر x، ...بهینه‌ترین راه حل (y) با توجه به تابع هدف را پیدا کنیم.18

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

اسلاید 19: اصل بهینگی (Principle of Optimality)تعریف: مساله‌ای شرایط اصل بهینگی را داردچنانچه در آن مساله ...زیر راه‌حل‌های یک راه‌‌حل بهینه برای هر نمونه مساله‌ ...خودشان راه‌حل‌های بهینه برای زیرمسائلی متناظر باشند.20حل مسائل بهینه‌سازی ترکیبی با برنامه‌نویسی پویا

اسلاید 20: مثال: آیا شرایط بهینگی در مساله کوتاه‌ترین مسیر برقرار است؟ روش بررسی ....اگر برای مساله کوتاه‌ترین مسیر از هر a به هر bای، ...a,x1,x2,...,xn,b راه‌حل بهینه باشد ...در این‌صورت هر بخش xi to xj در این راه‌حل بهینه ...خود را حل بهینه برای کوتاه‌ترین مسیر از xi به xj می‌باشد ...چراکه اصلا ممکن نیست بخشی از راه‌حل کوتاه‌ترین مسیر نباشد ولی کل راه حل بهینه گردد.21حل مسائل بهینه‌سازی ترکیبی با برنامه‌نویسی پویا

اسلاید 21: مثال: همان مساله قبلی را به جای کوتاه‌ترین مسیر، طولانی‌ترین مسیر ساده درنظر بگیرید.مسیر ساده: مسیری که هیچگاه دوبار از یک راس نگذرد.حالا چرا مسیر ساده ؟ ....اصل بهینگی برقرار است؟آیا نمی‌توان همان توجیه کوتاه‌ترین مسیر را اینجا نیز مطرح کنیم؟ امکان دارد بین دو راس میانی طولانی‌ترین مسیر ساده‌ای وجود داشته باشد که اگر طولانی‌ترین مسیر مساله اصلی بخواهد از همان بگذرد دیگر ساده نشود یعنی مجبور است از یک راس دوبار بگذرد.22حل مسائل بهینه‌سازی ترکیبی با برنامه‌نویسی پویا

اسلاید 22: به مثال زیر توجه کنید:طولانی‌ترین مسیر از v1 به v4، ....[v1, v3, v2, v4] هست ولی ...طولانی‌ترین مسیر از v1 به v3 دیگر ...[v1, v3] نیست بلکه ....[v1,v2,v3] است.23حل مسائل بهینه‌سازی ترکیبی با برنامه‌نویسی پویا

اسلاید 23: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافنمایش یک گراف وزن‌دار جهت‌دار در شکل زیر آمده است:24

اسلاید 24: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافچرخه: مسیری از یک راس به خود آن راسمسیر ساده: مسیری که هیچگاه دوبار از یک راس نگذردطول مسیر: حاصلجمع وزن یال‌های مسیر و اگر یال‌ها وزن نداشتند برابر با تعداد یال‌ها در مسیر25

اسلاید 25: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافبا این الگوریتم می‌خواهیم کوتاه‌ترین مسیر بین هر دو گره را به‌دست بیاوریم.یک الگوریتم واضح: تعیین طول همه مسیر‌ها برای هر راس از آن راس به همه رئوس دیگر26

اسلاید 26: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافیک گراف وزن‌دار حاوی n راس را با آرایه W نشان می‌دهیم:27

اسلاید 27: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافدر این الگوریتم، در نهایت می‌خواهیم ماتریس D را که دربرگیرنده کوتاه‌ترین مسیر بین هر دو گره است را پیدا کنیم28

اسلاید 28: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافD(k) [i][j] را برابر طول کوتاه‌ترین مسیری قرار می‌دهیم که vi را به vj وصل می‌کند و فقط هم از راس‌های موجود در مجموعه {v1,v2,…,vk} به عنوان رئوس میانی استفاده می‌کند. 29

اسلاید 29: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافبنابراین برای پیداکردن D بایستی به دنبال راه حلی باشیم که ...D(n) را از D(0) به دست بیاوریم.همانگونه که در جلسه قبل بیان شد در برنامه نویسی پویا باید ابتدا ...ویژگی بازگشتی بنویسیم که ...D(k) را از D(k-1) بدست بیاورد.سپس ...برنامه‌ای بنویسیم که مساله را به صورت پایین به بالا حل کند. یعنی در برنامه ...k را ابتدا صفر قرار دهیم و تا n این فرایند را تکرار کنیم.30

اسلاید 30: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافگام اول: ویژگی بازگشتی بنویسیم که D(k) را از D(k-1) بدست بیاورد.برای حل این گام می‌توانیم دو حالت را در نظر بگیریم:حالت اول: ...استفاده از راس kام در مرحله kام سبب کوتاه‌ترشدن مسیر نمی‌شود.حالت دوم: ...استفاده از راس kام سبب کوتاه‌ترشدن مسیر می‌شود.31

اسلاید 31: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافگام اول: ویژگی بازگشتی بنویسیم که D(k) را از D(k-1) بدست بیاورد.حالت دوم: ...استفاده از راس kام سبب کوتاه‌ترشدن مسیر می‌شود.از آنجایی که vk نمی‌تواند راس میانی در زیر مسیرها از vi به vk و همچنین از vk به vj باشد بنابراین ...در این مسیرها تنها از مجموعه رئوس {v1,…,vk-1} به عنوان رئوس میانی استفاده می‌شود. یعنی ...32

اسلاید 32: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافبنابراین چون حالت‌های ما از این دو حالت خارج نیست بنابراین ...حالتی که کمتر می‌شود درنظر گرفته می‌شود ...33

اسلاید 33: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گراف34

اسلاید 34: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافبعد از اینکه کل آرایه D(1) محاسبه شد سپس آرایه D(2) محاسبه می‌شود.35

اسلاید 35: کوئیز از جلسه قبل)الف) اصل بهینگی در برنامه‌نویسی پویا چیست؟ب) آیا این اصل در مساله یافتن طولانی‌ترین مسیر ساده در گراف برقرار است؟ پاسخ خود را با مثالی توضیح دهید.36

اسلاید 36: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافfunction [D,P]=floyd(W) n=length(W); D=zeros(n,n,n); D(0,:,:)=W; for k=1:n for i=1:n for j=1:n if ((D(k-1,i,k)+D(k-1,k,j)<D(k-1,i,j))) D(k,i,j)=D(k-1,i,k)+D(k-1,k,j); else D(k,i,j)=D(k-1,i,j); end end end endend37

اسلاید 37: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافاگر بخواهیم به جای آرایه سه‌بعدی با یک آرایه دو‌بعدی الگوریتم را بنویسیم ...چه مشکلی پیش می‌آید؟ ...امکان دارد در دور kامی مقدار D[i][k] یا D[k][j]ای تغییر کند و ما دیگر در همان دور kام نتوانیم به مقادیر دور k-1ام آنها دسترسی پیدا کنیم.نشان می‌دهیم که این دو مقدار در دور kام هیچگاه تغییر نمی‌کنند ...38

اسلاید 38: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافچاپ کردن کوتاه‌ترین مسیرماتریس P[i][j] را به این صورت تعریف می‌کنیم:0: چنانچه راس میانی در کوتاه‌ترین مسیر از vi به vj وجود نداشته باشد.بزرگترین اندیس راس میانی: چنانچه حداقل یک راس میانی در کوتاه‌ترین مسیر وجود داشته باشد. if ((D(i,k)+D(k,j)<D(i,j)))P(i,j)=k;39

اسلاید 39: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافfunction [D,P]=floyd(W) n=length(W); D=W; P=zeros(n,n); for k=1:n for i=1:n for j=1:n if ((D(i,k)+D(k,j)<D(i,j))) D(i,j)=D(i,k)+D(k,j); P(i,j)=k; else D(i,j)=D(i,j); end end end endend40

اسلاید 40: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافچنانچه الگوریتم گفته‌شده بر گراف زیر اعمال شود، ماتریس P محتوایی برابر مقدار زیر خواهد داشت.41

اسلاید 41: ب) الگوریتم فلوید برای یافتن کوتاه‌ترین مسیر در گرافتمرین: تابعی با نام printPath بنویسید که با دادن i و j، اندیس راس‌های واقع در کوتاه‌ترین مسیر بین این دو راس را با رویکرد تقسیم‌وحل چاپ کند. فرض کنید P به صورت global تعریف شده‌است.پیچیدگی زمانی الگوریتم فلوید: 42

اسلاید 42: کوئیز از جلسه قبل) در گراف زیر با الگوریتم فلوید، کوتاه‌ترین مسیر بین هر دو راس را بدست آورید. در هر گام، Dk (k=0…n) را نشان دهید.43v1v2v3v4v512111756

اسلاید 43: ج) ضرب زنجیره‌ای ماتریس‌هاظرب چهار ماتریس زیر را درنظر بگیرید:ابعاد هر ماتریس در زیر آن نشان داده شده است.اپراتور ضرب ماتریس‌ها ویژگی انجمنی (associative) دارد.ویژگی انجمنی به این معنا است که ترتیب ضرب در نتیجه حاصل تاثیری ندارد.برای مثال A (B (CD)) و (AB (CD) هر دو نتیجه یکسانی دارند.چهار ماتریس را با پنج ترتیب متفاوت می‌توان در هم ضرب کرد.هر ترتیب ضرب تعداد عملیات‌های ضرب پایه‌ای متفاوتی خواهد داشت.44

اسلاید 44: ج) ضرب زنجیره‌ای ماتریس‌هابرای این پنج ماتریس تعداد عملیات‌های پایه‌ای ضرب آورده شده است.سومین ترتیب از این نظر که تعداد عملیات‌های ضرب پایه‌ای کمتری در آن صورت می‌پذیرد بهینه است.45

اسلاید 45: ج) ضرب زنجیره‌ای ماتریس‌هادر این مساله به دنبال آن هستیم ترتیب بهینه ضرب n ماتریس را بدست آوریم که ...تعداد عملیات پایه‌ای ضرب کمتری در آن صورت پذیرد.46

اسلاید 46: ج) ضرب زنجیره‌ای ماتریس‌هااین مساله به صورت چهارتایی (I, f, m, g) بیان می‌شوند که .... I مجموعه نمونه‌ها است. در اینجا ...مجموعه حاصلضرب ماتریس‌های مختلف با ابعاد و n های مختلفxای که عضو I است را درنظر بگیریم. مثلا ...یک نمونه از حاصلضرب ماتریس‌ها مانند مثال اسلاید قبلf(x) مجموعه راه حل‌های ممکن از ویژگی انجمنی ضرب این نمونه است.با فرض اینکه y، یکی از این راه حل‌ها باشد،m(x,y) بیانگر تعداد ضرب‌های پایه است.g، تابع هدف است که در اینجا min می‌باشد.47

اسلاید 47: ج) ضرب زنجیره‌ای ماتریس‌هاالگوریتمی که تمام yها را به ازای هر x درنظر می‌گیرد: ...(brute force)در این مساله بهینه سازی، بیاییم و تمامی ترتیب‌های ممکن را ایجاد کنیم، ....در هر ترتیب، تعداد ضرب‌های پایه را بشماریم و ...ترتیبی را انتخاب کنیم که کمترین تعداد ضرب‌های پایه را دارد.48

اسلاید 48: ج) ضرب زنجیره‌ای ماتریس‌هاالگوریتم brute force:فرض کنید tn تعداد ترتیب‌های مختلفی باشد که n ماتریس A1, A2, …, An را در هم می‌توان در هم ضرب کرد.خانواده‌ای از ترتیب‌ها می‌تواند به این صورت باشد:غیر از این خانواده، گروهی دیگر را هم می‌توان درنظر گرفت که ...An آخرین ماتریسی باشد که ضرب می‌شود.49

اسلاید 49: ج) ضرب زنجیره‌ای ماتریس‌هابنابراین، و از آنجاییکه t2 = 1، این رابطه بازگشتی به صورت زیر حل می‌شود.50

اسلاید 50: ج) ضرب زنجیره‌ای ماتریس‌هاآیا اصل بهینگی در این مساله برقرار است؟بله، چراکه چنانچه ترتیب بهینه برای ضرب n ماتریس اگر داشته باشیم در این صورت، هر زیر راه حل آن مسلما خود راه حل بهینه برای ماتریس‌های موجود در زیر راه حل می‌باشد.به عنون مثال چنانچه راه حل زیر ترتیب بهینه برای ضرب ماتریس‌های A1 تا A6 باشد، آنگاه ...باید ترتیب بهینه برای ضرب ماتریس‌های A2 تا A4 باشد. 51

اسلاید 51: ج) ضرب زنجیره‌ای ماتریس‌هابرای آغاز حل مساله ابتدا ساختاری را تعریف می‌کنیم که بر اساس آن بتوانیم ویژگی بازگشتی را تعریف کنیم:فرض کنید در ماتریس M، M [i] [j] برابر با حداقل تعداد ضرب‌ها برای ضرب ماتریس‌های Ai تا Aj باشد (چنانچه i<j باشد).بنابراین ...M [i] [i] =052

اسلاید 52: ترتیب بهینه برای ضرب شش ماتریس A1 تا A6 در یکی از پنج حالت‌ زیر قرار می‌گیرد.A1 (A2A3A4A5A6)(A1A2) (A3A4A5A6)(A1A2A3) (A4A5A6)(A1A2A3A4) (A5A6)(A1A2A3A4A5) (A6)ج) ضرب زنجیره‌ای ماتریس‌ها53

اسلاید 53: ج) ضرب زنجیره‌ای ماتریس‌هاآیا ویژگی بازگشتی بدست آمد؟شبیه هر حل با برنامه نویسی پویا بعد از بدست آوردن ویژگی بازگشتی بایستی ترتیب اجرایی در برنامه نویسی پیدا کنیم تا مساله از پایین به بالا حل شود.یعنی باید مشخص کنیم که المان‌های ماتریس M به چه نحوی مقدار دهی شود تا در نهایت ....؟M[1][n] بدست آید.54

اسلاید 54: ج) ضرب زنجیره‌ای ماتریس‌ها55

اسلاید 55: ج) ضرب زنجیره‌ای ماتریس‌هاfunction [m,P]=minimult(d) n=length(d)-1; M=zeros(n,n); P=zeros(n,n); for diagonal=2:n for i=1:n-diagonal+1 j=i+diagonal-1; clear values; for k=i:j-1 values(k)=M(i,k)+M(k+1,j)+d(i)*d(k+1)*d(j+1); end [M(i,j),k]=min(values); P(i,j)=k; end end m=M(1,n);end56

اسلاید 56: ج) ضرب زنجیره‌ای ماتریس‌هاfor diagonal=2:n for i=1:n-diagonal+1 j=i+diagonal-1; for k=i:j-1 end endend57تمرین: نشان دهید که حاصل این سیگما برابر با رابطه زیر است.

اسلاید 57: ج) ضرب زنجیره‌ای ماتریس‌هاThe array P58

اسلاید 58: ج) ضرب زنجیره‌ای ماتریس‌هاfunction order(i,j) global P; if (i==j) disp([A num2str(i)]); else k=P(i,j); disp((); order(i,k); order(k+1,j); disp()); endend59

اسلاید 59: کوئیز از جلسه قبل) ترتیب و هزینه ضرب بهینه چهار ماتریس A1(10*4)، A2(4*5)، A3(5*20)، A4(20*2) بدست آورید. دو ماتریس M و P را نشان دهید و بر اساس ماتریس P ضرب بهینه را براساس تابع زیر نشان دهید.function order(i,j) global P; if (i==j) disp([A num2str(i)]); else k=P(i,j); disp((); order(i,k); order(k+1,j); disp()); endend60

اسلاید 60: د) درخت جستجوی دودویی بهینهدرخت جستجوی دودویی، درختی دودویی از آیتم‌ها است.این آیتم‌ها معمولا کلید‌هایی هستند که ...از یک مجموعه مرتب بدست می‌آیند یعنی ...برای آیتم‌ها اپراتورهای کوچکتر، بزرگتر و مساوی وجود داردمانند مجموعه کدهای ملی، مجموعه نام‌های خانوادگیدر این درخت:هر راس، شامل یک کلید می‌شودکلیدهایی که در زیردرخت سمت چپ هر راس وجود دارند، کوچکتر از کلید آن راس هستند.کلیدهایی که در زیردرخت سمت راست هر راس وجود دارند، بزرگتر از کلید آن راس هستند.61

اسلاید 61: د) درخت جستجوی دودویی بهینه62

اسلاید 62: د) درخت جستجوی دودویی بهینهعمق هر راس در درخت برابر است با ...تعداد یالهایی که در مسیر واحد ریشه به آن راس وجود دارد.به عمق، همچنین سطح نیز گفته می‌شود. عمق درخت، ...بیشینه عمق راس‌های درخت می‌باشد.درخت دودویی بالانس است، اگر ...تفاوت عمق دو زیردرخت هر راس، بیشتر از یک نباشد.63

اسلاید 63: د) درخت جستجوی دودویی بهینههدف آن است تا کلیدها در درخت جستجویی دودویی به گونه‌ای سازمان‌دهی شوند که ...میانگین زمان برای پیداکردن کلیدها‌ کمینه شود.درختی که با این رویکرد سازمان‌دهی شود، بهینه گفته می‌شود.اگر همه کلیدهای با احتمال یکسان کلید جستجو باشند ...بین این دو درخت کدام‌یک بهینه است؟64√

اسلاید 64: د) درخت جستجوی دودویی بهینهمساله بهینه‌سازی که در این جلسه مد نظر است، ...کلید‌ها دارای احتمال جستجوی یکسان نیستند.مثلا، درخت جستجوی دودویی را درنظر بگیرید که کلیدها نام افراد می‌باشد.در این درخت باتوجه به نام افراد به رکورد اطلاعاتی آنها دست می‌یابیم.چون «Tom» بیشتر از نام «Ursula» عمومی است، بنابراین احتمال بیشتری به آن نسبت داده می‌شود. برای آنکه میانگین زمان جستجو کمینه شود بایستی تعریفی از زمان جستجو ارائه شود. 65

اسلاید 65: د) درخت جستجوی دودویی بهینهزمان جستجو: تعداد مقایسه‌هایی که توسط تابع جستجو برای یافتن هر کلید صورت می‌پذیرد.هدف: یافتن درخت جستجوی دودویی است که ...میانگین زمان جستجو کمینه گردد.66

اسلاید 66: د) درخت جستجوی دودویی بهینهاین مساله به صورت چهارتایی (I, f, m, g) بیان می‌شود که .... I مجموعه نمونه‌ها است. در اینجا ...مجموعه کلیدها با احتمال جستجو برای هر کلیدxای که عضو I است را درنظر بگیریم. مثلا ...یک تعدادی مشخص از کلیدها که به هر کلید احتمال جستجویی نسبت داده شده است. f(x) مجموعه درخت‌های جستجوی دودویی متفاوتی که می‌توان درنظر گرفت. با فرض اینکه y، یکی از این راه حل‌ها باشد،m(x,y) بیانگر میانگین زمان جستجو در درخت y می‌باشد.g، تابع هدف است که در اینجا min می‌باشد.67

اسلاید 67: د) درخت جستجوی دودویی بهینهمی‌توانیم رابطه زیر را برای زمان جستجوی هر کلید ارائه دهیم:مثلا در درخت جستجوی دودویی زیر زمان جستجو برای کلید «Ursula» برابر است با:68

اسلاید 68: د) درخت جستجوی دودویی بهینهفرض کنید «Key1, Key2,…, Keyn»، n کلید مرتب شده باشد.فرض کنید که pi احتمالی است که Keyi جستجو شود.چنانچه ci زمان جستجوی یافتن Keyi در هر درخت فرضی باشد، با توجه به فرضیات بالا، برای درخت جستجوی دودویی مفرض، میانگین زمان جستجو با رابطه زیر محاسبه می‌شود:این همان مقداری است که به دنبال کمینه کردن آن هستیم.69

اسلاید 69: د) درخت جستجوی دودویی بهینهبرای این پنج درخت، میانگین زمان جستجو به صورت زیر محاسبه می‌شود:3 (0.7) + 2 (0.2) + 1 (0.1) = 2.62 (0.7) + 3 (0.2) + 1 (0.1) = 2.12 (0.7) + 1 (0.2) + 2 (0.1) = 1.81 (0.7) + 3 (0.2) + 2 (0.1) = 1.51 (0.7) + 2 (0.2) + 3 (0.1) = 1.470

اسلاید 70: د) درخت جستجوی دودویی بهینه(brute force)در این مساله به ازای هر x، تمامی درخت‌های جستجوی دودویی را ایجاد کنیم و به ازای هر درخت، میانگین زمان جستجو را محاسبه کنیم و ...درختی را انتخاب کنیم میانگین زمان جستجوی کمتری دارد.71

اسلاید 71: د) درخت جستجوی دودویی بهینه(brute force)در اینجا نمی‌خواهیم تمامی درخت‌های جستجوی دودویی را ایجاد کنیم ...بلکه شبیه جلسه قبل می‌خواهیم نشان دهیم تعداد آنها از یک کفی بیشتر است.اگر فقط درخت‌های جستجوی دودویی را درنظر بگیریم که دارای عمق n-1 هستند ...نشان می‌دهیم که تعداد این درخت‌ها نمایی است.در اینگونه درخت‌ها (درخت‌های با عمق n-1)، یک راس در ریشه است (سطح صفر) ...راسی که در سطح اول قرار می‌گیرد، می‌تواند سمت چپ و یا سمت راست راس سطح صفر قرار گیرد ...راسی که در سطح دوم قرار می‌گیرد، می‌تواند در سمت چپ و یا راست راس سطح اول قرار گیرد و ...72

اسلاید 72: د) درخت جستجوی دودویی بهینه(brute force)این به آن معنا است که می‌توان ....2n−1 درخت جستجوی دودویی متفاوت با عمق n-1 ایجاد کرد.73

اسلاید 73: د) درخت جستجوی دودویی بهینههدف ادامه مبحث درس این جلسه آن است تا با رویکرد برنامه‌نویسی پویا الگوریتمی کاراتر بدست آوریم.74

اسلاید 74: د) درخت جستجوی دودویی بهینهمسلما هر زیردرخت در هر درخت بهینه خود باید بهینه باشد ...بنابراین اصل بهینگی در این مساله برقرار است.75

اسلاید 75: د) درخت جستجوی دودویی بهینهفرض کنید کلیدهای Keyi تا Keyj در یک درخت بگونه‌ای قرار گرفته باشند که رابطه زیر کمینه شود. که cm برابر با زمان جستجو برای یافتن Keym در درخت می‌باشد.این درخت را درخت بهینه می‌نامیم که در A [i] [j] ذخیره شده است.در درختی که تنها یک کلید دارد، ....چون تنها یک مقایسه برای یافتن آن کلید نیاز است پس ...A [i] [i] = pi76

اسلاید 76: د) درخت جستجوی دودویی بهینهچنانچه مجموعه‌ای از n کلید مرتب در اختیار داشته باشیم، هرکدام از n حالت زیر را می‌توان متصور شد:1) فرض کنید «tree 1» درختی باشد که بهینه است و Key1 در ریشه قرارا گرفته باشد.2) فرض کنید «tree 2» درختی باشد که بهینه است و Key2 در ریشه قرارا گرفته باشد.3) فرض کنید «tree 3» درختی باشد که بهینه است و Key3 در ریشه قرارا گرفته باشد.…n) فرض کنید «tree n» درختی باشد که بهینه است و Keyn در ریشه قرارا گرفته باشد.------------------------------------------------------مسلما ...برای هرکدام از حالت‌های بالا، زیردرخت‌ها نیز بایست بهینه باشند.77

اسلاید 77: د) درخت جستجوی دودویی بهینه78بنابراین اگر A [1] [n] میانگین زمان جستجو در درخت بهینه باشد، بنابراین میانگین زمان جستجو در درخت‌های سمت چپ و راست به صورت زیر است.

اسلاید 78: د) درخت جستجوی دودویی بهینهحال می‌خواهیم میانگین زمان جستجوی tree k را براساس....زیردرخت‌هایش بنویسیم یعنی همان رابطه 79

اسلاید 79: د) درخت جستجوی دودویی بهینهتوجه کنیم که فرض می‌کنیم میانگین زمان جستجوی بهینه را برای هر دو زیر درخت داریم.همانگونه که در این شکل مشهود است برای m ≠ k دقیقا یک جستجوی بیشتر نسبت به زیر درخت‌ مربوطه بایستی انجام پذیرد تا Keym در «درخت k» پیدا شود. این یک مقایسه بیشتر چگونه در میانگین زمان جستجو تاثیر می‌گذارد؟برای Keym ، 1 x pm به میانگین زمان جستجو در «درخت k» اضافه می‌کند.بنابراین میانگین زمان جستجو در «درخت k» برابر خواهد بود با:80

اسلاید 80: د) درخت جستجوی دودویی بهینهکه با رابطه زیر برابر خواهد بود:به دلیل آنکه یکی از این درخت‌های «درخت k» بهینه می‌باشد بنابراین ....میانگین زمان جستجو برای درخت بهینه به صورت زیر خواهد بود:که A [1] [0] و A [n + 1] [n]، صفر درنظر گرفته می‌شوند.81

اسلاید 81: د) درخت جستجوی دودویی بهینههمین بحث‌ها برای Keyi تا Keyj که i < j نیز معتبر است.بنابراین رابطه زیر را خواهیم داشت:82

اسلاید 82: د) درخت جستجوی دودویی بهینهfunction [R,minavg]=optSearchTree(P) n=length(P); A=zeros(n,n); for i=1:n A(i,i)=P(i); R(i,i)=i; end for diagonal=2:n for i=1:n-diagonal+1 j=i+diagonal-1; clear values; for k=i:j values(k)=A(i,k-1)+A(k+1,j); end [A(i,j),k]=min(values); A(i,j)=A(i,j)+sum(P(i:j)); R(i,j)=k; end end minavg=A(1,n);endبا آنالیزی شبیه آنالیز جلسه قبل خواهیم داشت:83

اسلاید 83: د) درخت جستجوی دودویی بهینهمثال) چهار کلید و احتمال‌های آنها را درنظر بگیرید:ماتریس A و R پس از حل به صورت زیر خواهد بود:84

اسلاید 84: د) درخت جستجوی دودویی بهینهکه شکل درخت جستجوی بهینه به صورت زیر خواهد بود:85

اسلاید 85: کوئیز از جلسه قبل)درخت جستجوی دودویی بهینه را با احتمال‌های داده‌شده محاسبه نمایید.CASE (.05)ELSE (.15)END (.05)IF (.35)OF (.05)THEN (.35)86