سلام. وقت بخیر.
در مورد سوال دوم با شما موافقم. هدفش اگه بیشترین تعداد بازه بود گزینه ۲ میشد.
در مورد سوال اول میتونید مثال نقض ارائه بدید؟ به نظرم مشکلی نداره.

(۲۳ آذر ۱۳۹۵ ۰۱:۱۱ ب.ظ)Jooybari نوشته شده توسط:  سلام. وقت بخیر.
در مورد سوال دوم با شما موافقم. هدفش اگه بیشترین تعداد بازه بود گزینه ۲ میشد.
در مورد سوال اول میتونید مثال نقض ارائه بدید؟ به نظرم مشکلی نداره.

مثال نقض گزینه ۱
P1=4 d1=5
P2=3 d2=4


مثال نقض گزینه ۲
P1=4 d1=5
P2=3 d2=14

مثال نقض گزینه ۳
P1=8 d1=8
P2=1 d2=2

آیا هر ۲ سوال راه حریصانه ندارند؟ اگر ندارند چه راه حلی دارند ؟ آیا np hard هستند ؟

(۲۳ آذر ۱۳۹۵ ۰۴:۴۲ ب.ظ)maneshti نوشته شده توسط:  مثال نقض گزینه ۱
P1=4 d1=5
P2=3 d2=4


مثال نقض گزینه ۲
P1=4 d1=5
P2=3 d2=14

مثال نقض گزینه ۳
P1=8 d1=8
P2=1 d2=2

آیا هر ۲ سوال راه حریصانه ندارند؟ اگر ندارند چه راه حلی دارند ؟ آیا np hard هستند ؟

کاربرد الگوریتمهای حریصانه تو مسائل زمان بندی با مهلت یه مقدار متفاوته و از حالت های قبلی پیچیده تره. اینجا فقط انتخاب کارها مهمه. ترتیبشون هم به شکل حریصانه انجام میگیره ولی به همین ترتیب نیست. برای مثال گزینه ۱ شما اول کار ۲ و بعد کار ۱ انتخاب میشه. جریمه هم برابر ۲ خواهد بود. برای گزینه ۲ هردو کار انتخاب میشن. درسته که اول کار ۲ و بعد کار ۱ انتخاب میشه. ولی ترتیب اجرای اونها تو این حالت برعکسه. گزینه ۳ مثالتون درسته.
میشه اول یه بررسی برای کارهایی که بدون جریمه انجام میشن داشته باشیم. بعد یه بررسی برای کارهای باقی مونده. برای گزینه ۱ مثال نقض دارم:
p1 = 5 , d1 = 4
p2 = 10 , d2 = 3
چون هردو کار جریمه میخورن، اگه برحسب گزینه ۱ عمل کنیم، کار اول (کار شماره ۲) ۷ و کار دوم (کار شماره ۱) ۱۱ واحد جریمه میخوره. اگه کارها رو برعکس انتخاب کنیم، کار اول (کار شماره ۱) ۱ و کار دوم (کار شماره ۲) ۱۲ واحد جریمه میخوره. مجموع جریمه ها برای حالت دوم بهتر بوده و گزینه ۱ غلطه.
گزینه ۲ هم مثل اینکه مشکل داره. ممکنه یه حالتی پیش بیاد که یه کار جریمه بخوره و یکی نخوره. مثل مورد زیر:
p1 = 6 , d1 = 5
p1 = 4 , d1 = 9
روش بهینه اینه که اول کار ۱ و دوم کار ۲ انتخاب بشه که مجموع جریمه بشه ۲، ولی اگه اول کار شماره ۲ رو انتخاب کنیم، کار شماره ۱ به اندازه ۵ واحد جریمه میخوره. به نظرم روش مناسب این مساله برنامه نویسی پویا باشه.

(۲۳ آذر ۱۳۹۵ ۱۰:۲۰ ب.ظ)Jooybari نوشته شده توسط:  

(23 آذر ۱۳۹۵ ۰۴:۴۲ ب.ظ)maneshti نوشته شده توسط:  مثال نقض گزینه ۱
P1=4 d1=5
P2=3 d2=4


مثال نقض گزینه ۲
P1=4 d1=5
P2=3 d2=14

مثال نقض گزینه ۳
P1=8 d1=8
P2=1 d2=2

آیا هر ۲ سوال راه حریصانه ندارند؟ اگر ندارند چه راه حلی دارند ؟ آیا np hard هستند ؟

