Algorythm Design (5)

‫روش حریصانه‬ ‫‪Greedy Method‬‬ ‫طراحی الگوریتم ها ‪ -‬دانشگاه فردوسی مشهد ‪ -‬صمد‬ ‫پایدار‬

‫مطالب مورد بحث‬ ‫‪‬‬ ‫‪‬‬

‫مقدمه‬ ‫بررسی چند مساله نمونه‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫کوله پشتی غیر صفر و یک‬ ‫زمانبندی بهینه اجرای برنامه ها‬ ‫درخت پوشای مینیمم‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬ ‫‪‬‬

‫الگوریتم ‪Prim‬‬ ‫الگوریتم ‪Kruskal‬‬

‫کوتاهترین مسیرها از مبدأ واحد‬ ‫فشرده سازی با استفاده از کد ‪Huffman‬‬

‫روش حریصانه‬

‫‪2‬‬

‫مقدمه‬ ‫‪‬‬

‫در مسائلی که به این روش حل می شوند‪ ،‬معمول‪:‬‬ ‫‪‬‬ ‫‪‬‬

‫ورودی مساله شامل مجموعه ای از عناصر است‪.‬‬ ‫خروجی مساله شامل مجموعه ای از عناصر است که بیشتر مواقع‪،‬‬ ‫زیرمجموعه ورودی مساله می باشد‪.‬‬ ‫‪‬‬

‫‪‬‬

‫موضوع بهینگی مطرح است‪.‬‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫علیرغم استفاده از لفظ مجموعه‪ ،‬ممکن است ترتیب عناصر مجموعه جواب‪،‬‬ ‫مهم باشد‪.‬‬ ‫یعنی حل مساله‪ ،‬مستلزم انتخاب زیرمجموعه ای از مجموعه عناصر ورودی‬ ‫می باشد که تابع هدف مساله را بهینه می نمایند‪.‬‬

