نوشته شده توسط
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
البته الگوریتم دایجسترا هم هست که باید بررسی بشه.
روشهایی مثل ژنتیک و PSO و مورچگان و غیره روشهای ابتکاری و فرا ابتکاری هستن که بحث مفصلی نیاز دارن. میتونید از این پیوند استفاده کنید: