صفحه محصول - پاورپوینت طراحی الگوریتم

پاورپوینت طراحی الگوریتم (pptx) 11 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 11 اسلاید

قسمتی از متن PowerPoint (.pptx) :

بسم اللّه الرحمن الرحیم طراحی الگوریتم الگوریتم رنگ آمیزی حریصانه گراف: Greedy coloring: این روش رئوس گراف را بر اساس ترتیب مشخصی انتخاب کرده و تلاش می‌کند با رنگ‌هایی که در رنگ آمیزی رئوس قبلی به کار رفته آن را به گونه‌ای رنگ کند که هیچ دو راس مجاوری دارای رنگ یکسان نباشند. در صورتیکه امکان استفاده از رنگ‌های پیشین نباشد یک رنگ جدید به مجموعه رنگ‌ها اضافه می‌شود. اگرچه با استفاده از این الگوریتم در همه حالات جواب بهینه برای مسائل رنگ آمیزی بدست نخواهد آمد اما به طور کلی از آن برای کمینه کردن تعداد رنگهای لازم برای رنگ آمیزی گراف استفاده میشود. مرتب سازی رئوس : معمولا الگوریتم رنگ آمیزی آزمند، بدترین عملکرد خود را بر روی گراف‌های کامل دوبخشی k n,n دارد که یال نظیر رئوس xi و xj که i=j حذف شده‌اند. در صورتیکه پس از شماره گذاری رئوس، دو راسی که در یک یال حذف شده قرار دارند به صورت متوالی شماره گذاری شوند، چنین گرافی با n رنگ، رنگ آمیزی میشود درحالیکه یک گراف ۲-رنگ پذیر است. بنابراین ترتیب رئوس در الگوریتم آزمند اهمیت فراوانی دارد. تعدادی از معروف ترین الگوریتم‌های شماره گذاری رئوس عبارتند از: -ترتیب خاص از پیش تعیین شده (SPECIFIC-PREDEFINED-ORDERING:SP) -ترتیب کاهش درجه نودها (DECREASING DEGREE ORDERING: DD) به عبارت دیگر هر بار راس رنگ نشده با بزرگترین درجه -ترتیب افزایش درجه نودها (INCREASING DEGREE ORDERING: ID) به عبارت دیگر هر بار راس رنگ نشده با کوچکترین درجه الگوریتم رنگ آمیزی گراف به روش عقب گرد:  در این روش هر نود پس از رنگ آمیزی چک میشود که اگر با نود قبلی در ارتباط است،همرنگ نباشد.در اینجا m تعداد رنگ ها و n تعداد نود هاست.   void m_coloring (index i )  {   int color ;   if ( promising (i))   if ( i == n)   cout << vcolor[1] through vcolor [n];   else  for (color = 1; color ≤ m; color ++) {    vcolor [ i + 1] = color ;  m_coloring (i + 1);  }  }    } bool promising ( index i )  {  index j ;  bool switch ;  switch = true;      j = 1;   while ( j < i && switch ) {   if ( W [i] [j] && vcolor [i] == vcolor[j])  switch = false ;  j ++;  }   return switch ; 3 2 5 4 1 5 4 3 2 1 5 3 2 4 1 5 3 4 2 1 5 3 4 2 1 5 3 4 2 1 5 3 4 2 1 5 3 4 2 1