طراحی وب سایت

در شماره های گذشته، با درخت و ساختار آن آشنا شدیم و بررسی کردیم که یک درخت، گرافی است همبند و فاقد دور یا حلقه. یکی از انواع درخت، درخت پوشای کمینه است، یعنی درختی که کمترین یال را داشته باشد و در ضمن شامل تمامی رئوس نیز باشد. الگوریتم هایی زیادی برای محاسبه درخت پوشای کمینه وجود دارد. یکی از این الگوریتم ها، الگوریتم پرایم است. الگوریتم پرایم برای به دست آوردن درخت پوشای کمینه بر اساس یک گراف همبند وزن دار است.
ورودی این الگوریتم یک گراف همبند وزن دار با مجموعه v است که شامل رئوس گراف و e (یال های گراف) می شود.
خروجی الگوریتم یک مجموعه به نام vnew، شامل رئوس درخت حاصل و یک مجموعه enew (یال های درخت) می شود. اما این الگوریتم چگونه این کار را می کند؟
بگذارید روش کار این الگوریتم را با یک مثال بیان کنیم:
فرض کنیم گرافی داریم با رئوس a، b، c، d، e، f، g و ماتریس مجاورت به صورت زیر:
ماتریس مجاورت ماتریسی است که یال های یک گراف را نشان می دهد. از روی ماتریس مجاورت می توان فهمید از یک راس بخصوص تا راس دیگر یالی وجود دارد یا نه؟ و اگر وجود دارد اندازه یال یا همان وزن یال چقدر است؟
بسیار خب، در الگوریتم پرایم یک راس را به دلخواه انتخاب می کنیم و آن را در مجموعه vnew قرار می دهیم. مثلا راس d، سپس تمامی یال های خروجی از d را در می آوریم و یالی که کمترین وزن را دارد در نظر می گیریم و راس دیگر آن را در vnew و یال مربوط را در enew قرار می دهیم. برای مثال، یال ad در vnew قرار می گیرد و راس a را نیز به مجموعه enew می افزاییم.
در مرحله بعد باید یال هایی را پیدا کنیم که به a یا d نزدیک باشد. در مثال بالا کوتاه ترین یالی که در شرط صدق می کند، یال df است. وزن یال ab برابر ? است، یال db برابر ?، de برابر ?? و df برابر ?. پس کوتاه ترین یال df است. این یال در مجموعه enew قرار می گیرد و راس f را در مجموعه vnew اضافه می کنیم.
این کار را آنقدر ادامه می دهیم تا تعداد اعضای مجموعه vnew برابر v شود. چون قرار است درخت پوشا باشد، پس باید شامل تمامی رئوس شود.
از طریق مجموعه enew نیز می توان درخت مورد نظر را رسم کرد.
برای مثال ما درخت پوشای کمینه دارای یال های زیر است:
{{a,b},{a,d},{b,e},{c,e},{d,f},{e,g}}
شکل گراف به صورت روبه روست و یال هایی که با رنگ سبز مشخص شده اند، نشان دهنده درخت پوشای کمینه هستند.
شبه کد الگوریتم پرایم به صورت زیر است:
function prim(m,a)
[init]
define nearest[2..n], distance[2..n]
set f = 0
for i=2 to n
nearest[i] = 1
distance[i]=a[1,i]
end-of-for
for j=1 to n-1
min = infinity
for i = 2 to n
if 0«=distance[i]«=min
min = distance[i]
vnear=i
end-of-for-i
e=edge connectiong vertices indexed by vnear and nearest[vnear]
add e to f
distance[vnear]=-1
for i=2 to n
if a[1,vnear]«distance[i]
then distance[i] =a[i,vnear]
nearest[i] = vnear
end-of-for-i
end-of-for-j
end
کد منبع این الگوریتم به زبان c را می توانید از نشانی زیر دریافت کنید:
http://clicklinks.ir/30213a
اما پیچیدگی زمانی الگوریتم پرایم عمل غالب در الگوریتم بالا مطابق شبه کد حلقه for-j است که دو حلقه تودرتو دارد و عملیات درون آن را می توان به عنوان عمل غالب در نظر گرفت.
حلقه اصلی که همان for-j است به اندازه n-1 بار تکرار می شود. در هر بار تکرار حلقه اصلی، دو حلقه داخلی هر کدام n-1 بار اجرا می شوند. اما مدت زمان اجرا شدن حلقه for-j از رابطه زیر به دست می آید:
t(n) = 2(n-1)(n-1)
چون عمل غالب در این الگوریتم حلقه for-j است، می توان مدت زمان اجرا شدن الگوریتم را هم ارز با مدت زمان اجرای حلقه for-j در نظر گرفت، در نتیجه مرتبه اجرایی الگوریتم بالا از مرتبه o(n2)) n2 است.
حال سوال این است که الگوریتم بالا که به روش حریصانه است، درخت پوشای کمینه را درست می کند یا نه؟ بهتر است بگوییم درخت حاصل درخت پوشای کمینه است یا نه؟ چون در هر مرحله از اجرای الگوریتم یالی انتخاب می شود که کمترین اندازه را داشته باشد، این طور به نظر می رسد که درخت حاصل پوشای کمینه است و جواب الگوریتم درست است اما به هر حال چون روشی که ما در بالا برای نوشتن الگوریتم استفاده کردیم، روش حریصانه است، بهتر است که پس از به دست آمدن جواب، صحت بهینه بودن پاسخ بررسی شود.
امیر بهاءالدین سبط الشیخ

منبع : جام جم آنلاین  تاریخ : 18   مهر   1389  شاخه : برنامه نویسی