طراحی الگوریتم ها جلسه چهارم

فصل چهارم:

روش حریصانه در طراحی الگوریتم

الگوریتم حریصانه ، به ترتیب عناصر را گرفته ، هر بار آن عنصری را که طبق ملاکی معین ”بهترین“ به نظر می رسد، بدون توجه به انتخاب هایی که قبلا انجام داده یا در آینده انجام خواهد داد، بر می دارد.

الگوریتم حریصانه ، همانند برنامه نویسی پویا غالبا برای حل مسائل بهینه سازی به کار می روند، ولی روش حریصانه صراحت بیشتری دارد.

در روش حریصانه ، تقسیم به نمونه های کوچک تر صورت نمی پذیرد.

الگوریتم حریصانه با انجام یک سری انتخاب، که هر یک در لحظه ای خاص ،بهترین به نظر می رسد عمل می کند، یعنی انتخاب در جای خود بهینه است.امید این است که یک حل بهینه سرتاسری یافت شود، ولی همواره چنین نیست.

برای یک الگوریتم مفروض باید تعیین کرد که آیا حل همواره بهینه است یا خیر.

الگوریتم حریصانه ، کار را با یک مجموعه تهی آغاز کرده به ترتیب عناصری به مجموعه اضافه می کند تا این مجموعه حلی برای نمونه ای از یک مسئله را نشان دهد.

هر دور تکرار ، شامل مولفه های زیر است:

1- روال انتخاب، عنصربعدی را که باید به مجموعه اضافه شود،انتخاب می کند.انتخاب طبق یک ملاک حریصانه است.

2- بررسی امکان سنجی ، تعیین می کند که آیا مجموعه جدید برای رسیدن به حل،عملی است یا خیر.

3- بررسی راه حل ، تعیین می کند که آیا مجموعه جدید ، حل نمونه را ارائه می کند یا خیر.

1-4 درخت های پو شای کمینه

فرض کنید طراح شهری می خواهد چند شهر معین را با جاده به هم وصل کند، به قسمی که مردم بتوانند از هر شهر به شهر دیگر بروند. اگر محدودیت بودجه ای در کار باشد ، ممکن است طراح بخواهد این کار را با حداقل مقدار جاده کشی انجام دهد.

برای این مسئله دو الگوریتم حریصانه متفاوت : پریم و کروسکال بررسی می شود.

هر یک از این الگوریتم ها از یک ویژگی بهینه محلی استفاده می کند.

تضمینی وجود ندارد که یک الگوریتم حریصانه همواره حل بهینه بدهد، ثابت می شود که الگوریتم های کروسکال و پریم همواره درخت های پوشای کمینه را ایجاد می کنند.

1-1-4الگوریتم پریم

الگوریتم پریم با زیر مجموعه ای تهی از یال های F و زیرمجموعه ای از رئوس Y آغاز می شود، زیرمجموعه حاوی یک راس دلخواه است. به عنوان مقداراولیه، {v1}

را به Y می دهیم . نزدیک ترین را س به Y ، راسی در V – Y است که توسط یالی با وزن کمینه به راسی در Y متصل است.

الگوریتم 1-4: الگوریتم پریم

void prim ( int n,

const number W[ ] [ ],

set_ of_edges & F )

