تالار گفتمان مانشت

با سلام

میخواستم در این مثال روش حل مسئله Bellman-Ford رو برام توضیح بدید.

با تشکر

با سلام

از دوستان کسی هست تا در مورد نحوه بدست آوردن edge relaxation اطلاعاتی داشته باشه ؟

با تشکر

اگر ممکن هست در این مثال یا هر مثالی که مد نظر دارید روش الگوریتم Bellman-Ford رو توضیح بدید. این الگوریتم بر چه مبنایی کوتاه ترین مسیر را شناسایی می کند ؟ بر چه مبنایی حرکت می کند ؟

ممنون

توضیحات من طبق کتاب clrs هست چون من فقط الگویتم رو از رویه این کتاب خوندم .
در الگوریتم بلمن فورد، از یک راس مبدا شروع کرده و با تکنیک relaxing جلو رفته و در هر بار مسیره بهینه را انتخاب می کند. ابتدا از راس مبدا شروع کرده و سپس به ازای هر لبه ها آرام سازی رو انجام میده تا کوتاهترین مسیر بین هر u,v انتخاب شود.
در مثال که شما آوردید، مثلا از راس A شروع می کنیم، ابتدا یال 2و یال 5 انتخاب میشه که هر دو از گره مبدا شروع می شوند، سپس کوتاه ترین مسیر ممکنه از گره های انتخاب تا کنون با در نظر گرفتن گره واسط محاسبه میشه، پس یال 3 هم انتخاب میشه، در مرحله بعد الگوریتم سعی در انتخاب یال 5 داره اما بسته به انتخاب گره بعداز s در پیمایش dfs (چون اگر در هنگام dfs مقادیر اولین لحظه ملاقات یعنی d یا مسیر ABD یا ACD انتخاب میشه ) می تونه یال های 4و3(بعد A گره B انتخاب شود)، یا 2و3 (بعد A گره C انتخاب شود) و چون وزن جمع آنها یکی است پس بسته به ترتیب پیمایش dfs برای گره d یال ها انتخاب می شن که چون هر دو 7 هست فرقی نداره اما از لحاظ الگوریتمی گفتم تا بدونید که کدوم مسیر محاسبه برای پیدا کرده گره D استفاده میشه .
روش Relaxing به این صورت هست که پس تعیین مقادیر d و pi (پی یونانی) در پیمایش عمقی ، مشخص می کنه که آیا با داشتن وزن یال بین u,v آیا می توان میسر را بهبود بخشید یا نه ، یعنی آیا اگه u رو به مسیر اضافه کنیم مقداری که تا کنون برای v پیدا شده ببهبود پیدا می کنه (کمتر میشه یا نه) یا نه ؟ اگه شد پس u رو نیز در مسیر قرار بده.

(02 آبان 1391 12:24 ق.ظ)esi نوشته شده توسط: [ -> ]توضیحات من طبق کتاب clrs هست چون من فقط الگویتم رو از رویه این کتاب خوندم .
در الگوریتم بلمن فورد، از یک راس مبدا شروع کرده و با تکنیک relaxing جلو رفته و در هر بار مسیره بهینه را انتخاب می کند. ابتدا از راس مبدا شروع کرده و سپس به ازای هر لبه ها آرام سازی رو انجام میده تا کوتاهترین مسیر بین هر u,v انتخاب شود.
در مثال که شما آوردید، مثلا از راس A شروع می کنیم، ابتدا یال 2و یال 5 انتخاب میشه که هر دو از گره مبدا شروع می شوند، سپس کوتاه ترین مسیر ممکنه از گره های انتخاب تا کنون با در نظر گرفتن گره واسط محاسبه میشه، پس یال 3 هم انتخاب میشه، در مرحله بعد الگوریتم سعی در انتخاب یال 5 داره اما بسته به انتخاب گره بعداز s در پیمایش dfs (چون اگر در هنگام dfs مقادیر اولین لحظه ملاقات یعنی d یا مسیر ABD یا ACD انتخاب میشه ) می تونه یال های 4و3(بعد A گره B انتخاب شود)، یا 2و3 (بعد A گره C انتخاب شود) و چون وزن جمع آنها یکی است پس بسته به ترتیب پیمایش dfs برای گره d یال ها انتخاب می شن که چون هر دو 7 هست فرقی نداره اما از لحاظ الگوریتمی گفتم تا بدونید که کدوم مسیر محاسبه برای پیدا کرده گره D استفاده میشه .
روش Relaxing به این صورت هست که پس تعیین مقادیر d و pi (پی یونانی) در پیمایش عمقی ، مشخص می کنه که آیا با داشتن وزن یال بین u,v آیا می توان میسر را بهبود بخشید یا نه ، یعنی آیا اگه u رو به مسیر اضافه کنیم مقداری که تا کنون برای v پیدا شده ببهبود پیدا می کنه (کمتر میشه یا نه) یا نه ؟ اگه شد پس u رو نیز در مسیر قرار بده.

ممنون از راهنمایی که کردید.