‫جواب را می توان بصورت مرحله به مرحله بدست آورد‪) .‬در هر‬ ‫مرحله یک مولفه جواب را بدست آورد(‬

‫مثال‪ :‬خرد کردن اسکناس‬

‫روش حریصانه‬

‫‪3‬‬

‫مقدمه‬ ‫‪‬‬

‫کلیات روش حریصانه‬ ‫‪‬‬ ‫‪‬‬

‫در ابتدا مجموعه جواب را تهی در نظر می گیریم‪.‬‬ ‫بطور مرحله به مرحله عمل می کنیم‪ .‬در هر مرحله‪:‬‬ ‫‪‬‬

‫‪‬‬

‫از بین عناصر ممکن که می توانیم بعنوان عنصر بعدی مجموعه‬ ‫جواب انتخاب کنیم‪ ،‬بهترین عنصر را در نظر می گیریم‪.‬‬ ‫بررسی می کنیم آیا با انتخاب آن مولفه‪ ،‬امکان رسیدن به جواب‬ ‫وجود دارد یا خیر‪.‬‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫اگر بله‪ :‬آن مولفه را به مجموعه جواب اضافه می کنیم‪.‬‬ ‫اگر خیر‪ :‬آن مولفه را به مجموعه جواب اضافه نمی کنیم و آن را برای‬ ‫همیشه کنار می گذاریم‪.‬‬

‫با افزودن هر عنصر به مجموعه جواب‪ ،‬بررسی می کنیم اگر جواب‬ ‫مساله حاصل شده است‪ ،‬جواب بدست آمده بهینه خواهد بود و کار‬ ‫تمام است‪.‬‬ ‫‪‬‬

‫بنابراین با بدست آوردن اولین جواب کار تمام می شود‪.‬‬

‫روش حریصانه‬

‫‪4‬‬

‫مقدمه‬ ‫‪‬‬

‫یک الگوریتم حریصانه باید بطور صریح یا‬ ‫ضمنی دارای این اجزا باشد‪:‬‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬ ‫‪‬‬

‫قسمتی برای انتخاب مولفه بعدی جواب از بین‬ ‫نامزدهای ممکن‬ ‫قسمتی برای تعیین اینکه آیا با انتخاب مولفه جدید‬ ‫)بهمراه عناصری که تا کنون انتخاب شده‬ ‫اند(امکان رسیدن به جواب وجود دارد یا خیر‪.‬‬ ‫قسمتی برای تعیین میزان ارزش مجموعه جواب‬ ‫قسمتی برای بررسی اینکه آیا مجموعه عناصر‬ ‫انتخاب شده‪ ،‬جواب مساله را تولید کرده است یا‬ ‫کار باید ادامه پیدا کند‪.‬‬

‫روش حریصانه‬

‫‪5‬‬

‫مطالب مورد بحث‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫کوله پشتی غیر صفر و یک‬ ‫زمانبندی بهینه اجرای برنامه ها‬ ‫درخت پوشای مینیمم‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬ ‫‪‬‬

‫الگوریتم ‪Prim‬‬ ‫الگوریتم ‪Kruskal‬‬

‫کوتاهترین مسیرها از مبدأ واحد‬ ‫فشرده سازی با استفاده از کد ‪Huffman‬‬

‫روش حریصانه‬

‫‪6‬‬

‫کوله پشتی غیر صفر و یک‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫تعدادی شیء و یک کوله پشتی داریم‪.‬‬ ‫شیء ‪ i‬دارای وزن ‪ wi‬و ارزش ‪ pi‬می باشد‪.‬‬ ‫ظرفیت وزنی کوله پشتی برابر ‪ M‬می باشد‪.‬‬ ‫هدف‪ :‬اشیا را برای قرار دادن در داخل کوله پشتی‬ ‫انتخاب کنیم‪ ،‬بگونه ای که ضمن رعایت ظرفیت وزنی‬ ‫کوله پشتی‪ ،‬مجموع ارزش اشیای انتخاب شده‪،‬‬ ‫ماکزیمم گردد‪.‬‬ ‫امکان انتخاب کسری از هر شیء نیز وجود دارد‪.‬‬ ‫بنابراین از هر شیء ‪ i‬به میزان ‪ xi‬واحد انتخاب می‬ ‫کنیم‪(xi ≤1 ≥ 0) .‬‬ ‫‪‬‬

‫اگر اینطور نباشد‪ ،‬یعنی یا باید یک شیء را بطور کامل‬ ‫انتخاب کنیم یا اصل آن را انتخاب نکنیم‪ .‬در اینصورت‪ ،‬مساله‬ ‫به مساله کوله پشتی صفر و یک تبدیل خواهد شد‪.‬‬

‫روش حریصانه‬

‫‪7‬‬

‫کوله پشتی غیر صفر و یک‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫‪n‬‬

‫بیان ریاضی‬ ‫تعداد اشیا‪n :‬‬ ‫‪xi ≤ 1 ≤ 0‬‬

‫‪i‬‬

‫‪≤M‬‬

‫روش حریصانه‬

‫‪∑p x‬‬ ‫‪i‬‬

‫‪i =1‬‬

‫‪n‬‬

‫‪i‬‬

‫‪∑w x‬‬ ‫‪i‬‬

‫‪maximize‬‬

‫‪subject to‬‬

‫‪i =1‬‬

‫‪8‬‬

‫کوله پشتی غیر صفر و یک‬ ‫‪‬‬

‫حدس‪:‬‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫‪‬‬

‫چون ارزش اشیا تاثیر مثبت دارد و می خواهیم‬ ‫مجموع ارزش اشیای انتخاب شده را ماکزیمم کنیم‪،‬‬ ‫پس بهتر است اشیا را به ترتیب بیشترین ارزش‬ ‫انتخاب کنیم‪.‬‬ ‫چون وزن اشیا تاثیر منفی دارد و می خواهیم کوله‬ ‫پشتی دیرتر پر شود‪ ،‬پس بهتر است اشیا را به ترتیب‬ ‫کمترین وزن انتخاب کنیم‪.‬‬ ‫چون ارزش اشیا تاثیر مثبت و وزن اشیا تاثیر منفی‬ ‫دارد‪ ،‬بهتر است اشیا را به ترتیب بیشترین ‪pi/wi‬‬ ‫انتخاب کنیم‪.‬‬ ‫در هر صورت‪ ،‬کوله پشتی را تا حداکثر ظرفیت پر می‬ ‫کنیم‪ ،‬مگر آنکه اشیا تمام شوند‪.‬‬

‫روش حریصانه‬

‫‪9‬‬

‫کوله پشتی غیر صفر و یک‬ ‫‪‬‬

‫مثال‪ M=20 :‬و ‪n=3‬‬ ‫)‪(p1 , p2 , p3) = (25, 24, 15‬‬ ‫)‪(w1 , w2 , w3) = (18, 15, 10‬‬ ‫حدس مورد‬ ‫استفاده‬

‫جواب‬

‫مجموع وزن اشیای مجموع ارزش‬ ‫اشیای انتخاب شده‬ ‫انتخاب شده‬

‫حدس اول‬

‫)‪(0 ,2/15 ,1‬‬

‫‪20‬‬

‫‪28.2‬‬

‫حدس دوم‬

‫)‪(1 ,2/3 ,0‬‬

‫‪20‬‬

‫‪31‬‬

‫حدس سوم‬

‫)‪(1/2 ,1 ,0‬‬

‫‪20‬‬

‫‪31.5‬‬

‫روش حریصانه‬

‫‪10‬‬

‫کوله پشتی غیر صفر و یک‬ ‫‪‬‬

‫درستی این حدس را باید اثبات کنیم‪.‬‬

‫روش حریصانه‬

‫‪11‬‬

‫کوله پشتی غیر صفر و یک‬ void knapsack(float P[], float W[], float M, float X[], int n) { pwSort(P, W, n); //،‫اشیا را بر حسب نسبت ارزش به وزن‬ ‫نزولی مرتب کن‬

for(int i=0; i
for(int i=0; i
‫روش حریصانه‬

‫کوله پشتی غیر صفر و یک‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫محاسبه مرتبه زمانی‬ ‫ورودی‪ :‬لیست وزن و ارزش اشیای ورودی و‬ ‫مقدار ‪M‬‬ ‫اندازه ورودی‪ :‬تعداد اشیای ورودی یعنی ‪n‬‬ ‫عمل کلیدی‪ :‬مقایسه ‪ [W[i‬با ‪rc‬‬ ‫تابع پیچیدگی‪:‬‬ ‫‪n‬‬ ‫)‪W(n‬‬ ‫=‬ ‫‪O(n‬‬ ‫‪log‬‬ ‫)‬ ‫‪ W(n) = n + W‬‬ ‫)‪(n‬‬ ‫‪pwSort‬‬ ‫)‪WpwSort(n) = O(n logn‬‬ ‫روش حریصانه‬

‫‪‬‬

‫‪13‬‬

‫کوله پشتی غیر صفر و یک‬ ‫‪‬‬

‫‪‬‬

‫الگوریتم منطبق بر الگوی روش حریصانه می‬ ‫باشد‪.‬‬ ‫اثبات درستی‬

‫روش حریصانه‬

‫‪14‬‬

‫مطالب مورد بحث‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫کوله پشتی غیر صفر و یک‬ ‫زمانبندی بهینه اجرای برنامه ها‬ ‫درخت پوشای مینیمم‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬ ‫‪‬‬

‫الگوریتم ‪Prim‬‬ ‫الگوریتم ‪Kruskal‬‬

‫کوتاهترین مسیرها از مبدأ واحد‬ ‫فشرده سازی با استفاده از کد ‪Huffman‬‬

‫روش حریصانه‬

‫‪15‬‬

‫زمانبندی بهینه اجرای برنامه ها‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫تعدادی برنامه با زمان اجرای معلوم موجود است‪ .‬می خواهیم‬ ‫برنامه ها را به ترتیبی اجرا کنیم که زمان متوسط برگشت آنها‬ ‫مینیمم گردد‪.‬‬ ‫زمان برگشت )‪ ،(turnaround time‬مدت سپری شده از زمان‬ ‫تحویل برنامه به کامپیوتر تا پایان اجرای آن می باشد‪.‬‬ ‫ویژگیهای مساله‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫ورودی مجموعه ای از عناصر است )مجموعه زمان اجرای برنامه ها(‬ ‫خروجی مجموعه ای از عناصر است‪ .‬در این مثال تعداد عناصر مجموعه‬ ‫خروجی با تعداد عناصر مجموعه ورودی برابر است و فقط ترتیب عناصر‬ ‫ممکن است متفاوت باشد‪.‬‬ ‫مساله بهینه سازی مطرح است‪ :‬کمینه کردن متوسط زمان برگشت‬

‫روش حریصانه‬

‫‪16‬‬

‫زمانبندی بهینه اجرای برنامه ها‬ ‫‪‬‬

‫‪‬‬

‫احتمال می توانیم در هر مرحله یکی از مولفه های‬ ‫مجموعه جواب را تعیین کنیم‪.‬‬

‫این ویژگیها ‪ ‬مساله به احتمال زیاد به روش‬ ‫حریصانه قابل حل است‪.‬‬

‫روش حریصانه‬

‫‪17‬‬

‫زمانبندی بهینه اجرای برنامه ها‬ ‫‪‬‬

‫مثال ‪ :‬سه برنامه ‪ P1‬و ‪ P2‬و ‪ P3‬با زمان های اجرای ‪8‬‬ ‫زمان‪ 4‬و ‪6‬‬ ‫و‬ ‫متوسط زمان برگشت زمان برگشت زمان برگشت ترتیب اجرا‬ ‫برگشت‬

‫برنامه سوم‬

‫برنامه دوم‬

‫برنامه اول‬

‫‪12.7‬‬

‫‪6+4+8‬‬

‫‪4+8‬‬

‫‪8‬‬

‫‪P 1 P2 P3‬‬

‫‪13.3‬‬

‫‪4+6+8‬‬

‫‪6+8‬‬

‫‪8‬‬

‫‪P 1 P3 P2‬‬

‫‪11.3‬‬

‫‪6+8+4‬‬

‫‪8+4‬‬

‫‪4‬‬

‫‪P 2 P1 P3‬‬

‫‪10.7‬‬

‫‪8+6+4‬‬

‫‪6+4‬‬

‫‪4‬‬

‫‪P 2 P3 P1‬‬

‫‪12.7‬‬

‫‪4+8+6‬‬

‫‪8+6‬‬

‫‪6‬‬

‫‪P 3 P1 P2‬‬

‫روش حریصانه‬

‫‪18‬‬

‫زمانبندی بهینه اجرای برنامه ها‬ ‫مجموع زمان‬ ‫برگشت‬

‫زمان برگشت زمان برگشت زمان برگشت‬ ‫برنامه اول‬ ‫برنامه دوم‬ ‫برنامه سوم‬

‫‪x + y + z 3x + 2y +z‬‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫‪‬‬

‫‪x+y‬‬

‫‪x‬‬

‫ترتیب اجرا‬

‫‪Px Py Pz‬‬

‫از آنجا که می خواهیم میانگین را مینیمم کنیم‪ ،‬پس باید‬ ‫مجموع زمانهای برگشت )‪ (sum‬را مینیمم کنیم‪.‬‬ ‫زمان اجرای برنامه اول ‪ 3‬بار در ‪ sum‬ظاهر می شود و‬ ‫زمان اجرای برنامه دوم‪ 2 ،‬بار و زمان اجرای برنامه سوم‪،‬‬ ‫‪ 1‬بار‪.‬‬ ‫حدس‪ :‬برنامه ها را به ترتیب زمان اجرا‪ ،‬بطور غیر نزولی‬ ‫مرتب کرده و بهمان ترتیب اجرا نماییم‪.‬‬ ‫بدین ترتیب برنامه ای که بیشترین تاثیر را در ‪ sum‬دارد‪،‬‬ ‫برنامه ای خواهد بود که کمترین زمان اجرا را دارد و ‪....‬‬ ‫روش حریصانه‬

‫‪19‬‬

‫زمانبندی بهینه اجرای برنامه ها‬ ‫‪‬‬

‫درستی این حدس را هم باید اثبات کرد‪.‬‬

‫روش حریصانه‬

‫‪20‬‬

‫زمانبندی بهینه اجرای برنامه ها‬ ‫‪‬‬

‫الگوریتم منطبق بر الگوی روش حریصانه‬ ‫{ )‪void optOrder(float P[], float C[], int n‬‬ ‫‪//‬آرایه ‪ P‬زمان اجرای برنامه ها را شامل می شود‬ ‫‪ //‬آرایه ‪ C‬خروجی برنامه است که ترتیب اجرای برنامه ها را‬ ‫مشخص می کند‪.‬‬

‫)‪for (int i=0; i
‫‪21‬‬

‫زمانبندی بهینه اجرای برنامه ها‬ selectMin ‫الگوریتم‬ int selectMin(float P[], int k, int n) { min = P[k]; minIndex = k; for( int i=k+1; i
‫روش حریصانه‬



‫زمانبندی بهینه اجرای برنامه ها‬ ‫‪‬‬

‫محاسبه مرتبه زمانی الگوریتم ‪selectMin‬‬ ‫‪‬‬

‫عمل کلیدی‪ :‬عمل مقایسه‬

‫‪TselectMin(n,i) = n-i-1‬‬ ‫‪T(n, 0) = n-1‬‬ ‫‪T(n, 1) = n-2‬‬ ‫…‬ ‫‪T(n, n-1) = 1‬‬

‫روش حریصانه‬

‫‪23‬‬

‫زمانبندی بهینه اجرای برنامه ها‬ ‫‪‬‬ ‫‪‬‬

‫محاسبه مرتبه زمانی الگوریتم ‪optOrder‬‬ ‫عمل کلیدی‪ :‬عمل انتساب ‪[C[i‬‬

‫‪(n − 1)n‬‬ ‫‪T (n ) = n + ∑ (n − i − 1) = n +‬‬ ‫‪2‬‬ ‫‪i =0‬‬ ‫‪n −1‬‬

‫‪2‬‬

‫‪n n‬‬ ‫‪T(n ) = +‬‬ ‫‪2 2‬‬ ‫‪2‬‬ ‫) ‪⇒ T ( n ) = O( n‬‬ ‫روش حریصانه‬

‫‪24‬‬

‫زمانبندی بهینه اجرای برنامه ها‬ ‫‪‬‬

‫الگوریتم دیگر با مرتبه زمانی بهتر )منطبق بر‬ ‫الگوی روش حریصانه نیست(‬ ‫{ )‪void optOrder2( float P[], float C[], int n‬‬ ‫;)‪C = descendingSort(P‬‬ ‫}‬

‫‪‬‬

‫از آنجا که الگوریتم هایی برای مرتب سازی با‬ ‫مرتبه زمانی ‪ (O(nlogn‬وجود دارد‬ ‫‪‬‬

‫‪‬‬

‫پس الگوریتم ‪ optOrder2‬نیز مرتبه زمانی اش ‪O(n‬‬ ‫‪ (logn‬می باشد‪.‬‬

‫نکته‪ :‬الگوریتم قبلی )‪ (optOrder‬را می توان یک‬ ‫الگوریتم مرتب سازی مبتنی بر روش حریصانه به‬ ‫حساب آورد‪.‬‬ ‫روش حریصانه‬

‫‪25‬‬

‫مطالب مورد بحث‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫کوله پشتی غیر صفر و یک‬ ‫زمانبندی بهینه اجرای برنامه ها‬ ‫درخت پوشای مینیمم‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬ ‫‪‬‬

‫الگوریتم ‪Prim‬‬ ‫الگوریتم ‪Kruskal‬‬

‫کوتاهترین مسیرها از مبدأ واحد‬ ‫فشرده سازی با استفاده از کد ‪Huffman‬‬

‫روش حریصانه‬

‫‪26‬‬

‫درخت پوشای مینیمم‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫گراف‪(G=(V, E :‬‬ ‫‪V‬مجموعه گره ها ‪:‬‬ ‫‪E‬مجموعه یالها ‪:‬‬

‫‪A‬‬

‫‪B‬‬

‫‪C‬‬

‫} ‪V = { A, B, C, D, E‬‬

‫‪D‬‬ ‫‪E‬‬

‫‪E = { (A,B), (A,D), (B,C), (B,E), (C,‬‬ ‫} )‪D‬‬

‫روش حریصانه‬

‫‪27‬‬

‫درخت پوشای مینیمم‬ ‫‪‬‬

‫گراف جهت دار‬

‫‪A‬‬

‫‪B‬‬

‫‪C‬‬

‫‪D‬‬

‫‪E‬‬ ‫} ‪V = { A, B, C, D, E‬‬ ‫‪E = { , , , , ,‬‬ ‫} >‪
‫روش حریصانه‬

‫‪28‬‬

‫درخت پوشای مینیمم‬ ‫‪‬‬

‫گراف وزن دار‪ :‬گرافی که یالهای آن دارای وزن‬ ‫می باشند‪ .‬مفهوم وزن یالها‪ ،‬به اینکه گراف در چه‬ ‫کاربردی استفاده شده باشد‪ ،‬بستگی دارد‪.‬‬ ‫‪‬‬

‫گراف راههای ارتباطی بین شهرها‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫گره ها‪ :‬شهرها‬ ‫یالها‪ :‬جاده ها‬ ‫وزن یالها‪ :‬طول جاده ها‬

‫بین دو گره ‪ u‬و ‪ v‬مسیری وجود دارد اگر‬ ‫‪‬‬ ‫‪‬‬

‫یک یال بین دو گره ‪ u‬و ‪ v‬موجود باشد‪ .‬یا‬ ‫یک گره ‪ z‬موجود باشد که با یک یال به گره ‪ u‬متصل‬ ‫باشد و ضمنا مسیری بین دو گره ‪ z‬و ‪ v‬موجود باشد‪.‬‬

‫روش حریصانه‬

‫‪29‬‬

‫درخت پوشای مینیمم‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬ ‫‪‬‬

‫چرخه یا حلقه )‪ :(cycle‬اگر در یک گراف‬ ‫مسیری از یک گره به خودش وجود داشته‬ ‫باشد‪ ،‬آن گراف دارای حلقه خواهد بود‪.‬‬ ‫گراف متصل یا همبند )‪ :(connected‬گرافی‬ ‫که بین هر دو گره دلخواه آن حداقل یک مسیر‬ ‫وجود داشته باشد‪.‬‬ ‫درخت‪ :‬گراف همبند بدون جهت بدون حلقه‬ ‫زیرگراف‪ :‬گراف ‪ ،(G2=(V2, E2‬زیرگراف‬ ‫گراف ‪ (G1=(V1,E1‬خواهد بود اگر‬ ‫‪‬‬ ‫‪‬‬

‫‪ V2‬شامل تمام گره های ‪.V1‬باشد‬ ‫‪ E2‬زیرمجموعه ‪.E1‬باشد‬

‫روش حریصانه‬

‫‪30‬‬

‫درخت پوشای مینیمم‬

‫‪B‬‬

‫‪C‬‬

‫‪D‬‬

‫‪E‬‬

‫یک زیرگراف از‬ ‫گراف ‪G‬‬ ‫روش حریصانه‬

‫‪B‬‬

‫‪A‬‬

‫‪A‬‬

‫‪C‬‬

‫‪D‬‬

‫‪E‬‬

‫گراف ‪G‬‬

‫‪31‬‬

‫درخت پوشای مینیمم‬ ‫‪‬‬

‫درخت پوشا‬ ‫‪‬‬

‫اگر ‪ G‬یک گراف همبند بدون جهت باشد‪ T ،‬یک‬ ‫درخت پوشا برای ‪ G‬است اگر‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫‪ T‬یک زیرگراف از گراف ‪ G‬باشد و‬ ‫‪.T‬یک درخت باشد‬

‫درخت پوشای مینیمم )‪MST: Minimum‬‬ ‫‪(Spanning Tree‬‬ ‫‪ ‬اگر ‪ G‬یک گراف همبند بدون جهت وزن دار باشد‪،‬‬ ‫‪ T‬یک درخت پوشای مینیمم برای ‪ G‬است اگر‬ ‫‪‬‬ ‫‪‬‬

‫‪ T‬یک درخت پوشا برای ‪G‬باشد و‬ ‫هزینه ‪ T‬از هزینه تمام درخت های پوشای گراف ‪ G‬کمتر‬ ‫باشد‪.‬‬

‫روش حریصانه‬

‫‪32‬‬

‫درخت پوشای مینیمم‬ ‫‪A‬‬

‫‪B‬‬ ‫‪6‬‬

‫‪B‬‬ ‫‪3‬‬

‫‪4‬‬

‫‪C‬‬ ‫‪5‬‬

‫‪E‬‬

‫یک درخت‬ ‫پوشای غیر‬ ‫مینیمم برای‬ ‫گراف ‪G‬‬

‫روش حریصانه‬

‫‪D‬‬

‫‪1‬‬

‫‪A‬‬

‫‪3‬‬

‫‪6‬‬

‫‪3‬‬

‫‪4‬‬

‫‪C‬‬ ‫‪5‬‬

‫‪D‬‬ ‫‪2‬‬

‫‪E‬‬

‫گراف ‪G‬‬

‫‪33‬‬

‫درخت پوشای مینیمم‬

‫‪B‬‬

‫‪C‬‬

‫‪1‬‬

‫‪B‬‬

‫‪A‬‬

‫‪4‬‬

‫‪3‬‬

‫‪6‬‬

‫‪D‬‬

‫‪C‬‬

‫‪2‬‬ ‫‪E‬‬

‫درخت پوشای مینیمم‬ ‫گراف ‪G‬‬ ‫روش حریصانه‬

‫‪1‬‬

‫‪A‬‬

‫‪3‬‬

‫‪3‬‬

‫‪4‬‬ ‫‪5‬‬

‫‪D‬‬ ‫‪2‬‬

‫‪E‬‬

‫گراف ‪G‬‬

‫‪34‬‬

‫درخت پوشای مینیمم‬ ‫‪‬‬

‫یک روش نمایش گراف‪ :‬ماتریس مجاورت‬ ‫‪B‬‬

‫‪D‬‬

‫‪‬‬

‫‪C‬‬

‫‪A‬‬

‫‪B‬‬

‫‪1‬‬ ‫‪3‬‬

‫‪6‬‬

‫∞‬

‫∞‬

‫‪3‬‬

‫‪1‬‬

‫∞‪E‬‬

‫∞‬

‫‪3‬‬

‫‪6‬‬

‫∞‬

‫‪1‬‬

‫‪B‬‬

‫‪5‬‬

‫‪4‬‬

‫∞‬

‫‪6‬‬

‫∞‬

‫‪C‬‬

‫‪2‬‬

‫∞‬

‫‪4‬‬

‫‪3‬‬

‫‪3‬‬

‫‪D‬‬

‫∞‬

‫‪2‬‬

‫‪5‬‬

‫∞‬

‫∞‬

‫‪E‬‬

‫‪A‬‬

‫‪A‬‬ ‫‪3‬‬

‫‪4‬‬

‫‪C‬‬ ‫‪5‬‬

‫‪D‬‬ ‫‪2‬‬

‫‪E‬‬

‫با ‪ (O(1‬می توان هزینه یال بین دو گره را بدست‬ ‫آورد‪.‬‬ ‫روش حریصانه‬

‫‪35‬‬

‫درخت پوشای مینیمم‬ ‫‪‬‬

‫‪‬‬

‫مساله‪ :‬الگوریتمی که گراف همبند بدون‬ ‫جهت وزن دار ‪ G‬را گرفته و درخت پوشای‬ ‫مینیمم آن را بدست آورد‪.‬‬ ‫الگوریتم ‪ Prim‬و همچنین الگوریتم ‪Kruskal‬‬ ‫مبتنی بر روش حریصانه برای حل این مساله‬ ‫طراحی شده اند‪.‬‬

‫روش حریصانه‬

‫‪36‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪Prim‬‬ ‫‪‬‬

‫روش کلی‬ ‫‪‬‬

‫‪‬‬

‫از آنجا که تمام گره ها باید در ‪ MST‬باشند‪ ،‬ابتدا‬ ‫یک گره را به دلخواه بعنوان عضو اول مجموعه‬ ‫جواب انتخاب می کنیم‪ .‬سپس در هر مرحله یک‬ ‫گره انتخاب نشده را به عنوان عضو بعدی مجموعه‬ ‫جواب انتخاب می کنیم‪.‬‬ ‫در هر مرحله‬ ‫‪‬‬

‫‪‬‬

‫گره ای را انتخاب می کنیم که با کمترین هزینه )وزن‬ ‫یال( به گره های مجموعه جواب متصل می شود‪.‬‬ ‫این گره را به مجموعه جواب اضافه می کنیم‪.‬‬

‫روش حریصانه‬

‫‪37‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪Prim‬‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫قضیه ‪ :1‬افزودن یک یال )بین گره های موجود( به یک‬ ‫درخت موجب ایجاد حلقه می شود‪.‬‬ ‫اثبات‪ :‬درخت ‪ T‬با ‪ n‬گره موجود است‪ .‬یال ‪ e‬را به آن می‬ ‫افزاییم که گره های ‪ u‬و ‪ v‬را به هم متصل می کند‪ .‬از آنجا‬ ‫که ‪ T‬در ابتدا‪ ،‬درخت بود بنابراین مسیری بین دو گره ‪ u‬و‬ ‫‪ v‬موجود بوده است )مسیر ‪ .(p1‬با افزودن یال ‪ e‬که ‪ u‬را‬ ‫به ‪ v‬متصل می کند‪ ،‬مسیر دیگری بین ‪ u‬و ‪ v‬بوجود خواهد‬ ‫آمد )خود یال ‪ e‬در واقع یک مسیر جدید است‪ .(p2 :‬ترکیب‬ ‫دو مسیر ‪ p1‬و ‪ ،p2‬یک حلقه می باشد‪.‬‬ ‫واضح است که یال افزوده شده در حلقه قرار دارد‪.‬‬

‫روش حریصانه‬

‫‪38‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪prim‬‬ ‫‪‬‬

‫‪‬‬

‫‪)G=(V,E‬یک گراف همبند‪ ،‬بدون جهت و وزن‬ ‫دار‬ ‫تعریف‪ :‬مجموعه ‪ F‬زیرمجموعه ‪ ،E‬را‬ ‫امیدوارکننده )‪ (promising‬گوییم اگر ‪ F‬این‬ ‫قابلیت را داشته باشد که به ‪ (MST(G‬منتهی‬ ‫شود‪.‬‬ ‫‪‬‬

‫‪‬‬

‫یعنی بتوان با افزودن تعدادی از یالهای ‪ G‬به آن‪،‬‬ ‫به درخت پوشای مینیمم ‪ G‬رسید‪.‬‬ ‫یعنی ‪ F‬شامل هیچ یال مزاحمی نباشد‪.‬‬

‫روش حریصانه‬

‫‪39‬‬

‫ الگوریتم‬/ ‫درخت پوشای مینیمم‬ prim 1

A

B

3

3

4

D 2

1

A 6

3

C

D

5

4

C

2

E

E

G

MST(G)

F={ (B,C), (A,B) }

is not promising

F={ (A,B), (A,D) }

is promising

40

B

‫روش حریصانه‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪prim‬‬ ‫‪‬‬

‫قضیه ‪ (G=(V,E :2‬گراف همبند بدون جهت و‬ ‫وزن دار است‪.‬‬ ‫‪‬‬

‫‪‬‬

‫فرض‪ F :‬زیرمجموعه ‪ ،E‬و ‪ Y‬مجموعه گره هایی که‬ ‫توسط یالهای ‪ F‬بهم متصل می شوند‪ .‬همچنین ‪F‬‬ ‫امیدوارکننده است‪.‬‬ ‫حکم‪ :‬اگر ‪ e‬کم وزن ترین یالی باشد که یک گره ‪Y‬‬ ‫را به گره ای در ‪ V-Y‬متصل می کند‪ ،‬آنگاه ‪{F∪{e‬‬ ‫نیز امیدوارکننده خواهد بود‪.‬‬ ‫‪‬‬

‫‪‬‬

‫یعنی با افزودن یال ‪ e‬به ‪ F‬باز هم ‪ F‬این قابلیت را دارد‬ ‫که به ‪ (MST(G‬منتهی شود‪.‬‬

‫اثبات‬

‫روش حریصانه‬

‫‪41‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪prim‬‬ ‫‪‬‬ ‫‪‬‬

‫الگوریتم ‪ prim‬بر اساس قضیه ‪ 2‬عمل می کند‪.‬‬ ‫ابتدا ‪ Y‬تنها شامل یک گره می باشد )به دلخواه انتخاب می شود(‬ ‫‪‬‬

‫‪‬‬

‫در هرگام‪،‬‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫درنتیجه ‪ F‬تهی می باشد‪) .‬واضح است که ‪ F‬امیدوارکننده است(‬ ‫ابتدا گره های موجود در ‪ V-Y‬را بررسی می کنیم و برای هر گره ‪ i‬موجود در ‪،V-Y‬‬ ‫کم هزینه ترین یالی را که آن گره را به گره ای در ‪ Y‬متصل می کند مشخص می‬ ‫کنیم‪ ،‬وزن این یال را با ‪ (dist(i‬نمایش می دهیم‪.‬‬ ‫سپس گره ای را که دارای کمترین ‪ dist‬می باشد را انتخاب کرده و آن را به‬ ‫مجموعه ‪ V-Y‬منتقل می کنیم‪ .‬همچنین یال مربوط به آن را به ‪ F‬اضافه می کنیم‪.‬‬

‫ادامه می دهیم تا ‪ Y‬شامل تمام گره های ‪ G‬شود‪.‬‬

‫روش حریصانه‬

‫‪42‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪prim‬‬ ‫ساختار مورد استفاده برای انجام‬ ‫عملیات الگوریتم‬ ‫‪minDist‬‬

‫‪near‬‬

‫‪Y‬‬

‫‪nodes‬‬ ‫‪0‬‬ ‫‪1‬‬ ‫‪...‬‬ ‫‪n‬‬

‫روش حریصانه‬

‫مشخص می کند که آیا گره‬ ‫انتخاب شده یا نه‪ 1 .‬یعنی‬ ‫انتخاب شده و ‪ 0‬یعنی انتخاب‬ ‫نشده‬ ‫برای هر گره انتخاب نشده‪ ،‬شماره‬ ‫نزدیکترین گره انتخاب شده را‬ ‫مشخص می کند‪ .‬برای گره های‬ ‫انتخاب شده مقدار این ستون ‪-1‬‬ ‫باشد‪.‬گره انتخاب نشده‪ ،‬فاصله‬ ‫برای هر‬ ‫می‬ ‫نزدیکترین گره انتخاب شده را‬ ‫مشخص می کند‪ .‬برای گره های‬ ‫انتخاب شده مقدار این ستون ∞‬ ‫می باشد‪.‬‬

‫‪43‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪prim‬‬ ‫‪‬‬

‫مثال‬ ‫‪10‬‬

‫‪1‬‬ ‫‪40‬‬

‫‪45‬‬

‫‪50‬‬ ‫‪2‬‬

‫‪35‬‬

‫‪0‬‬

‫‪30‬‬

‫‪4‬‬ ‫‪3‬‬ ‫‪55‬‬

‫‪25‬‬

‫‪15‬‬

‫‪20‬‬ ‫‪5‬‬

‫روش حریصانه‬

‫‪44‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪prim‬‬ ‫‪near minDist‬‬

‫‪10‬‬

‫‪1‬‬ ‫‪40‬‬

‫‪2‬‬

‫‪35‬‬

‫‪0‬‬ ‫‪45‬‬

‫‪50‬‬

‫‪30‬‬

‫‪4‬‬ ‫‪3‬‬ ‫‪55‬‬

‫‪25‬‬

‫‪Y‬‬

‫‪nodes‬‬

‫‪15‬‬

‫∞‬

‫‪1-‬‬

‫‪1‬‬

‫‪0‬‬

‫‪10‬‬

‫‪0‬‬

‫‪0‬‬

‫‪1‬‬

‫∞‬

‫‪0‬‬

‫‪0‬‬

‫‪2‬‬

‫‪30‬‬

‫‪0‬‬

‫‪0‬‬

‫‪3‬‬

‫‪45‬‬

‫‪0‬‬

‫‪0‬‬

‫‪4‬‬

‫∞‬

‫‪0‬‬

‫‪0‬‬

‫‪5‬‬

‫‪20‬‬ ‫‪5‬‬

‫گره های زرد مشخص کننده گره های‬ ‫انتخاب شده هستند )گره های عضو‬ ‫مجموعه ‪(Y‬‬ ‫روش حریصانه‬

‫‪0‬‬

‫=‪Cost‬‬ ‫‪0‬‬

‫‪45‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪prim‬‬ ‫‪near minDist‬‬

‫‪10‬‬

‫‪1‬‬ ‫‪40‬‬

‫‪2‬‬

‫‪35‬‬

‫‪0‬‬ ‫‪45‬‬

‫‪50‬‬

‫‪30‬‬

‫‪4‬‬ ‫‪3‬‬ ‫‪55‬‬

‫‪25‬‬

‫‪Y‬‬

‫‪nodes‬‬

‫‪15‬‬

‫‪20‬‬ ‫‪5‬‬

‫گره های زرد مشخص کننده گره های‬ ‫انتخاب شده هستند )گره های عضو‬ ‫مجموعه ‪(Y‬‬ ‫روش حریصانه‬

‫∞‬

‫‪1-‬‬

‫‪1‬‬

‫‪0‬‬

‫∞‬

‫‪1-‬‬

‫‪1‬‬

‫‪1‬‬

‫‪50‬‬

‫‪1‬‬

‫‪0‬‬

‫‪2‬‬

‫‪30‬‬

‫‪0‬‬

‫‪0‬‬

‫‪3‬‬

‫‪40‬‬

‫‪1‬‬

‫‪0‬‬

‫‪4‬‬

‫‪25‬‬

‫‪1‬‬

‫‪0‬‬

‫‪5‬‬

‫‪1‬‬

‫‪Cost=1‬‬ ‫‪0‬‬

‫‪10‬‬

‫‪0‬‬

‫‪46‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪prim‬‬ ‫‪near minDist‬‬

‫‪10‬‬

‫‪1‬‬ ‫‪40‬‬

‫‪2‬‬

‫‪35‬‬

‫‪0‬‬ ‫‪45‬‬

‫‪50‬‬

‫‪30‬‬

‫‪4‬‬ ‫‪3‬‬ ‫‪55‬‬

‫‪25‬‬

‫‪Y‬‬

‫‪nodes‬‬

‫‪15‬‬

‫‪20‬‬ ‫‪5‬‬

‫∞‬

‫‪1-‬‬

‫‪1‬‬

‫‪0‬‬

‫∞‬

‫‪1-‬‬

‫‪1‬‬

‫‪1‬‬

‫‪15‬‬

‫‪5‬‬

‫‪0‬‬

‫‪2‬‬

‫‪20‬‬

‫‪5‬‬

‫‪0‬‬

‫‪3‬‬

‫‪40‬‬

‫‪1‬‬

‫‪0‬‬

‫‪4‬‬

‫∞‬

‫‪1-‬‬

‫‪1‬‬

‫‪5‬‬

‫‪1‬‬

‫‪10‬‬

‫‪0‬‬

‫‪25‬‬

‫گره های زرد مشخص کننده گره های‬ ‫انتخاب شده هستند )گره های عضو‬ ‫مجموعه ‪(Y‬‬ ‫روش حریصانه‬

‫‪5‬‬ ‫‪Cost=3‬‬ ‫‪5‬‬

‫‪47‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪prim‬‬ ‫‪near minDist‬‬

‫‪10‬‬

‫‪1‬‬ ‫‪40‬‬

‫‪2‬‬

‫‪35‬‬

‫‪0‬‬ ‫‪45‬‬

‫‪50‬‬

‫‪30‬‬

‫‪4‬‬ ‫‪3‬‬ ‫‪55‬‬

‫‪25‬‬

‫‪Y‬‬

‫‪nodes‬‬

‫‪15‬‬

‫‪20‬‬ ‫‪5‬‬

‫گره های زرد مشخص کننده گره های‬ ‫انتخاب شده هستند )گره های عضو‬ ‫مجموعه ‪(Y‬‬ ‫روش حریصانه‬

‫∞‬

‫‪1-‬‬

‫‪1‬‬

‫‪0‬‬

‫∞‬

‫‪1-‬‬

‫‪1‬‬

‫‪1‬‬

‫∞‬

‫‪1-‬‬

‫‪1‬‬

‫‪2‬‬

‫‪20‬‬

‫‪5‬‬

‫‪0‬‬

‫‪3‬‬

‫‪35‬‬

‫‪2‬‬

‫‪0‬‬

‫‪4‬‬

‫∞‬

‫‪1-‬‬

‫‪1‬‬

‫‪5‬‬

‫‪1‬‬ ‫‪2‬‬

‫‪15‬‬

‫‪10‬‬

‫‪0‬‬

‫‪25‬‬

‫‪5‬‬ ‫‪Cost=5‬‬ ‫‪0‬‬

‫‪48‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪prim‬‬ ‫‪near minDist‬‬

‫‪10‬‬

‫‪1‬‬ ‫‪40‬‬

‫‪2‬‬

‫‪35‬‬

‫‪30‬‬

‫‪4‬‬ ‫‪3‬‬ ‫‪55‬‬

‫‪25‬‬

‫‪Y‬‬

‫‪0‬‬ ‫‪45‬‬

‫‪50‬‬

‫‪nodes‬‬

‫‪15‬‬

‫‪20‬‬ ‫‪5‬‬

‫گره های زرد مشخص کننده گره های‬ ‫انتخاب شده هستند )گره های عضو‬ ‫مجموعه ‪(Y‬‬ ‫روش حریصانه‬

‫∞‬

‫‪1-‬‬

‫‪1‬‬

‫‪0‬‬

‫∞‬

‫‪1-‬‬

‫‪1‬‬

‫‪1‬‬

‫∞‬

‫‪1-‬‬

‫‪1‬‬

‫‪2‬‬

‫∞‬

‫‪1-‬‬

‫‪1‬‬

‫‪3‬‬

‫‪35‬‬

‫‪2‬‬

‫‪0‬‬

‫‪4‬‬

‫∞‬

‫‪1-‬‬

‫‪1‬‬

‫‪5‬‬

‫‪1‬‬ ‫‪2‬‬

‫‪15‬‬

‫‪10‬‬

‫‪0‬‬

‫‪25‬‬

‫‪5‬‬ ‫‪Cost=7‬‬ ‫‪0‬‬

‫‪20‬‬

‫‪3‬‬

‫‪49‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪prim‬‬ ‫‪near minDist‬‬

‫‪10‬‬

‫‪1‬‬ ‫‪40‬‬

‫‪2‬‬

‫‪35‬‬

‫‪30‬‬

‫‪4‬‬ ‫‪3‬‬ ‫‪55‬‬

‫‪25‬‬

‫‪Y‬‬

‫‪0‬‬ ‫‪45‬‬

‫‪50‬‬

‫‪nodes‬‬

‫‪15‬‬

‫‪20‬‬ ‫‪5‬‬

‫گره های زرد مشخص کننده گره های‬ ‫انتخاب شده هستند )گره های عضو‬ ‫مجموعه ‪(Y‬‬ ‫روش حریصانه‬

‫∞‬

‫‪1-‬‬

‫‪1‬‬

‫‪0‬‬

‫∞‬

‫‪1-‬‬

‫‪1‬‬

‫‪1‬‬

‫∞‬

‫‪1-‬‬

‫‪1‬‬

‫‪2‬‬

‫∞‬

‫‪1-‬‬

‫‪1‬‬

‫‪3‬‬

‫∞‬

‫‪1-‬‬

‫‪1‬‬

‫‪4‬‬

‫‪1-‬‬

‫∞‬ ‫‪1‬‬

‫‪4‬‬

‫‪1‬‬

‫‪10‬‬

‫‪0‬‬

‫‪25‬‬ ‫‪35‬‬

‫‪2‬‬

‫‪15‬‬

‫‪5‬‬

‫‪5‬‬

‫‪Cost=10‬‬ ‫‪5‬‬ ‫‪20‬‬ ‫‪3‬‬

‫‪50‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪prim‬‬ ‫‪10‬‬

‫‪1‬‬ ‫‪40‬‬

‫‪45‬‬

‫‪50‬‬ ‫‪2‬‬

‫‪35‬‬

‫‪0‬‬

‫‪30‬‬

‫‪4‬‬ ‫‪3‬‬ ‫‪55‬‬

‫‪25‬‬

‫)‪MST(G‬‬

‫روش حریصانه‬

‫‪15‬‬

‫‪20‬‬ ‫‪5‬‬ ‫‪G‬‬

‫‪51‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪prim‬‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫محاسبه مرتبه زمانی به روش ذهنی‬ ‫تعداد گره های گراف‪n :‬‬ ‫الگوریتم شامل ‪ n‬مرحله است که در هر مرحله یک گره‬ ‫را انتخاب می کنیم‪.‬‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫در هر مرحله برای هر گره انتخاب نشده‪ ،minDist ،‬یعنی‬ ‫مینیمم فاصله آن گره با گره های ‪ Y‬را مشخص می کنیم‪ .‬برای‬ ‫این کار باید وزن یال بین آن گره و هر یک از گره های ‪ Y‬را‬ ‫بررسی کنیم‪) .‬برای راحتی کار تعداد این گره ها را ‪ n‬در نظر‬ ‫می گیریم( ‪( O(n‬‬ ‫سپس باید در بین گره های انتخاب نشده‪ ،‬گره با کمترین‬ ‫‪ minDist‬را انتخاب کنیم‪( O(n .‬‬

‫در نهایت الگوریتم از مرتبه زمانی ‪ (O(n2‬می باشد‪.‬‬ ‫روش حریصانه‬

‫‪52‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪Kruskal‬‬ ‫‪‬‬

‫روش کلی‬ ‫‪‬‬

‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫برای گراف دارای ‪ n‬گره‪ MST ،‬شامل ‪ n-1‬یال خواهد بود‬ ‫)چون درخت است(‪.‬‬ ‫یالها را بر حسب وزنشان بطور غیرنزولی مرتب می کنیم‪.‬‬ ‫ابتدا گراف را در قالب ‪ n‬مجموعه که هر یک دارای یک گره‬ ‫می باشند در نظر می گیریم‪.‬‬ ‫یالها را از ابتدای لیست مرتب‪ ،‬یکی یکی بررسی می کنیم‪.‬‬ ‫در هر مرحله‬ ‫‪‬‬

‫‪‬‬

‫اگر یال مورد بررسی دو مجموعه جدا از هم را به هم متصل می کند‪،‬‬ ‫آن را بعنوان یک یال موجود در ‪ MST‬در نظر می گیریم و دو مجموعه‬ ‫مربوط به ابتدا و انتهای یال را با هم ادغام می کنیم‪.‬‬

‫این کار را ادامه می دهیم تا ‪ n-1‬یال انتخاب شوند‪.‬‬

‫روش حریصانه‬

‫‪53‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪Kruskal‬‬ ‫‪Sorted list of edges‬‬

‫‪cost‬‬

‫‪edge‬‬

‫‪10‬‬

‫)‪(0,1‬‬

‫‪15‬‬

‫)‪(2,5‬‬

‫‪20‬‬

‫)‪(3,5‬‬

‫‪25‬‬

‫)‪(1,5‬‬

‫‪30‬‬

‫)‪(0,3‬‬

‫‪35‬‬

‫)‪(2,4‬‬

‫‪40‬‬

‫)‪(1,4‬‬

‫‪45‬‬

‫)‪(0,4‬‬

‫‪50‬‬

‫)‪(1,2‬‬

‫‪55‬‬

‫)‪(4,5‬‬

‫روش حریصانه‬

‫‪10‬‬

‫‪1‬‬ ‫‪40‬‬

‫‪45‬‬

‫‪50‬‬ ‫‪2‬‬

‫‪35‬‬

‫‪0‬‬

‫‪30‬‬

‫‪4‬‬ ‫‪3‬‬ ‫‪55‬‬

‫‪25‬‬

‫‪15‬‬

‫‪20‬‬ ‫‪5‬‬

‫‪54‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪Kruskal‬‬ ‫‪Sorted list of edges‬‬

‫‪cost‬‬

‫‪edge‬‬

‫‪10‬‬

‫)‪(0,1‬‬

‫‪15‬‬

‫)‪(2,5‬‬

‫‪20‬‬

‫)‪(3,5‬‬

‫‪25‬‬

‫)‪(1,5‬‬

‫‪30‬‬

‫)‪(0,3‬‬

‫‪35‬‬

‫)‪(2,4‬‬

‫‪40‬‬

‫)‪(1,4‬‬

‫‪45‬‬

‫)‪(0,4‬‬

‫‪50‬‬

‫)‪(1,2‬‬

‫‪55‬‬

‫)‪(4,5‬‬

‫روش حریصانه‬

‫‪10‬‬

‫‪1‬‬

‫‪2‬‬

‫‪0‬‬

‫‪4‬‬ ‫‪3‬‬

‫‪5‬‬

‫‪55‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪Kruskal‬‬ ‫‪Sorted list of edges‬‬

‫‪cost‬‬

‫‪edge‬‬

‫‪10‬‬

‫)‪(0,1‬‬

‫‪15‬‬

‫)‪(2,5‬‬

‫‪20‬‬

‫)‪(3,5‬‬

‫‪25‬‬

‫)‪(1,5‬‬

‫‪30‬‬

‫)‪(0,3‬‬

‫‪35‬‬

‫)‪(2,4‬‬

‫‪40‬‬

‫)‪(1,4‬‬

‫‪45‬‬

‫)‪(0,4‬‬

‫‪50‬‬

‫)‪(1,2‬‬

‫‪55‬‬

‫)‪(4,5‬‬

‫روش حریصانه‬

‫‪10‬‬

‫‪1‬‬

‫‪0‬‬

‫‪4‬‬

‫‪2‬‬

‫‪3‬‬ ‫‪15‬‬ ‫‪5‬‬

‫‪56‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪Kruskal‬‬ ‫‪Sorted list of edges‬‬

‫‪cost‬‬

‫‪edge‬‬

‫‪10‬‬

‫)‪(0,1‬‬

‫‪15‬‬

‫)‪(2,5‬‬

‫‪20‬‬

‫)‪(3,5‬‬

‫‪25‬‬

‫)‪(1,5‬‬

‫‪30‬‬

‫)‪(0,3‬‬

‫‪35‬‬

‫)‪(2,4‬‬

‫‪40‬‬

‫)‪(1,4‬‬

‫‪45‬‬

‫)‪(0,4‬‬

‫‪50‬‬

‫)‪(1,2‬‬

‫‪55‬‬

‫)‪(4,5‬‬

‫روش حریصانه‬

‫‪10‬‬

‫‪1‬‬

‫‪0‬‬

‫‪4‬‬

‫‪2‬‬

‫‪3‬‬ ‫‪15‬‬

‫‪20‬‬ ‫‪5‬‬

‫‪57‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪Kruskal‬‬ ‫‪Sorted list of edges‬‬

‫‪cost‬‬

‫‪edge‬‬

‫‪10‬‬

‫)‪(0,1‬‬

‫‪15‬‬

‫)‪(2,5‬‬

‫‪20‬‬

‫)‪(3,5‬‬

‫‪25‬‬

‫)‪(1,5‬‬

‫‪30‬‬

‫)‪(0,3‬‬

‫‪35‬‬

‫)‪(2,4‬‬

‫‪40‬‬

‫)‪(1,4‬‬

‫‪45‬‬

‫)‪(0,4‬‬

‫‪50‬‬

‫)‪(1,2‬‬

‫‪55‬‬

‫)‪(4,5‬‬

‫روش حریصانه‬

‫‪10‬‬

‫‪1‬‬

‫‪4‬‬

‫‪2‬‬

‫‪25‬‬

‫‪0‬‬

‫‪3‬‬ ‫‪15‬‬

‫‪20‬‬ ‫‪5‬‬

‫‪58‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪Kruskal‬‬ ‫‪Sorted list of edges‬‬

‫‪cost‬‬

‫‪edge‬‬

‫‪10‬‬

‫)‪(0,1‬‬

‫‪15‬‬

‫)‪(2,5‬‬

‫‪20‬‬

‫)‪(3,5‬‬

‫‪25‬‬

‫)‪(1,5‬‬

‫‪30‬‬

‫)‪(0,3‬‬

‫‪35‬‬

‫)‪(2,4‬‬

‫‪40‬‬

‫)‪(1,4‬‬

‫‪45‬‬

‫)‪(0,4‬‬

‫‪50‬‬

‫)‪(1,2‬‬

‫‪55‬‬

‫)‪(4,5‬‬

‫روش حریصانه‬

‫‪10‬‬

‫‪1‬‬

‫‪4‬‬

‫‪2‬‬

‫‪25‬‬

‫‪0‬‬

‫‪3‬‬ ‫‪15‬‬

‫‪20‬‬ ‫‪5‬‬

‫‪59‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪Kruskal‬‬ ‫‪Sorted list of edges‬‬

‫‪cost‬‬

‫‪edge‬‬

‫‪10‬‬

‫)‪(0,1‬‬

‫‪15‬‬

‫)‪(2,5‬‬

‫‪20‬‬

‫)‪(3,5‬‬

‫‪25‬‬

‫)‪(1,5‬‬

‫‪30‬‬

‫)‪(0,3‬‬

‫‪35‬‬

‫)‪(2,4‬‬

‫‪40‬‬

‫)‪(1,4‬‬

‫‪45‬‬

‫)‪(0,4‬‬

‫‪50‬‬

‫)‪(1,2‬‬

‫‪55‬‬

‫)‪(4,5‬‬

‫روش حریصانه‬

‫‪10‬‬

‫‪1‬‬

‫‪2‬‬

‫‪25‬‬

‫‪35‬‬

‫‪0‬‬

‫‪4‬‬ ‫‪3‬‬

‫‪15‬‬

‫‪20‬‬ ‫‪5‬‬

‫‪60‬‬

‫ الگوریتم‬/ ‫درخت پوشای مینیمم‬ Kruskal 0

4 3

1

35

15

20 5 Cost of MST = 105

61

Sorted list of edges

10

2

25

edge

cost

(0,1)

10

(2,5)

15

(3,5)

20

(1,5)

25

(0,3)

30

(2,4)

35

(1,4)

40

(0,4)

45

(1,2)

50

(4,5)

55 ‫روش حریصانه‬

‫ الگوریتم‬/ ‫درخت پوشای مینیمم‬ Kruskal void kruskal(int n, int m) {

‫شبه کد‬ sortEdges(m); ‫الگوریتم‬ selectedEdges = 0; : ‫تعداد‬m while(selectedEdges < n-1) { ‫یالها‬ e = edge with min weight not yet considred; : ‫تعداد گره‬n i , j = source and dest of edge e; ‫ها‬ p = findSet(i);

q = findSet(j);

if ( p != q ) { merge(p, q); add e to selected edges; }}} 62

selectedEdges++; ‫روش حریصانه‬







‫ الگوریتم‬/ ‫درخت پوشای مینیمم‬ Kruskal void kruskal(int n, int m) { sortEdges(m); selectedEdges = 0;

‫مرتبه زمانی بر‬ m ‫ و‬n ‫حسب‬

O(m log m)

while(selectedEdges < n-1) { e = edge with min weight not yet considred; i , j = source and dest of edge e; p = findSet(i);

O(n log n)

q = findSet(j);

if ( p != q ) { merge(p, q); add e to selected Edges; }}} 63

k++; ‫روش حریصانه‬



‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪Kruskal‬‬ ‫‪‬‬

‫‪‬‬

‫)‪W(m,n) = O(n log n) + O(m log m‬‬ ‫از آنجا که برای گراف همبند ‪ m>=n-1‬پس‬ ‫)‪W(m,n) = O(m log m‬‬ ‫ضمنا از آنجا که ‪ n-1≤ m ≤ n(n-1)/2‬می توان گفت‬ ‫‪‬‬

‫‪‬‬

‫اگر تعداد یالها به حد پایین یعنی ‪ n-1‬نزدیک باشد مرتبه زمانی‬ ‫به سمت ‪ (O(n log n‬میل می کند و اگر تعداد یالها به سمت حد‬ ‫بال میل کند مرتبه زمانی به سمت ‪ (O(n2 logn‬میل می کند‪.‬‬

‫با توجه به اینکه مرتبه زمانی الگوریتم ‪ (prim ،O(n2‬بود‬ ‫‪‬‬

‫هر چه گراف خلوت تر )‪ (sparse‬باشد الگوریتم ‪ kruskal‬بهتر‬ ‫است و هر چه شلوغتر و متصل تر باشد‪ ،‬الگوریتم ‪ prim‬بهتر‬ ‫است‪.‬‬

‫روش حریصانه‬

‫‪64‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪Kruskal‬‬ ‫‪‬‬

‫مقایسه الگوریتم ‪ Kruskal‬و ‪Prim‬‬ ‫‪‬‬

‫حاصل الگوریتم ‪ prim‬در هر مرحله یک درخت‬ ‫است ولی حاصل الگوریتم ‪ kruskal‬در هر مرحله‬ ‫یک جنگل است‪.‬‬

‫روش حریصانه‬

‫‪65‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪Kruskal‬‬ ‫‪‬‬

‫چرا مرتبه زمانی ‪ findSet‬و ‪ merge‬را‬ ‫لگاریتمی در نظر گرفتیم؟‬ ‫‪‬‬

‫با استفاده از ساختمان داده خاصی با نام‬ ‫‪ Disjoint Sets‬می توان اعمال فوق را طوری‬ ‫پیاده سازی نمود که مرتبه زمانی لگاریتمی داشته‬ ‫باشند‪.‬‬

‫روش حریصانه‬

‫‪66‬‬

‫مطالب مورد بحث‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫کوله پشتی غیر صفر و یک‬ ‫زمانبندی بهینه اجرای برنامه ها‬ ‫درخت پوشای مینیمم‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬ ‫‪‬‬

‫الگوریتم ‪prim‬‬ ‫الگوریتم ‪Kruskal‬‬

‫کوتاهترین مسیرها از مبدأ واحد‬ ‫فشرده سازی با استفاده از کد ‪Huffman‬‬

‫روش حریصانه‬

‫‪67‬‬

‫کوتاهترین مسیرها از مبدأ واحد‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫‪Single-Source Shortest Path‬‬ ‫گراف ‪ (G=(V, E‬مفروض است‬ ‫هدف‪ ،‬یافتن کوتاهترین مسیرها از یک گره‬ ‫مشخص به گره های دیگر می باشد‪.‬‬ ‫‪‬‬

‫مثال‪ :‬گراف ‪ G‬بیانگر شبکه راههای ارتباطی‬ ‫شهرهای کشور باشد‪ ،‬هدف یافتن کوتاهترین‬ ‫مسیر از تهران به دیگر شهرها می باشد‪.‬‬

‫روش حریصانه‬

‫‪68‬‬

‫کوتاهترین مسیرها از مبدأ واحد‬ ‫‪1‬‬

‫گره مبدأ‪ :‬گره ‪0‬‬ ‫کوتاهترین مسیر از گره‬ ‫‪ 0‬به گره ‪1‬‬ ‫کوتاهترین مسیر از گره‬ ‫‪ 0‬به گره ‪2‬‬ ‫کوتاهترین مسیر از گره‬ ‫‪ 0‬به گره ‪3‬‬ ‫کوتاهترین مسیر از گره‬ ‫‪ 0‬به گره ‪4‬‬ ‫کوتاهترین مسیر از گره‬ ‫‪ 0‬به گره ‪5‬‬

‫روش حریصانه‬

‫‪10‬‬ ‫‪40‬‬

‫‪45‬‬

‫‪50‬‬ ‫‪2‬‬

‫‪35‬‬

‫‪0‬‬

‫‪30‬‬

‫‪4‬‬ ‫‪3‬‬ ‫‪55‬‬

‫‪25‬‬

‫‪15‬‬

‫‪20‬‬ ‫‪5‬‬

‫‪69‬‬

‫کوتاهترین مسیرها از مبدأ واحد‬ ‫‪‬‬

‫ایده اصلی‪:‬‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫مسیرها را به ترتیب از کوتاهترین به بلندترین‪ ،‬پیدا کنیم‪.‬‬ ‫اگر گره ‪ v‬گره مبدأ باشد‪ ،‬واضح است که کوتاهترین‬ ‫مسیر از این گره تا یک گره دیگر‪ ،‬باید تنها یک لبه داشته‬ ‫باشد که ‪ v‬را مستقیما به مقصد متصل می کند‪.‬‬ ‫‪ S‬مجموعه گره هایی که کوتاهترین مسیر از گره ‪v:‬به‬ ‫‪.‬آنها پیدا شده است‬ ‫در ابتدا ‪ S‬تنها شامل ‪ v‬است‪.‬‬ ‫اولین کوتاهترین مسیر را مشخص می کنیم‪.‬‬ ‫سپس در هر مرحله‪ ،‬کوتاهترین مسیر بعدی‪ ،‬از ‪ v‬شروع‬ ‫می شود و از گره های داخل ‪ S‬می گذرد و به گره ای‬ ‫برسد که تا حال مسیری برای آن پیدا نشده است‪.‬‬

‫روش حریصانه‬

‫‪70‬‬

‫کوتاهترین مسیرها از مبدأ واحد‬ ‫‪‬‬

‫‪‬‬

‫قضیه‪ :‬اگر کوتاهترین مسیر بعدی به گره ‪u‬‬ ‫باشد‪ ،‬آنگاه این مسیر از ‪ v‬شروع شده و می‬ ‫تواند تنها از گره های داخل ‪ S‬بگذرد و به ‪u‬‬ ‫ختم شود‪.‬‬ ‫اثبات با برهان خلف‬

‫روش حریصانه‬

‫‪71‬‬

‫کوتاهترین مسیرها از مبدأ واحد‬ ‫‪‬‬

‫الگوریتم دیکسترا مبتنی بر همین ایده‬

‫روش حریصانه‬

‫‪72‬‬

‫درخت پوشای مینیمم ‪ /‬الگوریتم‬ ‫‪prim‬‬ ‫ساختار مورد استفاده برای انجام‬ ‫عملیات الگوریتم‬ ‫‪path‬‬

‫‪dist‬‬

‫‪S‬‬

‫‪nodes‬‬ ‫‪0‬‬ ‫‪1‬‬ ‫‪...‬‬ ‫‪n‬‬

‫مشخص می کند که آیا گره‬ ‫انتخاب شده یا نه‪ 1 .‬یعنی‬ ‫انتخاب شده و ‪ 0‬یعنی انتخاب‬ ‫نشده‬ ‫طول کوتاهترین مسیر فعلی از‬ ‫مبدأ تا این گره‪ ،‬که فقط از گره‬ ‫های انتخاب شده می گذرد‪.‬‬ ‫کوتاهترین مسیر فعلی از مبدأ تا‬ ‫این گره‪ ،‬که ‪ dist‬طول آن را‬ ‫مشخص می کند‪.‬‬

‫روش حریصانه‬

‫‪73‬‬

‫کوتاهترین مسیرها از مبدأ واحد‬ ‫‪‬‬ ‫‪‬‬

‫مثال‬ ‫گره مبدأ‪ :‬گره ‪0‬‬

‫‪2‬‬

‫‪25‬‬ ‫‪30‬‬

‫‪1‬‬ ‫‪20‬‬

‫‪15‬‬

‫‪35‬‬

‫روش حریصانه‬

‫‪0‬‬ ‫‪20‬‬

‫‪10‬‬

‫‪10‬‬

‫‪15‬‬ ‫‪5‬‬

‫‪50‬‬

‫‪14‬‬ ‫‪4‬‬

‫‪12‬‬

‫‪3‬‬

‫‪74‬‬

‫کوتاهترین مسیرها از مبدأ واحد‬ ‫‪‬‬

‫‪‬‬

‫گام اول‪ :‬مقدار دهی‬ ‫‪2‬‬ ‫اولیه‬ ‫گام های بعد‪ :‬تعیین‬ ‫کوچکترین ‪ dist‬و انتخاب‪15‬‬ ‫گره مربوطه و‬ ‫سطرهای‬ ‫بروزرسانی ‪nodes S‬‬ ‫‪dist‬‬ ‫‪path‬‬ ‫‪5‬‬ ‫های‬ ‫جدول‬ ‫گره ‪0‬‬ ‫)برای ‪1‬‬ ‫‪0‬‬ ‫‪0-0‬‬ ‫‪1‬‬ ‫نشده(‪0‬‬ ‫انتخاب ‪50‬‬ ‫‪0-1‬‬ ‫‪0-2‬‬

‫∞‬

‫‪0‬‬

‫‪2‬‬

‫‪0-3‬‬

‫‪20‬‬

‫‪0‬‬

‫‪3‬‬

‫‪0-4‬‬

‫∞‬

‫‪0‬‬

‫‪4‬‬

‫‪0-5‬‬

‫∞‬

‫‪0‬‬

‫‪5‬‬

‫روش حریصانه‬

‫‪25‬‬ ‫‪30‬‬

‫‪1‬‬ ‫‪20‬‬

‫‪50‬‬ ‫‪15‬‬

‫‪0‬‬ ‫‪20‬‬

‫‪10‬‬

‫‪10‬‬ ‫‪14‬‬

‫‪35‬‬ ‫‪4‬‬

‫‪12‬‬

‫‪3‬‬

‫گره های زرد مشخص کننده گره‬ ‫های انتخاب شده هستند )گره های‬ ‫عضو مجموعه ‪(S‬‬

‫‪75‬‬

‫کوتاهترین مسیرها از مبدأ واحد‬ ‫‪2‬‬

‫‪25‬‬ ‫‪30‬‬

‫‪path‬‬

‫‪dist‬‬

‫‪S‬‬

‫‪0-0‬‬

‫‪0‬‬

‫‪1‬‬

‫‪0‬‬

‫‪0-3-1‬‬

‫‪35‬‬

‫‪0‬‬

‫‪1‬‬

‫‪0-2‬‬

‫∞‬

‫‪0‬‬

‫‪2‬‬

‫‪0-3‬‬

‫‪20‬‬

‫‪1‬‬

‫‪3‬‬

‫‪0-3-4‬‬

‫‪32‬‬

‫‪0‬‬

‫‪4‬‬

‫‪0-5‬‬

‫∞‬

‫‪0‬‬

‫‪5‬‬

‫روش حریصانه‬

‫‪15‬‬

‫‪20‬‬

‫‪35‬‬ ‫‪5‬‬

‫‪20‬‬

‫‪10‬‬

‫‪10‬‬

‫‪15‬‬ ‫‪nodes‬‬

‫‪1‬‬

‫‪50‬‬

‫‪0‬‬

‫‪14‬‬ ‫‪4‬‬

‫‪12‬‬

‫‪3‬‬

‫‪76‬‬

‫کوتاهترین مسیرها از مبدأ واحد‬ ‫‪2‬‬

‫‪25‬‬ ‫‪30‬‬

‫‪path‬‬

‫‪dist‬‬

‫‪S‬‬

‫‪0-0‬‬

‫‪0‬‬

‫‪1‬‬

‫‪0‬‬

‫‪0-3-1‬‬

‫‪35‬‬

‫‪0‬‬

‫‪1‬‬

‫‪0-3-4-2‬‬

‫‪67‬‬

‫‪0‬‬

‫‪2‬‬

‫‪0-3‬‬

‫‪20‬‬

‫‪1‬‬

‫‪3‬‬

‫‪0-3-4‬‬

‫‪32‬‬

‫‪1‬‬

‫‪4‬‬

‫‪0-5‬‬

‫∞‬

‫‪0‬‬

‫‪5‬‬

‫روش حریصانه‬

‫‪15‬‬

‫‪20‬‬

‫‪35‬‬ ‫‪5‬‬

‫‪20‬‬

‫‪10‬‬

‫‪10‬‬

‫‪15‬‬ ‫‪nodes‬‬

‫‪1‬‬

‫‪50‬‬

‫‪0‬‬

‫‪14‬‬ ‫‪4‬‬

‫‪12‬‬

‫‪3‬‬

‫‪77‬‬

‫کوتاهترین مسیرها از مبدأ واحد‬ ‫‪2‬‬

‫‪25‬‬ ‫‪30‬‬

‫‪path‬‬

‫‪dist‬‬

‫‪S‬‬

‫‪0-0‬‬

‫‪0‬‬

‫‪1‬‬

‫‪0‬‬

‫‪0-3-1‬‬

‫‪35‬‬

‫‪1‬‬

‫‪1‬‬

‫‪0-3-1-2‬‬

‫‪60‬‬

‫‪0‬‬

‫‪2‬‬

‫‪0-3‬‬

‫‪20‬‬

‫‪1‬‬

‫‪3‬‬

‫‪0-3-4‬‬

‫‪32‬‬

‫‪1‬‬

‫‪4‬‬

‫‪0-5‬‬

‫∞‬

‫‪0‬‬

‫‪5‬‬

‫روش حریصانه‬

‫‪15‬‬

‫‪20‬‬

‫‪35‬‬ ‫‪5‬‬

‫‪20‬‬

‫‪10‬‬

‫‪10‬‬

‫‪15‬‬ ‫‪nodes‬‬

‫‪1‬‬

‫‪50‬‬

‫‪0‬‬

‫‪14‬‬ ‫‪4‬‬

‫‪12‬‬

‫‪3‬‬

‫‪78‬‬

‫کوتاهترین مسیرها از مبدأ واحد‬ ‫‪2‬‬

‫‪25‬‬ ‫‪30‬‬

‫‪path‬‬

‫‪dist‬‬

‫‪S‬‬

‫‪0-0‬‬

‫‪0‬‬

‫‪1‬‬

‫‪0‬‬

‫‪0-3-1‬‬

‫‪35‬‬

‫‪1‬‬

‫‪1‬‬

‫‪0-3-1-2‬‬

‫‪60‬‬

‫‪1‬‬

‫‪2‬‬

‫‪0-3‬‬

‫‪20‬‬

‫‪1‬‬

‫‪3‬‬

‫‪0-3-4‬‬

‫‪32‬‬

‫‪1‬‬

‫‪4‬‬

‫‪0-5‬‬

‫∞‬

‫‪0‬‬

‫‪5‬‬

‫روش حریصانه‬

‫‪15‬‬

‫‪20‬‬

‫‪35‬‬ ‫‪5‬‬

‫‪20‬‬

‫‪10‬‬

‫‪10‬‬

‫‪15‬‬ ‫‪nodes‬‬

‫‪1‬‬

‫‪50‬‬

‫‪0‬‬

‫‪14‬‬ ‫‪4‬‬

‫‪12‬‬

‫‪3‬‬

‫‪79‬‬

‫کوتاهترین مسیرها از مبدأ واحد‬ ‫‪2‬‬

‫‪25‬‬ ‫‪30‬‬

‫‪path‬‬

‫‪dist‬‬

‫‪S‬‬

‫‪0-0‬‬

‫‪0‬‬

‫‪1‬‬

‫‪0‬‬

‫‪0-3-1‬‬

‫‪35‬‬

‫‪1‬‬

‫‪1‬‬

‫‪0-3-1-2‬‬

‫‪60‬‬

‫‪1‬‬

‫‪2‬‬

‫‪0-3‬‬

‫‪20‬‬

‫‪1‬‬

‫‪3‬‬

‫‪0-3-4‬‬

‫‪32‬‬

‫‪1‬‬

‫‪4‬‬

‫‪0-5‬‬

‫∞‬

‫‪1‬‬

‫‪5‬‬

‫روش حریصانه‬

‫‪15‬‬

‫‪20‬‬

‫‪35‬‬ ‫‪5‬‬

‫‪20‬‬

‫‪10‬‬

‫‪10‬‬

‫‪15‬‬ ‫‪nodes‬‬

‫‪1‬‬

‫‪50‬‬

‫‪0‬‬

‫‪14‬‬ ‫‪4‬‬

‫‪12‬‬

‫‪3‬‬

‫‪80‬‬

‫کوتاهترین مسیرها از مبدأ واحد‬ ‫‪‬‬ ‫‪‬‬

‫محاسبه مرتبه زمانی‬ ‫عملیات شامل ‪ n‬مرحله می باشد )‪ n‬تعداد گره های‬ ‫گراف(‪ ،‬در هر یک از این ‪ n‬مرحله‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫‪‬‬

‫ابتدا برای هر گره مقدار ‪ dist‬را مشخص می کنیم‪ .‬برای هر‬ ‫گره‪ ،‬این کار با مرتبه زمانی ‪ (O(1‬قابل انجام است‪  .‬برای‬ ‫‪ n‬گره این کار از مرتبه زمانی ‪ (O(n‬قابل انجام است‪.‬‬ ‫سپس در ستون ‪ dist‬کوچکترین مقدار را مشخص می کنیم تا‬ ‫گره مربوط به آن را انتخاب کنیم‪ .‬این کار با مرتبه زمانی‬ ‫‪ (O(n‬قابل انجام است‪.‬‬ ‫پس هر یک از ‪ n‬مرحله‪ ،‬با مرتبه زمانی ‪ (O(n‬قابل انجام‬ ‫است‪.‬‬

‫در نتیجه مرتبه زمانی کل الگوریتم ‪ (O(n2‬می باشد‪.‬‬ ‫روش حریصانه‬

‫‪81‬‬

‫مطالب مورد بحث‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬

‫کوله پشتی غیر صفر و یک‬ ‫زمانبندی بهینه اجرای برنامه ها‬ ‫درخت پوشای مینیمم‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬ ‫‪‬‬

‫الگوریتم ‪prim‬‬ ‫الگوریتم ‪Kruskal‬‬

‫کوتاهترین مسیرها از مبدأ واحد‬ ‫فشرده سازی با استفاده از کد ‪Huffman‬‬

‫روش حریصانه‬

‫‪82‬‬

‫فشرده سازی با استفاده از کد‬ ‫هافمن‬ ‫‪‬‬ ‫‪‬‬

‫مفهوم فشرده سازی )‪(compression‬‬ ‫به یک روش ‪ encoding‬و یک روش ‪decoding‬‬ ‫نیاز داریم‪.‬‬ ‫‪‬‬

‫‪‬‬ ‫‪‬‬

‫با ‪ encryption‬و ‪ decryption‬اشتباه نشود‪.‬‬

‫مزیت‪ :‬صرفه جویی در هزینه ذخیره و ارسال‬ ‫دو روش مختلف ‪encoding‬‬ ‫‪‬‬

‫انکدینگ با طول ثابت‪ :‬کد مربوط به تمام نویسه ها از‬ ‫نظر طول یکسان می باشند‪.‬‬ ‫‪‬‬

‫‪‬‬

‫در سیستم ‪ ASCII‬برای هر کاراکتر ‪ 8‬بیت در نظر گرفته شده‬ ‫است‪.‬‬

‫انکدینگ با طول متغیر‪ :‬کد مربوط به نویسه های‬ ‫مختلف ممکن است از نظر طول با هم یکسان نباشند‪.‬‬

‫روش حریصانه‬

‫‪83‬‬

‫فشرده سازی با استفاده از کد‬ ‫هافمن‬ ‫‪‬‬

‫در روش انکدینگ با طول متغیر‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫می توان به نویسه هایی که تکرار بیشتری دارند‪،‬‬ ‫کد کوتاهتری نسبت داد تا در مجموع میزان فشرده‬ ‫سازی افزایش یابد‪.‬‬ ‫مشکل اصلی‪ :‬نیاز به درج جداکننده در زمان‬ ‫انکدینگ‬

‫روش هافمن یک روش انکدینگ با طول متغیر‬ ‫است که مشکل فوق را حل کرده است یعنی‬ ‫نیازی به درج جداکننده ندارد‪.‬‬

‫روش حریصانه‬

‫‪84‬‬

‫فشرده سازی با استفاده از کد‬ ‫هافمن‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫مثال‪ :‬متن اولیه شامل ‪ 8100‬نویسه‬ ‫حجم متن در سیستم اسکی‬

‫‪2000‬‬ ‫‪a‬‬ ‫‪codebook‬‬ ‫‪ ‬برای هر نویسه ‪ 8‬بیت ‪  64800‬بیت‬ ‫‪1000‬‬ ‫‪b‬‬ ‫کد‬ ‫نویسه‬ ‫ثابت ‪500‬‬ ‫‪c‬‬ ‫حجم متن در یک سیستم انکدینگ با طول‬ ‫مربوطه‬ ‫‪500‬‬ ‫‪d‬‬ ‫‪ ‬برای ‪ 6‬نویسه مختلف ‪ ،‬کدی با طول ‪ 3‬بیت‬ ‫‪000‬‬ ‫نویسه کافی‪a‬‬ ‫تعداداست کد‬ ‫‪‬‬

‫‪‬‬

‫نویسه‬

‫تعداد‬ ‫تکرار‬

‫تکرار‬ ‫‪e‬‬ ‫‪b‬‬

‫برای هر نویسه ‪ 3‬بیت ‪  24300‬بیت‬

‫حجم متن با استفاده از روش‬ ‫‪(2000*2) + (1000*3) +‬‬ ‫= )‪(2000*2) + (2100*2‬‬

‫هافمن‪a‬‬

‫‪2000‬‬ ‫‪cf‬‬ ‫‪1000‬‬ ‫‪d‬‬

‫مربوطه‬ ‫‪2000‬‬ ‫‪001‬‬ ‫‪00‬‬ ‫‪2100‬‬ ‫‪010‬‬

‫‪101‬‬ ‫‪b‬‬ ‫‪011‬‬ ‫‪1000‬‬ ‫‪500‬‬ ‫‪c‬‬ ‫)‪100 (500*4‬‬ ‫‪e‬‬ ‫)‪+ (500*4‬‬ ‫‪+‬‬ ‫‪1001‬‬ ‫‪500‬‬ ‫‪d‬‬ ‫‪101‬‬ ‫‪f‬‬ ‫‪01 19100‬‬ ‫‪2000bits e‬‬ ‫‪f‬‬

‫روش حریصانه‬

‫‪2100‬‬

‫‪11‬‬

‫‪85‬‬

‫فشرده سازی با استفاده از کد‬ ‫هافمن‬ ‫‪‬‬

‫‪‬‬

‫‪‬‬

‫در روش هافمن کد هیچ نویسه ای‪ ،‬پیشوند کد نویسه‬ ‫دیگری نمی باشد‪ .‬در نتیجه نیازی به جدا کننده نمی‬ ‫باشد‪.‬‬ ‫اصطلحا کدها پیشوند‪-‬آزاد می باشند )‪prefix-free‬‬ ‫‪(code‬‬ ‫کد‬ ‫نویسه‬ ‫مثل با مربوطه‬ ‫استفاده از ‪ codebook‬صفحه قبل می توان‬ ‫‪00‬دیکد کرد‪:‬‬ ‫متن ‪a‬زیر را‬ ‫‪b‬‬

‫‪101‬‬

‫‪c‬‬

‫‪1000‬‬

‫‪d‬‬

‫‪1001‬‬

‫‪e‬‬

‫‪01‬‬

‫‪f‬‬

‫‪11‬‬

‫روش حریصانه‬

‫‪Input: 010010001001‬‬ ‫‪Output: eacd‬‬

‫‪‬‬

‫‪‬‬

‫‪86‬‬

‫فشرده سازی با استفاده از کد‬ ‫هافمن‬ ‫‪‬‬

‫روش هافمن برای بدست آوردن کد نویسه ها‬ ‫‪‬‬

‫محاسبه تعداد تکرار یا بسامدتمام نویسه های موجود در متن‬ ‫‪‬‬

‫‪‬‬

‫هر نویسه را بهمراه بسامد آن بعنوان ریشه یک درخت در نظر می‬ ‫گیریم‪.‬‬ ‫‪‬‬

‫‪‬‬

‫داشت‪.‬‬ ‫پس در حالت اولیه یک جنگل خواهیم‬ ‫‪a:30 b:10 c:7 d:8 e:40‬‬ ‫‪f:14‬‬

‫در هر مرحله‬ ‫‪‬‬ ‫‪‬‬

‫‪‬‬

‫یا استفاده از یک برآورد معتبر‬

‫دو درختی که دارای کمترین بسامد در ریشه می باشند را انتخاب کرده‬ ‫آن دو درخت را با هم ادغام می کنیم و درخت جدیدی می سازیم که بسامد ریشه‬ ‫آن مجموع بسامد ریشه های دو درخت می باشد و درختی که بسامد ریشه اس‬ ‫کمتر بوده را زیردرخت چپ و درختی را که بسامد ریشه اش بیشتر بوده را‬ ‫زیردرخت راست قرار می دهیم‪ .‬درخت جدید را جایگزین دو درخت اولیه می کنیم‪.‬‬

‫این کار را تا زمانیکه تنها یک درخت باقی بماند ادامه می دهیم‪.‬‬

‫روش حریصانه‬

‫‪87‬‬

‫فشرده سازی با استفاده از کد‬ ‫هافمن‬ ‫‪‬‬

‫در درخت حاصل‬ ‫‪‬‬

‫‪‬‬

‫نویسه ها در برگها قرار می گیرند )نشانه پیشوند آزاد‬ ‫بودن(‪.‬‬ ‫کد هر نویسه در مسیر ریشه تا آن نویسه نهفته است‬ ‫‪‬‬

‫‪‬‬

‫حرکت به سمت چپ را معادل ‪ 0‬و حرکت به راست را معادل ‪ 1‬در‬ ‫نظر می گیریم‪.‬‬

‫برای دیکدینگ یک رشته‪:‬‬ ‫‪‬‬

‫از ریشه حرکت می کنیم و با مشاهده هر ‪ 0‬در ورودی به‬ ‫سمت چپ و با مشاهده هر ‪ 1‬در ورودی به سمت راست‬ ‫حرکت می کنیم تا به برگ برسیم و نویسه موجود در آن‬ ‫برگ را به خروجی اضافه می کنیم و دوباره به ریشه رفته‬ ‫و کار را از آنجا ادامه می دهیم‪.‬‬

‫روش حریصانه‬

‫‪88‬‬