(۱۶ خرداد ۱۳۹۵ ۰۸:۵۶ ب.ظ)behnam5670 نوشته شده توسط:  

(16 خرداد ۱۳۹۵ ۰۸:۲۱ ب.ظ)kamal3401 نوشته شده توسط:  سلام من یک سوالی دیدم و نمیدونم به کدووم بحث طراحی الگوریتم مربوط میشه!! احساس میکنم این مسئله جزو مسئله های مهم و کاربردی طراحی الگوریتم

فرض میکنیم یک ماتریسی داریم در ابعاد N*M که تو هر کدوم از خانه های این ماتریس به تعداد $C_{i.j}$ سکه وجود داره!!
حالا عامل هوشمندی رو وارد ماتریس میکنیم که از محل یک و یک شروع به حرکت میکنه تا به محل N*M برسه
این عامل هوشمند فقط میتونه در دو جهت حرکت کنه(یک خانه به سمت راست یا یک خانه به سمت پایین)
الگوریتمی پیدا کنید که این عامل هوشمند در مسیری حرکت کند که حاوی بیشترین تعداد سکه باشد

این مسأله با dynamic programming حل میشه.
به صورت بازگشتی باید تابع cost رو اجرا کنید:
$cost(i,j)=C_{i, j}+\max\{cost(i+1, j),\: cost(i, j+1)\}$

فکر نکنم این الگوریتم درست باشه
ممکنه در جهت راست که حرکت میکنه تعداد سکه کمتری نسبت به جهت پایین باشه ولی تو ادامه مسیر تعداد سکه های اون قسمت بیشتر باشه

(۱۶ خرداد ۱۳۹۵ ۰۹:۱۱ ب.ظ)kamal3401 نوشته شده توسط:  

(16 خرداد ۱۳۹۵ ۰۸:۵۶ ب.ظ)behnam5670 نوشته شده توسط:  

(16 خرداد ۱۳۹۵ ۰۸:۲۱ ب.ظ)kamal3401 نوشته شده توسط:  سلام من یک سوالی دیدم و نمیدونم به کدووم بحث طراحی الگوریتم مربوط میشه!! احساس میکنم این مسئله جزو مسئله های مهم و کاربردی طراحی الگوریتم

فرض میکنیم یک ماتریسی داریم در ابعاد N*M که تو هر کدوم از خانه های این ماتریس به تعداد $C_{i.j}$ سکه وجود داره!!
حالا عامل هوشمندی رو وارد ماتریس میکنیم که از محل یک و یک شروع به حرکت میکنه تا به محل N*M برسه
این عامل هوشمند فقط میتونه در دو جهت حرکت کنه(یک خانه به سمت راست یا یک خانه به سمت پایین)
الگوریتمی پیدا کنید که این عامل هوشمند در مسیری حرکت کند که حاوی بیشترین تعداد سکه باشد

این مسأله با dynamic programming حل میشه.
به صورت بازگشتی باید تابع cost رو اجرا کنید:
$cost(i,j)=C_{i, j}+\max\{cost(i+1, j),\: cost(i, j+1)\}$

فکر نکنم این الگوریتم درست باشه
ممکنه در جهت راست که حرکت میکنه تعداد سکه کمتری نسبت به جهت پایین باشه ولی تو ادامه مسیر تعداد سکه های اون قسمت بیشتر باشه

یا جواب رو با دقت نخوندید یا dynamic programming رو بلد نیستید.
در فرمول ننوشتم که $cost(i,\: j)=C_{i,\: j}+\max\{C_{i+1,\: j},\: C_{i,\: j+1}\}$
نوشتم $cost(i,j)=C_{i, j}+\max\{cost(i+1, j),\: cost(i, j+1)\}$. وقتی به صورت بازگشتی اجرا میشه، خود اون تابع‌های cost این مشکلی که شما گفتید رو حل میکنند، چون تا آخرش اون مسیر رو به صورت انشعابی ادامه میدهند!

روی یک ماتریس ۳ در ۳ امتحان کنید. تابع $cost(0,0)$ به تابع‌های $cost(0,1)$ و $cost(1,0)$ منشعب میشه که تابع $cost(0,1)$ خودش به $cost(1,1)$ و $cost(0,2)$ تبدیل میشه (همچنین تابع منشعب دوم، یعنی $cost(1,0)$ هم خودش دو تا میشه و هر کدوم دنبال ماکزیمم میگردند...)

(۱۶ خرداد ۱۳۹۵ ۰۹:۲۰ ب.ظ)behnam5670 نوشته شده توسط:  

(16 خرداد ۱۳۹۵ ۰۹:۱۱ ب.ظ)kamal3401 نوشته شده توسط:  

(16 خرداد ۱۳۹۵ ۰۸:۵۶ ب.ظ)behnam5670 نوشته شده توسط:  

(16 خرداد ۱۳۹۵ ۰۸:۲۱ ب.ظ)kamal3401 نوشته شده توسط:  سلام من یک سوالی دیدم و نمیدونم به کدووم بحث طراحی الگوریتم مربوط میشه!! احساس میکنم این مسئله جزو مسئله های مهم و کاربردی طراحی الگوریتم

فرض میکنیم یک ماتریسی داریم در ابعاد N*M که تو هر کدوم از خانه های این ماتریس به تعداد $C_{i.j}$ سکه وجود داره!!
حالا عامل هوشمندی رو وارد ماتریس میکنیم که از محل یک و یک شروع به حرکت میکنه تا به محل N*M برسه
این عامل هوشمند فقط میتونه در دو جهت حرکت کنه(یک خانه به سمت راست یا یک خانه به سمت پایین)
الگوریتمی پیدا کنید که این عامل هوشمند در مسیری حرکت کند که حاوی بیشترین تعداد سکه باشد