{

index i , vnear;

number min;

edge e;

index nearest [2..n];

number distance [2..n];

F = Ø ;

for ( i = 2 ; i ≤ n ; i ++) {

narest [i] = 1 ;

distance [i] = W [1] [i] ;

}

repeat ( n-1 times ) {

min = ∞ ;

for ( i = 2 ; i < = n ; i ++)

if ( 0 ≤ distance [i] < min ) {

min = distance [i] ;

vnear = i ;

}

e = edge connecting vertices indexed by near and nearest [ vnear ] ;

add e to F ;

distance [ vnear ] = -1 ;

for ( i = 2 ; i ≤ n ; i ++)

if ( W[i] [ vnear ] < distance [i]) {

distance [i] = W [i] [ vnear ] ;

nearest [i] = vnear ;

}

تحلیل پیچیدگی زمانی در حالت معمول برای ا لگوریتم 1-4(الگوریتم پریم)

عمل اصلی: در حلقه repeat دو حلقه وجود دارد که هر یک (n – 1 )

بار تکرار می شود . اجرای دستورات داخل هر یک از آن ها را می توان

به عنوان یک بار اجرای عمل اصل در نظر گرفت.

اندازه ورودی: n ، تعداد رئوس.

T (n) = 2 ( n – 1) ( n – 1) Є θ ( n²)

قضیه 1-4

الگوریتم پریم همواره یک درخت پوشای کمینه تولید می کند.

اثبات : برای آ ن که نشان دهیم مجموعه F پس از هر بار تکرارحلقه repeat، امید بخش است ازاستقرا استفاده می کنیم.

مبنای استقرا : واضح است که مجموعه Ø امید بخش است.

الگوریتم 4-2: الگوریتم کروسکال

void kruskal ( int n , int m,

set _ of _ edges E,

set _ of _edges & F )

{

index i , j ;

set _pointer p , q;

edge e ;

sort the m edges in E by weight in

nondecreasing order;

F = Ø ;

intitial (n) ;

while( number of edges in F is less than n-1){

e = edge with least weight not yet

considered ;

i , j = indices of vertices connected by e;

p = find (i) ;

q = find (i) ;

if (! equal ( p, q )) {

merge ( p , q ) ;

add e to F ;

}

تحلیل پیچیدگی زمانی در بدترین حالت برای ا لگوریتم 2-4(الگوریتم کروسکال)

عمل اصلی: یک دستور مقایسه.

اندازه ورودی : n ، تعداد رئوس و m تعداد یال ها.

درباره این الگوریتم سه نکته را باید در نظر داشت:

1- زمان لازم برای مرتب سازی یال ها .

W (m) Є θ ( m lg m)

2- زمان در حلقه while .

W (m) Є θ ( m lg m)

3- زمان لازم برا ی مقدار دهی اولیه به n مجموعه متمایز.

W ( m, n ) Є θ( m lg m)

در نتیجه ، بدترین حالت:

( n² lg n² ) = θ ( n²lg n )W ( m, n ) Є θ

قضیه 2-4

الگوریتم کروسکال همواره یک درخت پوشای کمینه تولید می کند.

اثبات : اثبات از طریق استقرا با شروع از مجموعه ای تهی از یال ها آغاز می شود.

2-4 الگوریتم دیکسترا برای کوتاهترین مسیر تک مبدا

برای کوتاهترین مسیر از هر راس به همه رئوس دیگر در یک گراف موزون و بدون جهت یک الگوریتم(θ(n² از روش حریصانه داریم، که آن دیکسترا نام دارد.

الگوریتم را با این فرض ارائه می دهیم که از راس مورد نظر به هر یک از رئوس دیگر، مسیری وجود دارد.

این الگوریتم مشابه الگوریتم پریم برای مسئله درخت پوشای کمینه است.

الگوریتم3-4: الگوریتم دیکسترا

void dijkstra ( int n,

const number W[ ] [ ],

set _ of _ edges & F)

{

index i , vnear,

edge e ;

index touch [2..n];

number length[2..n];

F = Ø ;

for ( i = 2; i ≤ n ; i ++ ) {

touch [i] = 1 ;

length [i] = W [1][i];

}

repeat ( n – 1 times ) {

min = ∞ ;

for ( i = 2 ; i ≤ n ; i ++)

if ( 0 <= length [i] < min ) {

min = length [i] ;

vnear = i ;

}

e = edge from vertix indexed by touch [vnear]

to vertex indexed by vnear;

add e to F;

for ( i = 2 ; i ≤ n; i ++)

if ( length [vnear] + W [vnear] [i] < length[i]) {

length [i] = length [vnear] + W [vnear] [i];

touch [i] = vnear ;

}

length [vnear] = -1;

}

قضیه 3-4

تنها زمان بندی که زمان کل درسیستم را کمینه سازی می کند، زمان بندی است که در آن کارها بر حسب افزایش زمان ارائه خدمات مرتب می شوند.

الگوریتم 4-4 : زمان بندی با مهلت معین

مسئله : تعیین زمان بندی با سود کل بیشینه ، با این فرض که هر کاری دارای سود است و فقط وقتی قابل حصول است که آن کار در مهلت مقررش انجام شود.

void schedule ( int n ,

const int deadline [ ] ,

sequence _ of _ integer& j )

{

index i ;

sequence_ of_integer K ;

j = [1];

for ( i = 2 ; i ≤ n ; i ++) {

K = J with i added according to nondecreasing

values of deadline [i];

if ( K is feasible)

J = K;

}

تحلیل پیچیدگی زمانی در بدترین حالت برای ا لگوریتم زمان بندی با مهلت معین

عمل اصلی: باید برای مرتب سازی کارها، مقایسه هایی انجام پذیرد و هنگامی که K با J (پس از افزوده شدن کار i ام ) مساوی قرار داده می شود،به مقایسه های بیشتری نیاز داریم و هنگامی که امکان پذیر بودن K چک می شود، به مقا یسه های بیشتری نیاز است. عمل اصلی مقایسه است.

اندازه ورودی : n ، تعداد کارها.

W (n) Є θ (n²)

قضیه 4-4

الگوریتم 4-4 ( زمان بندی با مهلت معین ) همواره یک مجموعه بهینه تولید می کند.

اثبات: ازطریق استقرا روی تعداد کارها،n،صورت می پذیرد.

مبنای استقرا: اگر یک کار داشته باشیم ، قضیه بر قراراست.

قضیه 5-4

الگوریتم هافمن یک کد دودویی بهینه تولید می کند.

اثبات : ازطریق استقرا صورت می گیرد. با این فرض که درخت های به دست آمده درمرحله i، انشعاب هایی در درخت دودویی متناظر با کد بهینه اند، نشان می دهیم که درخت های بدست آمده در مرحله (( i + 1 نیز انشعاب هایی در درخت دودویی متناظر با یک کد بهینه اند.

طراحی الگوریتم ها جلسه چهارم

مطالب مشابه :

دانلود جزوه طراحی الگوریتم

آموزش طراحی الگوریتم به صورت تصویری

طراحی الگوریتم ها 1

طراحی الگوريتم ها؛ ويراست نهم - بهار 1394

طراحی الگوریتم ها 3

طراحی الگوریتم ها جلسه چهارم

طراحی الگوریتم