Printable View
سلام
یه جدول m در n خونه داریم که تو هر خونه مقداری عدد وجود داره،به نظر شما دوستان چطوری میشه از خونه اولی که شما هستین تا خونه آخر جدول ، طوری حرکت کرد که در انتها مطمئن بود مسیری رو انتخاب کردین که بزرگترین اعداد رو انتخاب کردین
یعنی الگوریتم انتخاب بزرگترین اعداد در مسیر حرکت.
البته شرط حرکت فقط راست و پایین هستش و به سمت دیگه ایی نمیتونین برین ،ضمن اینکه مسیر تکراری مجاز نیست
اگه منظورمو متوجه نشدید عکس ضمیمه رو ببینید
ضمیمه 86873
https://barnamenevis.org/images/misc/pencil.png
بهترین نظر رو برای یه کار خوب دعوت میکنم،پس اگه میتونید جواب بدین و شانستونو امتحان کنید
روش‌های حریصانه و پویا دو راه حل ممکن ساده هستن که دومی به جواب بهینه قطعی می‌رسه، اما اولی ممکنه بهینه‌ترین نباشه.نقل قول:
نوشته شده توسط alireza.zahani
اما اگه ابعاد صفحه خیلی بزرگ باشه برنامه‌ریزی پویا هم اونطور که باید در زمان خوبی جواب نمی‌ده و باید سراغ روش‌های ابتکاری و فرا ابتکاری مربوط به مباحث هوش مصنوعی رفت.
جواب دوستمون درسته
البته می شه از ژنتیک هم استفاده کرد اما به نظر من همون حریصانه جواب می ده
نقل قول:
نوشته شده توسط مسعود اقدسی فام
مسعود بیشتر توضیح بده
همون روش های اولتو
روش حریصانه یعنی اینکه در هر مرحله خانه‌ای از خانه‌های مجاور رو انتخاب کنیم که بیشترین مقدار رو داره. شکل شما دقیقا به روش حریصانه پیش رفته. فقط اینکه سطر سوم از آخر به جای حرکت از 5 به 1 از 5 به 4 می‌ره که نتیجه رو هم بزرگتر از مسیری که شما انتخاب کردید به دست می‌یاره. اما مشکل این روش در ساختاری مثل اعداد زیر مشخص میشه:نقل قول:
نوشته شده توسط alireza.zahani
1 1 1 100
2 1 1 1
3 1 1 1
4 1 1 1
روش حریصانه با شروع از عدد 1 عدد 2 در سطر پایین رو انتخاب می‌کنه و به همین ترتیب پایین می‌ره و آخر سر مجموع کل 13 به دست می‌یاد. در حالیکه اگه به سمت عدد 100 حرکت می‌کرد به 116 می‌رسید.
برنامه‌ریزی پویا این مشکل رو حل می‌کنه. توضیح این روش مفصله. از لینک‌های زیر میتونید کمک بگیرید:
در واقع این مساله مثل پیدا کردن کوتاهترین مسیر از یه شهر به شهر دیگه با استفاده از شهرهای میانیه. هر خانه یه گره از گراف جهت داری رو تشکیل می‌ده که جاده بین شهرهای مجاور و طول اونها رو مشخص کرده. با استفاده از برنامه‌ریزی پویا روش فلوید-وارشال برای حل مساله قبلا ابداع شده:
http://fa.wikipedia.org
البته الگوریتم دایجسترا هم هست که باید بررسی بشه.
روش‌هایی مثل ژنتیک و PSO و مورچگان و غیره روش‌های ابتکاری و فرا ابتکاری هستن که بحث مفصلی نیاز دارن. میتونید از این پیوند استفاده کنید:
البته که بهتره از روش پویا حل بشه
فکر میکنم حریصانه مرتبه اش ، نمایی هم می شه!!
بستگی داره از کدوم روش حریصانه استفاده کنید. روش اول نمایی نمی‌شه. چون در هر مرحله بالاخره یکی از دو گزینه انتخاب میشه، که m + n مرحله خواهد داشت. یعنی در کل (O( m + n میشه که خطیه. روش فلوید- وارشال هم قبلا ثابت شده از مرتبه درجه سه هستش. روش دایجسترا هم اگه اشتباه نکنم از مرتبه درجه دو میشه.نقل قول:
نوشته شده توسط alireza.zahani
فرق دایجسترا و فلوید-وارشال در اینه که دایجسترا فقط مسیر از یه مبدا مشخص به هر مقصدی رو مشخص می‌کنه. اما فلوید- وارشال از هر مبدا به هر مقصد رو در انتها تولید می‌کنه که برای مساله‌ی شما چندان مورد نیاز نیست.
البته همه‌ی این روش‌ها به صورت پیشفرض برای کوتاهترین مسیر (کمینه کردن) تعریف شده که برعکس مساله‌ی شماست. ولی میشه با کمی تغییر به همون مساله تبدیل کرد.
باز اگه دوستان نظر دیگه‌ای دارن خوشحال می‌شم بحث کنیم.
مسعود اقدسی فام اگه می شه راجع به الگوریتم پویا راهکاری پیشنهاد بده
همین پیشنهادی که دادم راجع به استفاده از دایجسترا یا فلوید رو بررسی کنید. البته دایجسترا پویا نیست. هر راهکار دیگه‌ای پیشنهاد بدم در واقع چیزی شبیه فلوید (برای پویا) میشه که فقط اسمش فلوید نیست! چون کلیت مساله همون مساله کوتاهترین مسیر از شهر گوشه چپ بالا به راست پایینه. درسته که مساله‌ی شما بزرگترین مسیر رو می‌خواد؛ اما کافیه اعداد رو معکوس کنید تا به کوتاهترین تبدیل بشه. مثلا عدد 2 بشه یک دوم و عدد 10 بشه یک دهم. در این حالت عدد بزرگتر به عدد کوچکتر تبدیل میشه.نقل قول:
نوشته شده توسط alireza.zahani
تعداد حرکات در تمامی مسیرها مساویه،فقط مقادیر مهمه که زیادتر نداشته باشه
منظورتونو بیشتر توضیح بدین
اگه میشه با شبه کد بگین
شما الگوریتم فلوید-وارشال رو سوای مساله‌ی خودتون مطالعه کنید. تا من ادامه رو بگم.نقل قول:
نوشته شده توسط alireza.zahani
این پروژه رو نگاه کنید و نظرتونو بگید
کل مسیرهای ممکن رو یکی یکی بررسی و مجموعشون رو محاسبه می‌کنه. در نهایت بیشترین عدد رو به عنوان مسیر جواب مشخص می‌کنه.نقل قول:
نوشته شده توسط alireza.zahani
این یه راه حل کاملا معمولیه که همه‌ی فضای جواب رو بررسی می‌کنه که بهترین رو پیدا کنه. اگه ابعاد صفحه زیاد باشه کارا نیست.
این چیزیکه شما میگید که اصلا احتیاج به این همه الگوریتم و روش ابتکاری و اینا نداره.نقل قول:
نوشته شده توسط alireza.zahani
فقط کافیه داخل هر خونه ای که هستید اعداد سمت راست و پایین رو چک کنید هر کدوم بزرگتر بود برید به همون خونه.
نمیدونم یا من متوجه نشدم یا شما خیلی مسئله رو پیچیده کردید ؟؟؟؟
این روش رو اگه تمام پست‌ها رو مطالعه می‌کردید بررسی کردیم. یه روش حریصانه که لزوما به جواب بهینه نمی‌رسه.نقل قول:
نوشته شده توسط torisoft