این مسأله با dynamic programming حل میشه.
به صورت بازگشتی باید تابع cost رو اجرا کنید:
$cost(i,j)=C_{i, j}+\max\{cost(i+1, j),\: cost(i, j+1)\}$

فکر نکنم این الگوریتم درست باشه
ممکنه در جهت راست که حرکت میکنه تعداد سکه کمتری نسبت به جهت پایین باشه ولی تو ادامه مسیر تعداد سکه های اون قسمت بیشتر باشه

یا جواب رو با دقت نخوندید یا dynamic programming رو بلد نیستید.
در فرمول ننوشتم که $cost(i,\: j)=C_{i,\: j}+\max\{C_{i+1,\: j},\: C_{i,\: j+1}\}$
نوشتم $cost(i,j)=C_{i, j}+\max\{cost(i+1, j),\: cost(i, j+1)\}$. وقتی به صورت بازگشتی اجرا میشه، خود اون تابع‌های cost این مشکلی که شما گفتید رو حل میکنند، چون تا آخرش اون مسیر رو به صورت انشعابی ادامه میدهند!

روی یک ماتریس ۳ در ۳ امتحان کنید. تابع $cost(0,0)$ به تابع‌های $cost(0,1)$ و $cost(1,0)$ منشعب میشه که تابع $cost(0,1)$ خودش به $cost(1,1)$ و $cost(0,2)$ تبدیل میشه (همچنین تابع منشعب دوم، یعنی $cost(1,0)$ هم خودش دو تا میشه و هر کدوم دنبال ماکزیمم میگردند...)

درسته من اشتباه تحلیل کردم
ممنون

(۱۶ خرداد ۱۳۹۵ ۰۹:۲۹ ب.ظ)kamal3401 نوشته شده توسط:  

(16 خرداد ۱۳۹۵ ۰۹:۲۰ ب.ظ)behnam5670 نوشته شده توسط:  

(16 خرداد ۱۳۹۵ ۰۹:۱۱ ب.ظ)kamal3401 نوشته شده توسط:  

(16 خرداد ۱۳۹۵ ۰۸:۵۶ ب.ظ)behnam5670 نوشته شده توسط:  

(16 خرداد ۱۳۹۵ ۰۸:۲۱ ب.ظ)kamal3401 نوشته شده توسط:  سلام من یک سوالی دیدم و نمیدونم به کدووم بحث طراحی الگوریتم مربوط میشه!! احساس میکنم این مسئله جزو مسئله های مهم و کاربردی طراحی الگوریتم

فرض میکنیم یک ماتریسی داریم در ابعاد N*M که تو هر کدوم از خانه های این ماتریس به تعداد $C_{i.j}$ سکه وجود داره!!
حالا عامل هوشمندی رو وارد ماتریس میکنیم که از محل یک و یک شروع به حرکت میکنه تا به محل N*M برسه
این عامل هوشمند فقط میتونه در دو جهت حرکت کنه(یک خانه به سمت راست یا یک خانه به سمت پایین)
الگوریتمی پیدا کنید که این عامل هوشمند در مسیری حرکت کند که حاوی بیشترین تعداد سکه باشد

این مسأله با dynamic programming حل میشه.
به صورت بازگشتی باید تابع cost رو اجرا کنید:
$cost(i,j)=C_{i, j}+\max\{cost(i+1, j),\: cost(i, j+1)\}$

فکر نکنم این الگوریتم درست باشه
ممکنه در جهت راست که حرکت میکنه تعداد سکه کمتری نسبت به جهت پایین باشه ولی تو ادامه مسیر تعداد سکه های اون قسمت بیشتر باشه

یا جواب رو با دقت نخوندید یا dynamic programming رو بلد نیستید.
در فرمول ننوشتم که $cost(i,\: j)=C_{i,\: j}+\max\{C_{i+1,\: j},\: C_{i,\: j+1}\}$
نوشتم $cost(i,j)=C_{i, j}+\max\{cost(i+1, j),\: cost(i, j+1)\}$. وقتی به صورت بازگشتی اجرا میشه، خود اون تابع‌های cost این مشکلی که شما گفتید رو حل میکنند، چون تا آخرش اون مسیر رو به صورت انشعابی ادامه میدهند!

روی یک ماتریس ۳ در ۳ امتحان کنید. تابع $cost(0,0)$ به تابع‌های $cost(0,1)$ و $cost(1,0)$ منشعب میشه که تابع $cost(0,1)$ خودش به $cost(1,1)$ و $cost(0,2)$ تبدیل میشه (همچنین تابع منشعب دوم، یعنی $cost(1,0)$ هم خودش دو تا میشه و هر کدوم دنبال ماکزیمم میگردند...)

درسته من اشتباه تحلیل کردم
ممنون

خواهش میکنم.
به عنوان تمرین اگر خواستی مسأله رو برای حالتی حل کن که امکان حرکت به بالا هم داشته باشی (منتهی هر خونه نباید بیشتر از یک بار ویزیت بشه، لذا نمیتونی فقط یه جمله اضافه کنی که مثلاً $cost(i-1,\: j)$ رو هم بیاری داخل ماکزیمم. روشش فرق میکنه)