Широкий выбор медицинских товаров в магазине Диамаг
ورود  \/ 
x
ثبت  \/ 
x

منو

برخی از ویدیو های آموزشی ما

در این ویدیو نرم افزار های تست کارت گرافیک رو بررسی میکنیم

الگوریتم راشال

  • نوشته شده توسط شیخ محمدی
  • دسته: هوش مصنوعی
  • بازدید: 4787

سلام دوستان
می خوام توی این پست در قالب یک مسئله عملی الگوریتمی رو براتون توضیح بدم.
فرض کنین نقشه شهرهای یک استان رو به شما میدن که بین اونا جاده ای وجود نداره هنوز، اما مسیر های مستقیم شهرها رو (البته با در نظر گرفتن مقادیر امتیاز راه سازی بین دو شهر) محاسبه کردن و بهتون دادن.مثل شکل زیر.

الگوریتم راشال

امتیاز راه سازی بین دو شهر رو که گفتم منظورم اینه که امکان داره بین دو شهر یک کوه بزرگ قرار داشته باشه که امتیاز منفی محسوب شده و مسیر مستقیم اگه مثلا ۳۰ KM باشه در نظر بگیرن ۴۰ KM و شاید هم یک مسیر به علت قرار گرفتن مکان های اقتصادی بین راهی امتیازی اختصاص بهش داده بشه که اگر فاصله واقعی اون با شهر مربوطه ۳۰ KM باشه در نظر بگیرن ۲۵ کیلومتر.
بگذریم، حالا به شما میگن می خوایم طوری بین اینا جاده کشی کنیم که از هر شهر به بقیه مسیری باشه(میتونیم هم از شهرهای دیگه عبور کنیم) و بهترین راه سازی ای که می تونیم انجام بدیم (یعنی مسیرها کوتاه باشه و هزینه راه سازی کمتر) رو شما به ما نشون بدین.
به نظرتون چه کار باید کرد؟
یک الگوریتم معروف در دنیای Data Structure به نام راشال هست که میگه:
در این مواقع باید شما نقشه ای رو که بهتون دادن رو اول فقط شهرها(همون گره ها در مبحث گراف) رو کشیده و بعد به صورت صعودی مسیرها(همون یال ها در مبحث گراف) رو انتخاب و رسم کنین و مواظب هم باشین که با رسم مسیر یک حلقه تشکیل نشه.با توجه به توضیحات الگوریتم راشال اولین مسیر که باید رسم بشه مسیر شماره ۱ هست.بعدی مسیر شماره ۲ و بعد ۳ و ۴ و الی آخر (اگه هنگام رسم مسیر به حلقه برخورد کردین باید از اون مسیر صرف نظر کنین و برین سراغ بعدی)

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

نویسنده : آرش هنرور

آرش هنرور

Share this post

Submit to DeliciousSubmit to DiggSubmit to FacebookSubmit to Google PlusSubmit to StumbleuponSubmit to TechnoratiSubmit to TwitterSubmit to LinkedIn