سوال در رابطه با طراحی الگوریتم

در اين بخش مي‌توانيد در مباحث مربوط ديگر زبانهاي برنامه نويسي به بحث بپردازيد

مدیران انجمن: Azadi.Isatis, abbas.m.k, athlon64x2, شوراي نظارت

ارسال پست
Major II
Major II
پست: 96
تاریخ عضویت: شنبه ۲۶ اسفند ۱۳۸۵, ۸:۰۸ ق.ظ
محل اقامت: مهم نیست که کجام ، همه جای ایران سرای من است
سپاس‌های ارسالی: 150 بار
سپاس‌های دریافتی: 155 بار

سوال در رابطه با طراحی الگوریتم

پست توسط free love »

سلام.

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

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

ممنونم
Captain II
Captain II
نمایه کاربر
پست: 246
تاریخ عضویت: یک‌شنبه ۹ فروردین ۱۳۸۸, ۹:۱۱ ق.ظ
سپاس‌های ارسالی: 780 بار
سپاس‌های دریافتی: 791 بار
تماس:

Re: سوال در رابطه با طراحی الگوریتم

پست توسط arashtabaie »

برای یافتن درخت پوشای مینیمال سه الگوریتم مشهور وجود داره: الگوریتم دیکسترا که یک روش greedy هست، الگوریتم کراسکال و الگوریتم پریم. چون شما مشخص نکرده بودید منظورتون تغییر کدام الگوریتم هست، من خودم کراسکال رو انتخاب کردم. امیدوارم منظورتون همون باشه چون برعکس کردن الگوریتم های greedy که اصولا کار خیلی سختی نیست...
برای این کار راهی که به نظر من رسید اینه که:
ابتدا مجموعه رئوس رو به عنوان مجموعه درخت ها در نظر میگیریم. سپس مجموعه ی یالها رو به صورت نزولی مرتب میکنیم. حال در یک for loop سعی میکنیم به ترتیب یالها با بزرگترین وزن رو انتخاب کنیم به این صورت که ایجاد دور نکند. یعنی چک میکنیم اگر دو راسی که این یال به آنها تعلق دارد، اگر در حال حاضر در یک درخت هستند، این راس را نمیتوان در نظر گرفت. و اگر در یک درخت نیستند آنها را با این یال(که بیشترین وزن بین یالهای ممکن بین این دو گراف را دارد، چون یالها را بر اساس وزن به صورت نزولی مرتب کرده ایم) به هم وصل می کنیم.
Major II
Major II
پست: 96
تاریخ عضویت: شنبه ۲۶ اسفند ۱۳۸۵, ۸:۰۸ ق.ظ
محل اقامت: مهم نیست که کجام ، همه جای ایران سرای من است
سپاس‌های ارسالی: 150 بار
سپاس‌های دریافتی: 155 بار

Re: سوال در رابطه با طراحی الگوریتم

پست توسط free love »

سلام

محبت میکنید روی الگوریتم پریم توضیح بدید و منظورم از اعمال تغییرات روی برنامه یا حداقل روی شبه کد هست .اگر شبه کد برنامه رو در اختیار ندارید بفرمایید تا بنده بذارم و روی اون بحث کنیم .

خیلی ممنون.
Captain II
Captain II
نمایه کاربر
پست: 246
تاریخ عضویت: یک‌شنبه ۹ فروردین ۱۳۸۸, ۹:۱۱ ق.ظ
سپاس‌های ارسالی: 780 بار
سپاس‌های دریافتی: 791 بار
تماس:

Re: سوال در رابطه با طراحی الگوریتم

پست توسط arashtabaie »

الگوریتم پریم به صورت زیر در میاید:

 Please Login or Register to see this code   در آنG یک Connected Graph است، و r یک گره فرضی که به عنوان ریشه به برنامه پاس میشه!
[U][U]
[/U][/U]
Major II
Major II
پست: 96
تاریخ عضویت: شنبه ۲۶ اسفند ۱۳۸۵, ۸:۰۸ ق.ظ
محل اقامت: مهم نیست که کجام ، همه جای ایران سرای من است
سپاس‌های ارسالی: 150 بار
سپاس‌های دریافتی: 155 بار

Re: سوال در رابطه با طراحی الگوریتم

پست توسط free love »

بسیار بسیار ممنونم . اما ممکنه بفرمایید تغییرات رو روی این الگوریتم باید چطور اعمال کنیم .

Please Login or Register to see this code
ارسال پست

بازگشت به “Other Programming”