کاربرد الگوریتمهای حریصانه تو مسائل زمان بندی با مهلت یه مقدار متفاوته و از حالت های قبلی پیچیده تره. اینجا فقط انتخاب کارها مهمه. ترتیبشون هم به شکل حریصانه انجام میگیره ولی به همین ترتیب نیست. برای مثال گزینه ۱ شما اول کار ۲ و بعد کار ۱ انتخاب میشه. جریمه هم برابر ۲ خواهد بود. برای گزینه ۲ هردو کار انتخاب میشن. درسته که اول کار ۲ و بعد کار ۱ انتخاب میشه. ولی ترتیب اجرای اونها تو این حالت برعکسه. گزینه ۳ مثالتون درسته.
میشه اول یه بررسی برای کارهایی که بدون جریمه انجام میشن داشته باشیم. بعد یه بررسی برای کارهای باقی مونده. برای گزینه ۱ مثال نقض دارم:
p1 = 5 , d1 = 4
p2 = 10 , d2 = 3
چون هردو کار جریمه میخورن، اگه برحسب گزینه ۱ عمل کنیم، کار اول (کار شماره ۲) ۷ و کار دوم (کار شماره ۱) ۱۱ واحد جریمه میخوره. اگه کارها رو برعکس انتخاب کنیم، کار اول (کار شماره ۱) ۱ و کار دوم (کار شماره ۲) ۱۲ واحد جریمه میخوره. مجموع جریمه ها برای حالت دوم بهتر بوده و گزینه ۱ غلطه.
گزینه ۲ هم مثل اینکه مشکل داره. ممکنه یه حالتی پیش بیاد که یه کار جریمه بخوره و یکی نخوره. مثل مورد زیر:
p1 = 6 , d1 = 5
p1 = 4 , d1 = 9
روش بهینه اینه که اول کار ۱ و دوم کار ۲ انتخاب بشه که مجموع جریمه بشه ۲، ولی اگه اول کار شماره ۲ رو انتخاب کنیم، کار شماره ۱ به اندازه ۵ واحد جریمه میخوره. به نظرم روش مناسب این مساله برنامه نویسی پویا باشه.

بنظرم با توجه به صورت سوال که میگه کدوم ترتیب اجرای پردازه ها یعنی معیار حریصانه اینجا دقیقا "پردازه ای که قراره اجرا بشه" هست و ما پردازه ها رو براساس معیار حریصانه انتخاب می کنیم که این انتخاب در درونش ترتیب اجرای پردازه ها است . این چیزی است که من از سوال متوجه شدم. باز هم نمیدونم که درست هست یا نه. به عبارتی من این جمله تون:

اینجا فقط انتخاب کارها مهمه. ترتیبشون هم به شکل حریصانه انجام میگیره ولی به همین ترتیب نیست.

رو از سوال استنباط نمیکنم. اما در کل شما هم برای ۳ گزینه مثال نقض ارائه دادید و جواب همون گزینه ۴ هست . حالا اگر جواب پویا داره میشه بفرمایین.ممنون.

(۲۴ آذر ۱۳۹۵ ۱۲:۱۸ ق.ظ)maneshti نوشته شده توسط:  بنظرم با توجه به صورت سوال که میگه کدوم ترتیب اجرای پردازه ها یعنی معیار حریصانه اینجا دقیقا "پردازه ای که قراره اجرا بشه" هست و ما پردازه ها رو براساس معیار حریصانه انتخاب می کنیم که این انتخاب در درونش ترتیب اجرای پردازه ها است . این چیزی است که من از سوال متوجه شدم. باز هم نمیدونم که درست هست یا نه. به عبارتی من این جمله تون:

اینجا فقط انتخاب کارها مهمه. ترتیبشون هم به شکل حریصانه انجام میگیره ولی به همین ترتیب نیست.

رو از سوال استنباط نمیکنم. اما در کل شما هم برای ۳ گزینه مثال نقض ارائه دادید و جواب همون گزینه ۴ هست . حالا اگر جواب پویا داره میشه بفرمایین.ممنون.

منظورم از اون جمله که ترتیب کارها مشخص نیست، مشابه بررسی سوالی میشه که قراره «تعدادی کار با ارزشهای متفاوت و دارای محدودیت زمانی و دارای زمان اجرای برابر با ۱ رو داریم و قراره با انجام دادن چندتا از اونها به بیشترین ارزش برسیم.» کارها با توجه به ارزششون مرتب میشن، ولی زمان اجراشون به اون ترتیب نیست.

راستش چیزی که در مورد برنامه نویسی پویا فکر میکردم مشابه با کوله پشتی ۰ و ۱ بود. تعداد سطرها رو برابر با تعداد کارها و تعداد ستونها رو برابر با مجموع مقادیر زمان کارها درنظر گرفته بودم. الآن که فکر میکنم ممکنه جواب نده. مساله در حالت کلی !n حالت داره. چون یه پردازنده داریم و بهترین جواب از بین جایگشت های این n کار رو باید پیدا کنیم.