الگوریتم لیله

[alireza.zahani]

سلام
یه جدول m در n خونه داریم که تو هر خونه مقداری عدد وجود داره،به نظر شما دوستان چطوری میشه از خونه اولی که شما هستین تا خونه آخر جدول ، طوری حرکت کرد که در انتها مطمئن بود مسیری رو انتخاب کردین که بزرگترین اعداد رو انتخاب کردین
یعنی الگوریتم انتخاب بزرگترین اعداد در مسیر حرکت.
البته شرط حرکت فقط راست و پایین هستش و به سمت دیگه ایی نمیتونین برین ،ضمن اینکه مسیر تکراری مجاز نیست
اگه منظورمو متوجه نشدید عکس ضمیمه رو ببینید
86873
http://barnamenevis.org/images/misc/pencil.png

[alireza.zahani]

بهترین نظر رو برای یه کار خوب دعوت میکنم،پس اگه میتونید جواب بدین و شانستونو امتحان کنید

[مسعود اقدسی فام]

سلام
یه جدول m در n خونه داریم که تو هر خونه مقداری عدد وجود داره،به نظر شما دوستان چطوری میشه از خونه اولی که شما هستین تا خونه آخر جدول ، طوری حرکت کرد که در انتها مطمئن بود مسیری رو انتخاب کردین که بزرگترین اعداد رو انتخاب کردین
یعنی الگوریتم انتخاب بزرگترین اعداد در مسیر حرکت.
البته شرط حرکت فقط راست و پایین هستش و به سمت دیگه ایی نمیتونین برین ،ضمن اینکه مسیر تکراری مجاز نیست
اگه منظورمو متوجه نشدید عکس ضمیمه رو ببینید
86873
http://barnamenevis.org/images/misc/pencil.png

روش‌های حریصانه و پویا دو راه حل ممکن ساده هستن که دومی به جواب بهینه قطعی می‌رسه، اما اولی ممکنه بهینه‌ترین نباشه.
اما اگه ابعاد صفحه خیلی بزرگ باشه برنامه‌ریزی پویا هم اونطور که باید در زمان خوبی جواب نمی‌ده و باید سراغ روش‌های ابتکاری و فرا ابتکاری مربوط به مباحث هوش مصنوعی رفت.

[Saber_Fatholahi]

جواب دوستمون درسته
البته می شه از ژنتیک هم استفاده کرد اما به نظر من همون حریصانه جواب می ده

[alireza.zahani]

روش‌های حریصانه و پویا دو راه حل ممکن ساده هستن که دومی به جواب بهینه قطعی می‌رسه، اما اولی ممکنه بهینه‌ترین نباشه.
اما اگه ابعاد صفحه خیلی بزرگ باشه برنامه‌ریزی پویا هم اونطور که باید در زمان خوبی جواب نمی‌ده و باید سراغ روش‌های ابتکاری و فرا ابتکاری مربوط به مباحث هوش مصنوعی رفت.


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

[مسعود اقدسی فام]

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

