ایده

سر کلاس امروز هندسه محاسباتی تو ارائه ی یکی از بچه ها دیدم اینو. (خیلی بقیه شون نامفهوم بودن!!)

برای مساله یک پارامتر گرفته بود و تابع هزینه رو بر حسب اون به دست آورده بود. بعد با dp روی این پارامتره اومده بود جواب رو به دست آورده بود.

یعنی ایده اش به نظرم به اندازه ی اون باینری سرچ روی مقادیر ارزشمند اومد!

بقیه هم ایده های جالب داشتند:

یکی اومده بود یه مساله ی بدون رنگ رو رنگ آمیزی کرده بود یه طوری که رنگ ها جدا کننده ی مرزهای تصمیم بودند، بعد تابع هدف رو روی اون نسخه ی رنگ آمیزی شده انجام داده بود.

یکی دیگه ایده اش لو رفته بود تقریبا (ساعت قبلش استاد مربوطه درس داد اینو!) این بود که با درخت های بازه ( و سگمنت و امثالهم!) بیایم پوسته محدب بسازیم مثلا. اینم یه جورایی dp است فقط به جای آرایه توی درخته! :))

اون یکی یه کاری روی گراف بود که اومده بود گراف رو به دو قسمت درخت و دور تقسیم کرده بود، برای هر کدوم جواب در آورده بود! البته فکر کنم به نتیجه نرسیده بود! :))

دیگه آخری هم بگم پس: اومده بود زیرمساله ها رو گرفته بود اما مستقل نبودن، بعد تاثیر اون یکی رو توی این اعمال می کرد. کوتاهترین مسیر توی grid بود که توش میومد دایجکسترا(؟!) میزد روی مرز این مربع های کوچکتر کوتاهترین مسیر بین نقاط رو پیدا می کرد. اشکالش هم همین بود که رو هم تاثیر داشتن دیگه، یعنی ممکن بود از توی یه مربع کناری به جواب بهینه ی این مربع فعلی برسی.

میرم مال خودمو درست کنم مثل اینها نشه!