آمار پرسش:
- پرسیده شده: 2019-06-06 08:23:55 -0600
- مشاهده شده: 180 بار
- بروز شده: 2019-06-19 06:01:42 -0600
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
پیدا کردن مسیر در ماتریس دو بعدی
https://cdn1.imggmi.com/uploads/2019/6/6/eed56c4b1ed552bc1f816e3c99f169b7-full.jpg 
قسمت اول که میشه با یه دایمنامیک ساده از پایین چپ به بالا راست رفت اما قسمت دوم رو می خواستم بدونم با کمتر از O(n^4 پیدا کرد؟ ممنون میشم کمک کنید.
2019-06-06 08:23:55 -0600
ممممممددد 156 ● 3 ● 5 ● 13
نظرات
1 پاسخ
توضیح الگوریتم:
با دیکسترا میتونی توی $O(n^2lg(n^2))$ جواب رو پیدا کنی.
به این صورت که بیای یه گراف جهت دار $n^2$ راسی متانظر با ماتریس بسازی بطوری که هر راسش متناظر با یکی از خونه های ماتریسه و بین هر دو راسی که خونه های متناظرشون توی ماتریس همساین دو تا یال بکشی(یکی از این به اون و یکی از اون به این D:). حالا وزن یالی که به راس $v$ وارد میشه رو برابر با عدد خونه ی متناظر با راس $v$ در نظر میگیری. حالا با یه دیکسترا ی ساده میتونی توی این گراف کوچکترین مسیر از $P_{1,1}$ به $P_{n,n}$ پیدا کنی.
توضیحات کد:
توی کد ماتریس رو توی آرایه ی 2بعدی M ذخیره میکنیم. بعدش داخل وکتور 2بعدی v گراف متانظر ذخیره میشه. تابع dijkstra هم الگوریتم دیکسترا رو اجرا میکنه. درآخر بدلیل اینکه برای رفتن از $P_{1,1}$ به $P_{n,n}$ باید از خود $P_{1,1}$ هم عبور کنیم مقدار درایه ی $(1,1)$ هم به جوابمون اضافه میشه.
2019-06-19 02:30:56 -0600
غزوو 1304 ● 7 ● 14 ● 24
نظرات