روش حریصانه یعنی اینکه در هر مرحله خانه‌ای از خانه‌های مجاور رو انتخاب کنیم که بیشترین مقدار رو داره. شکل شما دقیقا به روش حریصانه پیش رفته. فقط اینکه سطر سوم از آخر به جای حرکت از 5 به 1 از 5 به 4 می‌ره که نتیجه رو هم بزرگتر از مسیری که شما انتخاب کردید به دست می‌یاره. اما مشکل این روش در ساختاری مثل اعداد زیر مشخص می‌شه:


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 (http://fa.wikipedia.org/wiki/%D8%A8%D8%B1%D9%86%D8%A7%D9%85%D9%87%E2%80%8C%D8%B 1%DB%8C%D8%B2%DB%8C_%D9%BE%D9%88%DB%8C%D8%A7)


http://www.algorithmha.ir (http://www.algorithmha.ir/post-%D8%A8%D8%B1%D9%86%D8%A7%D9%85%D9%87-%D9%86%D9%88%DB%8C%D8%B3%DB%8C-%D9%BE%D9%88%DB%8C%D8%A7.aspx)




در واقع این مساله مثل پیدا کردن کوتاهترین مسیر از یه شهر به شهر دیگه با استفاده از شهرهای میانیه. هر خانه یه گره از گراف جهت داری رو تشکیل می‌ده که جاده بین شهرهای مجاور و طول اونها رو مشخص کرده. با استفاده از برنامه‌ریزی پویا روش فلوید-وارشال برای حل مساله قبلا ابداع شده:


http://fa.wikipedia.org (http://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_% D9%81%D9%84%D9%88%DB%8C%D8%AF-%D9%88%D8%A7%D8%B1%D8%B4%D8%A7%D9%84)


البته الگوریتم دایجسترا هم هست که باید بررسی بشه.

روش‌هایی مثل ژنتیک و PSO و مورچگان و غیره روش‌های ابتکاری و فرا ابتکاری هستن که بحث مفصلی نیاز دارن. می‌تونید از این پیوند استفاده کنید:


http://www.matlabsite.com (http://www.matlabsite.com/)

[alireza.zahani]

البته که بهتره از روش پویا حل بشه
فکر میکنم حریصانه مرتبه اش ، نمایی هم می شه!!

[مسعود اقدسی فام]

البته که بهتره از روش پویا حل بشه
فکر میکنم حریصانه مرتبه اش ، نمایی هم می شه!!

بستگی داره از کدوم روش حریصانه استفاده کنید. روش اول نمایی نمی‌شه. چون در هر مرحله بالاخره یکی از دو گزینه انتخاب می‌شه، که m + n مرحله خواهد داشت. یعنی در کل (O( m + n می‌شه که خطیه. روش فلوید- وارشال هم قبلا ثابت شده از مرتبه درجه سه هستش. روش دایجسترا هم اگه اشتباه نکنم از مرتبه درجه دو می‌شه.
فرق دایجسترا و فلوید-وارشال در اینه که دایجسترا فقط مسیر از یه مبدا مشخص به هر مقصدی رو مشخص می‌کنه. اما فلوید- وارشال از هر مبدا به هر مقصد رو در انتها تولید می‌کنه که برای مساله‌ی شما چندان مورد نیاز نیست.
البته همه‌ی این روش‌ها به صورت پیشفرض برای کوتاهترین مسیر (کمینه کردن) تعریف شده که برعکس مساله‌ی شماست. ولی می‌شه با کمی تغییر به همون مساله تبدیل کرد.
باز اگه دوستان نظر دیگه‌ای دارن خوشحال می‌شم بحث کنیم.

[alireza.zahani]

مسعود اقدسی فام (http://barnamenevis.org/member.php?87209-مسعود-اقدسی-فام) اگه می شه راجع به الگوریتم پویا راهکاری پیشنهاد بده

[مسعود اقدسی فام]

مسعود اقدسی فام (http://barnamenevis.org/member.php?87209-مسعود-اقدسی-فام) اگه می شه راجع به الگوریتم پویا راهکاری پیشنهاد بده

همین پیشنهادی که دادم راجع به استفاده از دایجسترا یا فلوید رو بررسی کنید. البته دایجسترا پویا نیست. هر راهکار دیگه‌ای پیشنهاد بدم در واقع چیزی شبیه فلوید (برای پویا) می‌شه که فقط اسمش فلوید نیست! چون کلیت مساله همون مساله کوتاهترین مسیر از شهر گوشه چپ بالا به راست پایینه. درسته که مساله‌ی شما بزرگترین مسیر رو می‌خواد؛ اما کافیه اعداد رو معکوس کنید تا به کوتاهترین تبدیل بشه. مثلا عدد 2 بشه یک دوم و عدد 10 بشه یک دهم. در این حالت عدد بزرگتر به عدد کوچکتر تبدیل می‌شه.

[alireza.zahani]

تعداد حرکات در تمامی مسیرها مساویه،فقط مقادیر مهمه که زیادتر نداشته باشه
منظورتونو بیشتر توضیح بدین
اگه میشه با شبه کد بگین

[مسعود اقدسی فام]

تعداد حرکات در تمامی مسیرها مساویه،فقط مقادیر مهمه که زیادتر نداشته باشه
منظورتونو بیشتر توضیح بدین
اگه میشه با شبه کد بگین

شما الگوریتم فلوید-وارشال رو سوای مساله‌ی خودتون مطالعه کنید. تا من ادامه رو بگم.

[alireza.zahani]

این پروژه رو نگاه کنید و نظرتونو بگید

[مسعود اقدسی فام]

87448
این پروژه رو نگاه کنید و نظرتونو بگید

کل مسیرهای ممکن رو یکی یکی بررسی و مجموعشون رو محاسبه می‌کنه. در نهایت بیشترین عدد رو به عنوان مسیر جواب مشخص می‌کنه.

این یه راه حل کاملا معمولیه که همه‌ی فضای جواب رو بررسی می‌کنه که بهترین رو پیدا کنه. اگه ابعاد صفحه زیاد باشه کارا نیست.

[torisoft]

بهترین نظر رو برای یه کار خوب دعوت میکنم،پس اگه میتونید جواب بدین و شانستونو امتحان کنید

این چیزیکه شما میگید که اصلا احتیاج به این همه الگوریتم و روش ابتکاری و اینا نداره.
فقط کافیه داخل هر خونه ای که هستید اعداد سمت راست و پایین رو چک کنید هر کدوم بزرگتر بود برید به همون خونه.
نمیدونم یا من متوجه نشدم یا شما خیلی مسئله رو پیچیده کردید ؟؟؟؟

[مسعود اقدسی فام]

این چیزیکه شما میگید که اصلا احتیاج به این همه الگوریتم و روش ابتکاری و اینا نداره.
فقط کافیه داخل هر خونه ای که هستید اعداد سمت راست و پایین رو چک کنید هر کدوم بزرگتر بود برید به همون خونه.
نمیدونم یا من متوجه نشدم یا شما خیلی مسئله رو پیچیده کردید ؟؟؟؟
این روش رو اگه تمام پست‌ها رو مطالعه می‌کردید بررسی کردیم. یه روش حریصانه که لزوما به جواب بهینه نمی‌رسه.