صفحه 1:
صفحه 2:
کونیز از جلسه قبل)
در کامپیوتری برای ضرب استراسن فرایند تقسیم نمونهای به اندازه ۲۱ به
نمونههای کوچکتر. بارگذاری در پشته. فراخولنی از آن. جمعها و تفریقها
همگی 5ل| 12/72 طول میکشد. چنانچه با الگوریتم استانداردی 5 773
ضرب دو ماتریس با ابعاد 11 >« 11 طول بکشد, حد آستانهای بیابید كه بهتر
است از الگوریتم استاندارد به جای الگوریتم استراسن استفاده کنیم. آیا در
این جل حد آنبتانه واحدی وچودد۱ <*
as] _ ۳ aa 7 ۳ ۳
C22 021 2 bay bee رده
1 +422) (b11 + B22)
21 — 11) (bur + O12)
‘mz = (ax2 ~ 029) (bas + 622).
ama + rts ودع تین
ma + ma my +1mg — m2 +me
صفحه 3:
Dynamic) by, برنامه نویسی
(Programming
یادآوری: روش تقسیم و حل برای محاسبه جمله 8 ام فیبوناجی
روش تقسیم و حل. روشی بالا به پایین است.
#اين روش در مسائلی مانند مرتب سازی ادغامی جواب میدهد چراکه نمونههای
کوچکتر به مرتبط نيستند.
#ولی در محاسبه جمله (ام فیبوناجی, نم
©
صفحه 4:
برنامه نویسی پویا
برنامه نویسی پویا از این نظر که نمونه به نمونههای کوچکتر تقسیم میشود. مشابه
روش تقسیم و حل است ولی
۱- ابتدا نمونههای کوچکتر را حل میکنیم
۲- نتایج را ذخیره میکنیم و
۳- بعدا هرگاه به آنها نیاز شد به جای محاسبه مجدد تنها آنها را بازیابی میکنیم
بنابراین روشی پایین به بالا است
©
صفحه 5:
برنامه نویسی پویا
مراحل بسط یک الگوریتم برنامه نویسی پویا:
۱- ارائه یک ویژگی بازگشتی برای نمونهای از مسئله
۲- حل مسئله به شیوه پایین به بالا با حل نمونههای کوچکتر
©
صفحه 6:
الف) ضریب دوجملهای
(Pao oa for0<k<
kk] 2۱-8 ON S*S"
5 1 1: ۰0 0۲ ۶
(0 O<k<n
صفحه 7:
الف) ضریب دوجملهای
حل با استفاده از روش تقسیموحل:
function [result]=binCoef(n,k) يسم حدم
if (k==0 || k==n) 0 ) O<k<n
۸ 1 k=0 or k=n
result=1;
else
result=binCoef(n-1,k-1)+binCoef(n-1,k);
end
end
صفحه 8:
الف) ضریب دوجملهای
همانند محاسبه جمله (ام فیبوناجی, این الگوریتم نیز کارایی کمی دارد.
binCoef(n-1,k) , binCoef(n-1,k-1) su. هر دو نياز ب
binCoef(n-2,k-1)
دارند و این نمونه در هر فراخوانی بازگشتی به صورت جداگانه محاسبه میشود.
نتیجه
صفحه 9:
الف) ضریب دوجملهای
حل با روش يويا:
-١ يك ویژگی بازگشتی ایجاد میکنیم
> >1 [ن] لا - تاهج[ - نالا -غ] 8ه
j=0 or j=i 1
۲- مسئله را به صورت پایین به بالا حل میکنیم ..
ناه
©
صفحه 10:
الف) ضریب دوجملهای
۱ a
حل با روش يويا: ا عمسم
1234 یک ویژگی بازگشتی ایجاد میکنب ر -۱
۲- مسئله را به صورت.
يايين به بالا حل مىكنيم:
0
1
1
1
1
1
Ronse
ene
61-111 [1 -ز[1 -8
i BIN)
صفحه 11:
fe
الف) ضریب دوجملهای
حل با روش پویا:
function [result]=binCoef2(n,k)
[زا[۱ - :| ۸+(۱ - ز(1 - | و ۶
bave{ ino o jn
B(i,j)=B(i-1,j-1)+B(i-1,));
end
end
end
result=B(n,k);
end
تمرين: تابع فوق را به كونهاى تغيير دهید که اجرای آن در ۱۷3*120 صحیح باشد ©
صفحه 12:
الف) ضریب دوجملهای
پیچیدگی محاسباتی و مرتبه آن:
Pee fees =]
)
for i=1:n
for j=1:min({ik])
end
end
(۰+ ۸
times
(+)
7-۸
(۶ 6)۸(
1+ 2+94 +۰. 1 + )
)(k
mies 1( ek
©
صفحه 13:
الف) ضریب دوجملهای
تمرین:
مسئله ضریب دو جملهای را با برنامهنویسی پوبا با آرایه یک بعدی حل
كنيد
03
صفحه 14:
كوئيز از جلسه قبل)
برای یافتن ضریب ام دوجملهای رابطه زیر برقرار yee ( 0 (
۵ ۰-1
O<k<n +
k ۸-1 | ب 0
1 k=0 or k=n
الف) ویژگی بازگشتی ارائه دهید که ضریب >ام با روش برنامه نویسی پویا
بدست آید.
ب) تابع متناظر با ویژگی بازگشتی در بخش الف را بنویسید
صفحه 15:
مسائل بهینه سازی
در ریاضیات و علوم کامپیوتر مساله بهینهسازی به صورت زیر تعریف میشود:
مسالداى است كه در آن به دنبال يافتن بهترین راه حل در بین..
ای RAS, LOS سب
این مسائل باتوجه متفیرهای موثر در حل مسئله به دو گروه زیر تقسیم میشوند:
مساله بهینهسازی پیوسته -متغیرهای پیوسته
مساله بهینهسازی ترکیبی «متغیرهای گسسته
صفحه 16:
مسائل بهینه سازی
aS Sie alas
فرم استانداره این مسائل به صورت زیر است: minimize f(x)
subject to gi(r) <0,
A(z)=0, i=1,...,p
f(z): R" +R re
تابع هدفی است که میخواهیم ای را برایش بيابیم که آن را کمینه کند.
محدودیتهایی هستند که به صورت عدم تساوی بیان میشوند. 0 > (ت)بو
محدودیتهاین هستند که به صورت فناوی h(x) =0 SIF age gle
صفحه 17:
مسائل بهینه سازی
مسائل بهینهسازی ت رکیبی
مانند ....
مساله یافتن کوتاهترین مسیر بین دو شهر
اين مسائل به صورت چهارتایی fy IM, Q) و) بیان میشوند که ...
D مجموعه ن_مونهها لستمانند..
مجموعه شهرها به صورت دوبهدو
»اللىوكه عضو | لستوا در نظر بكيريد مانند...
(یزد و کرمانشاه)
(()۲ مجموعه رلم حلایم مکن بلعلیر26 لستمانند...
مسیرهای مختلف جادهای بین این دو شهر
صفحه 18:
مسائل بهینه سازی
مسائل بهينهسازى ق ركيبى, dL f, m, Q)
فرض كنيد كه ل[. يكى از راه حلهاى ممكن باشد مانند...
يزد-ابركوه-اصفهان-بروجرد-كنكاور-كرمانشاه
(X,Y) تابعیلستکه لندازه /ا به ازلىكا كه معمولاعدهىم تب طستوا
sib fe
J) تابعهدفلستکه معمولایا ۲۱ و یا ۲30 لست
هدف در اين مسائل بهینهسازی آن است تا .
براى هر 26 ..
بهينهترين راه حل (ز) با توجه به تابع هدف را بيدا كنيم.
صفحه 19:
حل مسائل بهینهسازی ترکیبی با برنامهنوبسی پویا
برای حل مسائل بهینهسازی ترکیبی روشهای مختلفی وجود دارد که با
رویکردهای حل آنها با روشهای برنامهنویسی پویا. حریصانه. عقبگرد و
شاخوحد انشا.. در طول ترم آشنا خواهیم شد.
مسائل بيهينه سا زى تركيبى اى را مىتوان با برنامه نويسى يويا حل
كرد به شرط آنكه
اصل بهینگی در مورد آن برقرار باشد
صفحه 20:
حل مسائل بهینهسازی ترکیبی با برنامهنوبسی پویا
(Principle of Optimality) i. ol
مسالهای شرایط اصل بهینگی را دارد
چنانچه در آن مساله vn
زیر راهحلهای یک راهحل بهینه برای هر نمونه مساله ...
خودشان راهحلهای بهینه برای زیرمسائلی متناظر باشند.
صفحه 21:
حل مسائل بهینهسازی ترکیبی با برنامهنویسی پویا
مثال:
آیا شرایط بهینگی در مساله کو تاه ترین مسیر برقرار است؟
روش بررسی ...
اگر برای مساله کوتاهترین مسیر از هر 8 به هر أای» ..
۵۵و رلمحل هیثه پاش
در اینصورت هر بخش [۱ 0 ۱ در اين راهحل بهینه ...
خود را حل بهینه برای کوتاهترین مسیر از ۱6 به [ا مىباشد ...
چراکه اصلا ممکن نیسث بخشی از راهحل کوتاهترین مسیر نباشد ولی کل راه حل
بهینه گردد.
صفحه 22:
حل مسائل بهینهسازی ترکیبی با برنامهنوبسی پویا
مثال:
همان مساله قبلی را به جای کوتاهترین مسیر, طولانیترین مسیر ساده
درنظر بگیرید.
مسیر ساده: مسیری که هیچگاه دوبار از یک راس نگذرد.
حالا چرا مسیر ساده ؟
اصل بهینگی برقرار است؟
آیا نمیتوان همان توجیه کوتاهترین مسیر را اینجا نیز مطرح کنیم؟
امكان دارد بين دو راس ميانى طولانىترين مسير سادهاى وجود داشته باشد كه اكر
طولانیترین مسیر مساله اصلی بخواهد از همان بگذرد دیگر ساده نشود يعنى
مجبور است از یک راس دوبار بگذرد.
صفحه 23:
حل مسائل بهینهسازی ترکیبی با برنامهنوبسی پویا
به مثال زیر توجه کنید:
طولانیترین مسیر از ۷1 به ۷/4 ....
[۷4 ,۷2 ,۷3 ,۷1] هست ولی ...
طولانیترین مسیر از 1 به 3 دیگر . 2 ©
[۷3 ,۷1] نیست بلکه ..
[۷1,۷2,۷3] است.
صفحه 24:
ب) الگوربتم فلوید برای بافتن کوتاهترین مسیر در گراف
نمایش یک گراف وزندار جهتدار در شکل زیر آمده است:
صفحه 25:
ب) الگوربتم فلوید برای بافتن کوتاهترین مسیر در گراف
چرخه: مسیری از یک راس به خود آن راس
1
کنر
3
وسميو ساده يرق #دعيجكاة: دوبار از یک: رای تگذرد رات
0-0
طول مسير: حاصلجمع وزن يالهاى مسير و اكر يالها
وزن نداشتند برابر با تعداد یالها در مسیر
صفحه 26:
ب) الگوربتم فلوید برای بافتن کوتاهترین مسیر در گراف
با اين الكوريتم مى خواهيم كوتاهترين مسير بين هر دو كره
را بددست بياوريم.
يك الكوريتم واضح:
تعیین طول همه مسیرها برای هر راس از آن راس به همه رئوس
دیگر
nx (n-1)4n-2)« «4 =n!
صفحه 27:
ب) الگوربتم فلوید برای بافتن کوتاهترین مسیر در گراف
یک گراف وزندار حاوی ۲۱ راس را با آرایه ۷۷ نشان میدهیم:
‘weight on edge _ if there is an edge from »; to v;
if there is no edge from vj to vj 00 ¢ <[ن] W [i
0 ifi=j
صفحه 28:
ب) الگوربتم فلوید برای بافتن کوتاهترین مسیر در گراف
در این الگوریتم. در نهایت میخواهیم ماتریس 2 را که
دربرگیرنده کوتاهترین مسیر بین هر دو گره است را پیدا کنیم
صفحه 29:
ب) الگوربتم فلوید برای بافتن کوتاهترین مسیر در گراف
Do LiL] )| برلبر طولكوتامترينمسيرىقرار ميههيم كه ألا را به [لا
وصرميكد و فقطهماز رلسجائموجود در مجموعه {V1,V2,...,VK} 4
[v2, vs] = 00 طاوت! - زو || )جر
minimum(length [v2, v5), length[v2, vr, vs]) =]5[ ]2[ هو
= minimum(oo, 14) = 14
D®) (2) [5] = Do (2] [5] = 14 {For any graph these are equal because a}
{shortest path starting at v2 cannot pass }
{through v2.}
D®) [2] 5] = ام [2] [5| = 14 {For this graph these are equal because}
{including vs yields no new paths}
© {from v2 to vs.}
صفحه 30:
ب) الگوربتم فلوید برای بافتن کوتاهترین مسیر در گراف
بنابراین برای پیداکردن 2 بایستی به دنبال راه حلی باشیم که ...
0 را از 20 به دستبيلوييم
همانكونه كه در جلسه قبل بيان شد در برنامه نويسى يويا بايد ابتدا ...
ويزكى بازكشتى بنويسيم كه
9 را از (1203 بسدستتيسيلورد.
برنامهاى بنويسيم كه مساله را به صورت بايين به بالا حل كند. يعنى در برنامه ...
»ا رالمبتنا صفر قرار ههيمو تا 7الميزفرلين را تكرار كنيم
ار 1(
T 1
© 11 D
صفحه 31:
ب) الگوربتم فلوید برای بافتن کوتاهترین مسیر در گراف
گام اول: ویژگی باز گشتی بنویسیم که 4 را از (21] بدست
بیاورد.
برای حل این گام میتوانیم دو حالت را در نظر بگیریم:
حالت اول: ...
استفاده از راس ام در مرحله alk سب کمتاهترشددن مسب نم شووم
راز 2 زان 0و
حالت دوم: ..
استفاده از راس >لام سيب > لقنت يض ممصو راد وطس Astoestpatn tm vio
و
‘A shortest path from vito vusing A shortest ee from veto yusing
nly vertices in (Yves. Yq) Only Vetices in {¥.Yp 5 Vad
صفحه 32:
ب) الگوربتم فلوید برای بافتن کوتاهترین مسیر در گراف
گام اول: ویژگی باز گشتی بنویسیم که 4 را از (21] بدست
بیاورد.
حالت دوم: ...
استفاده از راس ام سبب کوتاهترشدن مسیر میشود.
از آنجایی که ۷۷ نمی اند راس میانی در زیر مسیرها از ۷ به ۷ و همچنین از
به [۷ باشد بنا
دز اين مسیرها تنها از مجموعه رئوس (۷1,...,۷/۷-1] به عنوان رئوس میانی
مق صش DW) fi {j] =DEY fi] KADER” [hem
صفحه 33:
ب) الگوربتم فلوید برای بافتن کوتاهترین مسیر در گراف
بنابراین چون حالتهای ما از اين دو حالت خارج نیست بنابراین ...
حالتی که کمتر میشود درنظر گرفته میشود ..
۳۱۱۸ ۴ رن رن ضوع (زززن هار
اس
Case 1 Case 2
صفحه 34:
ب) الگوریتم فلوبد برای بافتن کوتاهترین مسیر در گراف
DO [2] [4] = minimum (D® (2) [4] D© (2 [1] + )۵(۱۵(
= minimum(2, 9+1) =2
DC) {5} [2] = minimum ( D0 رم زم (5) [1]+ D® [1] 2) )
= minimum (oo, 3+1)=4
D [5] [4] = minimum (vo [5] [4D [5] (+٩ [1] [4] )
= minimum(oo, 3+1) =4
©
صفحه 35:
ب) الگوربتم فلوید برای یافتن کوتاه ترین مسیر در گراف
بعد از اينكه كل آرايه DY محاسبه شد سپس آرایه Ale Di?)
میشود.
minimum (po {5} [4]: D™ [5] [2]+ DO) [2] ial) ی و ری هار
= minimum(4, 4+2)=4
صفحه 36:
کوئیز از جلسه قبل)
الف) اصل بهینگی در برنامهنویسی پویا چیست؟
ب) آیا این اصل در مساله یافتن طولانیترین مسیر ساده در گراف برقرار
است؟ پاسخ خود را با مثالی توضیح دهید.
صفحه 37:
۱ RIF)
{j) = minimum (pe) اناما ۷۱۳۲۲ 7۳ ,زان
fi)
0 يي
ب) الكوريتم فلويد براى يافتن كوتاهترين مسير در كراف
function [D,P]=floyd(W)
n=length(W);
D=zeros(n,n,n); D(0,:,:)=W;
for k=
for
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
end
end
pi
صفحه 38:
۳*۱ خر تتم زا( aly), DE lla + DS")
ب) الگوربتم فلوید برای بافتن کوتاهترین مسیر در گراف
اگر بخواهیم به جای آرایه سهبعدی با یک آرایه دوبعدی الگوریتم را بنویسیم ...
چه مشکلی پیش میآید؟ ...
امکان دارد در دور کاامی مقدار [2]11]1 يا [[][16](آاى تغيير كند و ما دیگر در
همان دور كام نتوانيم به مقادير دور 1->ام آنها دسترسی پیدا کنیم.
نشان میدهیم که این دو مقدار در دور ام هیچگاه تغییر نمی کنند ...
D{i) [k] = minimum (D [i] [k) , D [i] [k] + D [k] (+
D{k] (j] = minimum (D [k} {j] , D (k] [k] + D [k] [7]).
©
صفحه 39:
ب) الگوربتم فلوید برای بافتن کوتاهترین مسیر در گراف
جاب کردن کوتاهترین مسیر
ماتریس [][۳]1 را به این صورت تعریف میکنیم:
چنانچه راس میانی در کوتاهترین مسیر از ۷ به [۷ وجود نداشته باشد.
بزرگترین اندیس راس میانی: چنانچه حداقل یک راس میانی در کوتاهترین
مسیر وجود داشته باشد.
if ((D(i,k)+D(k,j)<D(i,j)))
P(i,j)=k;
صفحه 40:
ب) الگوربتم فلوید برای بافتن کوتاهترین مسیر در گراف
function [0,P]=floyd(w)
سس
D=W;
P=zeros(n,n);
مره
elena
forjean
if (D(i,k)+D(k,j)<D(i,)))
Dii, i,k) +D(k,j);
P(i,j)=k;
shee
)باه
5
۳
ena
end
صفحه 41:
ب) الگوربتم فلوید برای بافتن کوتاهترین مسیر در گراف
چنانچه الگوریتم گفتهشده بر گراف زیر اعمال شود. ماتریس ۳ محتوایی برابر
مقدار زیر خواهد داشت.
صفحه 42:
ب) الگوربتم فلوید برای بافتن کوتاهترین مسیر در گراف
مر ین: تابعی با نام 0۳۱۳۲۳۵ بنویسید كه با دادن أ و ل انديس
راسهای واقع در کوتاهترین مسیر بین این دو راس را با رویکرد تقسیموحل چاپ
کند.
فرض کنید P به صورت 01001 تعریف شدهاست.
پیچیدگی (n3)""3 بتم فلوید:
صفحه 43:
کونیز از جلسه قبل)
در گراف زیر با الگوریتم فلوید. كوتاهترين مسير بين هر دو راس را
بدست آورید.
در هر كام Dk (k=0...n) را نشان ده
صفحه 44:
ج) ضرب زنجیرهای ماتریسها
ظرب چهار ماتریس زیر را درنظر بگیرید:
A x Bx GC x D
20x2 2x30 30x12 12x8
ابعاد هر ماتریس در زیر آن نشان داده شده است.
اپراتور ضرب ماتریسها ویژگی انجمنی (2550131/۷6) دارد.
ویژگی انجمنی به این معنا است که ترتیب ضرب در نتیجه حاصل تاثیری ندارد.
برای مثال (() 8) ۸ و «(0)) 2۸8 هر دو نتیجه یکسانی دارند.
چهار ماتریس را با پنج ترتیب متفاوت میتوان در هم ضرب کرد.
هر ترتیب ضرب تعداد عملیاتهای ضرب پایهای متفاوتی خواهد داشت.
صفحه 45:
ج) ضرب زنجیرهای ماتریسها
براى اين ينج ماتريس تعداد عملیاتهای پایهای ضرب آورده شده است.
Ax Bx € x 2
20x2 2x30 30x12 12x8
A(B(CD)) 30x 12x8+ 2x30x 8+20x 2x8= 3,680
AB)(CD) 20x 2x 30+30x 12x 8+20x30x8= 8,880
A((BC)D) 2x30x12+ 2x12x 8+20x 2x8= 1,232
((AB)C)D 20x 2 x 30 + 20 x 30 x 12+ 20 x 12 x 8 = 10,320
(A(BC))D 2x 30x 124+20x 2x 12420x12x8= 3,120
سومین ترتیب از این نظر که تعداد عملیاتهای ضرب پایهای کمتری در آن صورت
مىيذيرد بهينه است. ©
صفحه 46:
ج) ضرب زنجیرهای ماتریسها
در اين مساله به دنبال آن هستیم ترتیب ببهینه ضرب ٩ ماتریس را بدست
آوریم
کم
تعداد عملیات پایهای ضرب کمتری در آن صورت پذیرد.
صفحه 47:
ج) ضرب زنجیرهای ماتریسها
اين مساله به صورت جهارتايى (© م173 م4 و بیان میشوند که ..
1 مجموعه نموندها است. در اينجا ...
مجموعه حاصلضرب ماتریسهای مختلف با ابعاد و ۱ های مختلف
كالاىكه عضو | لستوا دينظر بكيريم مثلا..
يك نمونه از حاصلضرب ماتريسها مانند مثال اسلايد قبل
(7)06 مجموعه رلد حلهاوممكراز ويك إنجمنوضربلين:-مونه لست
با فرض اینکه .یکی از اين راه حلها باشد.
,66 113 بیانگر تعداد ضرجایپایه لست
و تابع هدفلستكه در لينجا 111117 ميياشد
صفحه 48:
ج) ضرب زنجیرهای ماتریسها
الگوربتمی که تمام /اها را به ازای هر 6 درنظر میگیر
(brute force)
در این مساله بهینه سازی بياييم و تمامى ترتیبهای ممکن را ایجاد کنیم. ...
در هر ترتیب تعداد ضربهای پایه را بشماریم و ..
ترتیبی را انتخاب کنیم که کمترین تعداد ضربهای پایه را دارد.
صفحه 49:
ج) ضرب زنجیرهای ماتریسها
الگوریتم :brute force
فرض کنید با تعداد ترتیبهای مختلفی باشد که ۲ ماتریس م2 ,... ,يك ,للم
را در هم میتوان در هم ضرب کرد.
خانوادهای از ترتیبها میتواند به این صورت باشد:
1-1
orders.
غير از اين خانواده. گروهی دیگر را هم میتوان درنظر گرفت که ..
م۸ آخرینماتریسیبساشد که ضربمیود.
صفحه 50:
ج) ضرب زنجیرهای ماتریسها
بنابراين»
tn > tn-1+tn-1= 2tn-1
واز آنجاييكه 1 > ي اين رابطه بازكشتى به صورت زير حل مىشود.
فا
صفحه 51:
ج) ضرب زنجیرهای ماتریسها
آيا اصل بهينكى در اين مساله برقرار است؟
بله. جراكه جنانجه ترتيب بهينه براى ضرب !١ ماتريس اكر داشته باشيم در اين
صورت. هر زیر راه حل آن مسلما خود راه حل بهینه برای ماتریسهای موجود در
زیر راه حل میباشد.
به عنون مثال چنانچه راه حل زیر ترتیب بهینه برای ضرب ماتریسهای ۸1 تا
6 باشد.
« (46 (45 (۸۸ (وشوش)))) ر۸
(A2A3) Ag
باید ترتیب بهینه برای ضرب ماتریسهای ۸٩2 تا ۸۸4 باشد.
۳
صفحه 52:
ج) ضرب زنجیرهای ماتریسها
برای آغاز حل مساله ابتدا ساختاری را تعریف میکنیم که بر اساس آن
بتوانیم ویژگی بازگشتی را تعریف کنیم:
فرض کنید در ماتریس [/] [/] ۷ ۱۰ برابر با حداقل تعداد ضربها
برای ضرب ماتریسهای ۸۵ تا [(/ باشد (چنانچه > باشد).
بنابراین ...
۷ ]/[ ]/[ >0
صفحه 53:
ج) ضرب زنجیرهای ماتریسها
ترتیب بهینه برای ضرب شش ماتریس ۸۵1 تا ۸۵6 در یکی از پنج حالت زیر
قرار میگیرد.
ete ۱
2.(A,A,) (AAAgAe)
3.(A,A,As) (A,AsAg) al A
AMAA AGAg) (AgAs) |
5.(A,A,A3A,As) (Ag)
M(1)[6] minimum ( M{1)[k]+M[k + 1][6}+d, d..d,)
lores
صفحه 54:
ج) ضرب زنجیرهای ماتریسها
ژ > ان,ب(رل ميك رفج(ق(۱ + ۲+ [ه( لسن [زا(] ۸
و وک دک
دوه
M{illi] =0
آيا ویژگی بازگشتی بدست آمد؟
شبیه هر حل با برنامه نویسی پویا بعد از بدست آوردن ویژگی بازگشتی بایستی
ترتیب اجرایی در برنامه نویسی پیدا کنیم تا مساله از پایین به بالا حل شود.
يعنى بايد مشخص کنیم که المانهای ماتریس ۷ به چه نحوی مقدار دهی شود تا
در نهایت...٩
[۷]1[]01 بدستلید
صفحه 55:
صفحه 56:
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 Mllj]= minimum M{i](6] +A و کنر( سب بل > j
m=M(1,n); Mili] =0
en"
صفحه 57:
7 ج) ضرب زنجیرهای ماتریسها
700 - by (n= diagonal + 1)x (i+ diagonal - i)
diagonal=2
3
TQ) = 2 (n= diagonal + 1) x (diagonal)
diagonal=2
تمرین: نشان دهید که حاصل این سیگما برابر با رابطه زیر است.
for diagonal=2:n
_ ۳-10۶1 و for i=1:n-
6 diagonal+1
j=i+diagonal-1;
for k=i:j-1
end
end
end
صفحه 58:
ج) ضرب زنجیرهای ماتریسها
Al x Ar x يه x Ay x As x Ae
5x2 2x3 3x4 4x6 6x7 7x8
The array P
Ay (A2A3AaA5 Ao) ۰
(ArA3 Ass) Ao:
A, ((A2A3414s) Ao) ,
Ay ((((AzAg) Aa) As) As)
صفحه 59:
ج) ضرب زنجیرهای ماتریسها
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(')');
end
end
صفحه 60:
کوئیز از جلسه قبل) ترتیب و هزینه ضرب بهینه چهار ماتریس ,(10*4) ,۸۵
(۸,)20*2 :(5*20) ۸ :(4*5 )۸ بدست آورید.
دو ماتریس Pg M را نشان دهید و بر اساس ماتریس 0 ضرب بهینه را براساس
تابع زیر نشان دهید.
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(')');
end
صفحه 61:
د) درخت جستجوی دودویی بهینه
خت جستجوی دودویی» درختی دودویی از آیتمها است.
آیتمها معمولا کلیدهایی هستند که ...
از یک مجموعه مرتب بدست میآیند یعنی ..
برای آیتمها اپراتورهای کوچکتر بزرگتر و مساوی وجود دارد
مانند مجموعه کدهای ملی» مجموعه نامهای خانوادگی
در این دزخت:
هر راس, شامل یک کلید میشود
کلیدهایی که در زیردرخت سمت چپ هر راس وجود دارند. کوچکتر از کلید آن راس
کلیدهایی که در زیردرخت سمت راست هر راس وجود دارند. بزرگتر از کلید آن راس
صفحه 62:
درخت جستجوی دودویی بهینه
© © © © جد
صفحه 63:
د) درخت جستجوی دودویی بهینه
عمق هر راس در درخت برابر است
تعداد يالهايى كه در مسير واحد ريشه به آن راس وجود دارد.
به عمق. همچنین سطح نیز گفته میشود.
عمق درخت. .
بيشينه عمق راسهاى درخت مىباشد.
درخت دودویی لاس است. اگر -
تفاوت عمق دو زيردرخت هر راس ب
ز یک نباشد.
صفحه 64:
۵) درخت جستجوی دودویی بهینه
هدش آن است تا کلیدها در درخت جستجویی دودویی به گونهای
سازماندهی شوند که ..
میانگین زمان برای پیداکردن کلیدها کمینه شود.
درختی که با اين رویکرد سازماندهی شود. بهینه گفته میشود.
اگر همه کلیدهای با احتمال یکسان کلید جستجو باشند ...
بین این ذو درخت کنامیک بهینه است؟
صفحه 65:
د) درخت جستجوی دودوبی بهینه
مساله بهینهسازی که در این جلسه مد نظر است. ...
کلیدها دارای احتمال جستجوی یکسان نيستند.
OL درخت جستجوی دودویی را درنظر بگیرید که کلیدها نام افراد میباشد.
در این درخت باتوجه به نام افراد به رکورد اطلاعاتی آنها دست مىيابيم.
TOM oye بيشتر از نام «013ا15لا» عمومى است. بنابراين احتمال بيشترى
به آن نسبت داده میشود.
برای آنکه میانگین زمان جستجو کمینه شود بایستی تعریفی از زمان جستجو ارائه
شود.
صفحه 66:
د) درخت جستجوی دودویی بهینه
زمان جستجو: تعداد مقایسههایی که توسط تابع جستجو برای یافتن هر
کلید صورت میپذیرد.
هدف:
یافتن درخت جستجوی دودویی است که ...
میانگین زمان جستجو کمینه گردد.
صفحه 67:
د) درخت جستجوی دودویی بهینه
اين مساله به صورت جهارتايى (/© م743 و ) بیان میشود که ...
4# مجموعه نمونهها است. در اینجا ...
مجموعه کلیدها با احتمال جستجو برای هر کلید
رکه عضو | لسیا دردظر ب قرم سيل
یک تعدادی مشخص از کلیدها که به هر کلید احتمال جستجویی نسبت داده شده
است.
(6 مجموعه درخهایجستجوودودوییم تنلیتیکه میت ودرنظر گرفتبا
فرضینکه کل یکیاز لینوله حلها باشد
m(x,y) بیانگر میانگیزمانجستجو در درختلا میاشد
J تابعهدفلسنکه در لینجا ۲۲۱0 میاشد
صفحه 68:
د) درخت جستجوی دودوبی بهینه
میتوانيم رابطه زیر را برای زمان جستجوی هر کلسف seats ail
depth (key) + 1,
مثلا در درخت جستجوی دودویی زیر زمان جستجو برای کلید «1[۲5۱02» برابر
depth(Ursula) + 1=2+1=3. © =
6 Co)
© &
©) &)
صفحه 69:
د) درخت جستجوی دودویی بهینه
فرض کنید «۲۱ ۰«( ,..., و6 ,/(6 کلید مرتب شده باشد.
فرض کنید که ,0 احتمالی است که 16 جستجو شود.
چنانچه ,> زمان جستجوی یافتن ,/61/ در هر درخت فرضی باشد.
با توجه به فرضیات باله برای درخت جستجوی دودوبی مفرضء میانگین
زمان جستجو با رابطه زیر محاسبه میشود:
0(
i=l
اين همان مقداری است که به دنبال کمینه کردن آن هستیم.
صفحه 70:
ne Ee
07رصم p2=02, and p3=Ol,
برای این پنج درخت. میانگین زمان جستجو به
صورت زیر محاسبه میشود:
2 ی
و
2.1
3.2 (0.7) + 1 (0.2) + 2 (0.1) =
1.8
4.1 (0.7) + 3 (0.2) + 2 (0.1) =
15 5
5.1 (0.7) + 2 (0.2) + 3 (0.1) =
رت )© 14
صفحه 71:
د) درخت جستجوی دودویی بهینه
(brute force)
در اين مساله به ازاى هر »ا تمامی درختهای جستجوی دودویی را ایجاد کنیم و
... به ازای هر درخت. میانگین زمان جستجو را محاسبه کنیم و
درختی را انتخاب کنیم میانگین زمان جستجوی کمتری دارد.
صفحه 72:
د) درخت جستجوی دودوبی بهینه
(brute force)
... در اینجا نمیخواهیم تمامی درختهای جستجوی دودویی را ایجاد کنیم
بلکه شبیه جلسه قبل میخواهیم نشان دهیم تعداد آنها از یک کفی بیشتر است.
۲-1 اگر فقط درختهای جستجوی دودویی را درنظر بكيريم كه داراى عمق
نشان میدهیم که تعداد اين درختها نمایی است.
... در اینگونه درختها (درختهای با عمق ۲۱-1). یک راس در ريشه است (سطح صفر)
راشیی:که. دررسطلح اول قراردم ی گیرته مي تواند: سمت چپ و با سمت زافترانن: سطح
.. صفر قرار گیرد
راسی که در سطح دوم قرار میگیرد. میتواند در سمت جب و يا راست راس سطح اول
قرار كيرد وام
صفحه 73:
د) درخت جستجوی دودوبی بهینه
(brute force)
... اين به آن معنا است كه میتوان
درختجستجووهودويىمتفايتها عمق1-1 ليجاد كرد. 271
صفحه 74:
د) درخت جستجوی دودویی بهینه
هدف ادامه مبحث درس این جلسه آن است تا با رویکرد
برنامهنویسی پویا الگوریتمی کاراتر بدست آوریم.
صفحه 75:
د) درخت جستجوی دودوبی بهینه
مسلما هر زیردرخت در هر درخت بهینه خود باید بهینه باشد ..
بنابراین اصل بهینگی در اين مساله برقرار است.
صفحه 76:
د) درخت جستجوی دودویی بهینه
فرض کنید کلیدهای ,/(6/ تا ,/۸6 در یک درخت بگونهای قرار گرفته باشند
که رابطه زیر کمینه شود. j
CmPm; >
mai
Gn برابر با زمان جستجو برای یافتن ,,/(6/ در درخت میباشد.
این درخت را درخت بهینه مینامیم که در [] [4] ۸4 ذخیره شده است.
يك مقایسه رای بات Sal SSS سید
B, = 1 1] ۸
صفحه 77:
د) درخت جستجوی دودوبی بهینه
چنانچه مجموعهای از ۷۱ کلید مرتب در اختیار داشته باشیم» plas ye )5 حالت زیر
را میتوان متصور شد:
)١ فرض كنيد «1 ۲6۵6» درختی باشد که بهینه است و 6 در ريشه قرارا گرفته باشد.
۲ فرض کنید «2 ۳66» درختی باشد که بهینه است و 6 در ty, قرارا گرفته باشد.
۲ فرض کنید «3 ۳66]» درختی باشد که بهینه است و و6 در ريشه قرارا گرفته باشد.
0 فرضک نید «(۲ 4۲۳66۵ درختیب اشد که بسهینه لستو ,/(6 در ريشه قرارا گرفته
باشد
برای هرکدام از حالتهای بالاء زیردرختها نیز بایست بهینه باشند.
صفحه 78:
د) درخت جستجوی دودوبی بهینه
بنابراین اگر [1/] 11.] ۸4 میانگین زمان جستجو در درخت بهینه باشد. بنابراین
میانگین زمان جستجو در درختهای سمت چپ و راست به صورت زیر است.
For each key, there is one
additional comparison at
the root. ۱
‘Average search time Average search time
in this subtree inthis subtree
و ۸116-11
is Alk +1][n]
صفحه 79:
د) درخت جستجوی دودویی بهینه
For each key, there is one
addtional comparison at
the rot |
‘Average search time
inthis subtree
1s Alk +1107)
‘Average search time
inthis subtree
is AUK 1]
حال میخواميم میانگین زمان جستجوی 1 6۲66 را براساس...
زیردرختهایش بنویسیم پعنی همان رابطه
صفحه 80:
م م
عرخت جستجوى دودویی بهینه سميج
22
2
توجه کنیم که فرض میکنیم میانگین زمان جستجوی بهینه را برای هر دو زیر
درخت داریم.
همانگونه که در این شکل مشهود است برای ۸ 7 77/ دقیقا یک جستجوی بیشتر نسبت به زیر
درخت مربوطه بایستی انجام پذیرد تا بم/(۸6 در «درخت » پیدا شود.
این یک مقایسه بیشتر چگونه در میانگین زمان جستجو تاثیر میگذارد؟
براى ,2 6 1 ۰ بم/( به میانگین زمان جستجو در «درخت >» اضافه میکند.
بنابراین میانگین زمان جستجو در «درخت >» برابر خواهد بود باه
۸6-1 + له درجم + pear tes + Pn
كك تشه نت a ee
Average time in Additional time Average time Average time in ‘Additional time
left subtree comparing at root searching for right aubtree ‘comparing at root
root
صفحه 81:
د) درخت جستجوی دودوبی بهینه
که با رابطه زیر برابر خواهد بود:
۷۰ + | [1 +۸6 + [6-1] [1] ۸
m=1
به دلیل آنکه یکی از اين درختهای «درخت ا» بهینه میباشد بنابراین ...
میانگین زمان جستجو برای درخت بهینه به صورت زیر خواهد بود:
n
All] [x] =minimum( ۸۱() - 1۱(+ ۸+ ۱((( + Ys Pm
احور
که [0] [1] ۸و [0] 11 + 0] 4 صفر درنظر گرفته میشوند.
صفحه 82:
د) درخت جستجوی دودوبی بهینه
همین بحثها برای /(۸6 تا 6 که [ > / نیز معتبر است.
بنابراین رابطه زیر را خواهیم داشت:
P< مه ج(زال۱ Ald[j] = minimum Allie — 1+ Alk-+
Alii] = pi
A{ij[i — 1] and Alj + 1][j) are defined to be 0
صفحه 83:
2 function
[R,minavg]=optSearchTree(P)
n=length(P); A=zeros(n,n);
د) درخت جستجوی دودویی بهینه for
R(i)=i; {Alillj] = minimnon( alte — 1) ala + إن ( 1
end 5
for diagonal=2:n_— fl
for i=1:n-diagonal+ 4 1] and Alj + [ززز۱ def بسب
j=itdiagonal-1; ~
clear values;
for k=i:j
values(k)=A(i,k-
1)+A(k+1,));
end
[A(i,j),k]=min(values); با آنالیزی شبیه آنالیز جلسه قبل
A(i,j)=A(i,j)+sum(P (ij); اهیم داشت:
8 Se
end
end n(n—1)(n+4)
1 تست > (n°)
end
9 minavg=A(1,n);
صفحه 84:
د) درخت جستجوی دودوبی بهینه
مثال) چهار کلید و احتمالهای آنها را درنظر بگیرید:
wb af =e 5
وحه ودس و وحلسم
Wally
Key(4]
4
Zz
4
Ralph
Key(3]
Isabelle
Key|2)
Don’
Key(1]
صفحه 85:
د) درخت جستجوی دودوبی بهینه
که شکل درخت جستجوی بهینه به صورت زیر خواهد بود:
Wally
Key(4]
Ralph
Key([3}
Isabelle
Key|2)
Isabelle
Don
Key[I]
صفحه 86:
کوئیز از جلسه قبل)
درخت جستجوی دودویی بهینه را با احتمالهای دادهشده محاسبه
CASE (.05)
ELSE (.15)
END (.05)
IF (.35)
OF (.05)
THEN (.35)
