لینک پرداخت و دانلود *پایین مطلب*
فرمت فایل:Word (قابل ویرایش و آماده پرینت)
تعداد صفحه10
فهرست مطالب
تحلیل مساله کوتاهترین مسیر در گراف جهت دار
یک ایده برنامه نویسی پویا :
ضمایم: بهینه سازیهای مهم الگوریتم
اگر G دورهای منفی نداشته باشد؛ پس کوتاهترین مسیر ساده از S به t وجود دارد.(یعنی گره ها تکرار نمی شوند.) و از اینرو در نهایت n-1 یال دارد.
اثبات: تا زمانی که هر دور هیچ هزینه منفی نداشته باشد؛ کوتاهترین مسیر P از s به t با بیشترین تعداد از یالها هیچ راس v را مرور نمی کند. اگر P ؛ راس v را تکرار کند؛ ما می توانیم بخش مابین عبورهای متوالی از v را حذف کنیم. که این عمل هزینه کمینه و یال بیشینه را نتیجه می دهد.
اجازه دهید OPT(i,v) را برای تفکیک کمترین هزینه یک مسیر v-t با استفاده از بیشترین یال i مورد استفاده قرار دهیم. مطابق مساله (6.22) اصی ترین مشکل؛ محاسبه OPT(n-1.s) است.(ما می توانیم به جای ساخت الگوریتم؛ زیر مسائل مرتبط با کمینه هزینه مسیر s-v را با استفاده از بیشترین یالi جایگزین کنیم. این یک موازی طبیعی با الگوریتم دایجسترا شکل خواهد داد. اما در پروتوکل های مسیر یابی که بعدا شرح خواهیم داد؛ این یک روش طبیعی نخواهد بود.)
اکنون راه ساده ای را برای بیان OPT(i,v) با استفاده از زیرمسائل کوچکتر نیازداریم. ما دیداه طبیعی تری که نکات بسیاری حالات مختلف را در بر می گیرد را مرور خواهیم کرد؛ این مثال دیگری است از اصل "انتخابهای چند مسیره" که در الگوریتم مساله کوچکترین مربعات بخش شده خواهیم دید.ش
تحقیق در مورد تحلیل مساله کوتاهترین مسیر در گراف جهت دار
