least discrepancy search

https://www.coursera.org/learn/discrete-optimization/lecture/Pa60m/knapsack-2-greedy-algorithms
مثالش مسئله‌ی کوله‌پشتی بود. روشش این بود که بار اول فرض می‌کرد الگوریتم حریصانه جواب بهینه را پیدا می‌کند و بار بعدی فرض می‌کرد یک انتخاب اشتباه می‌کند و مرحله‌ی بعدی ۲ بار و ... .
چون اگر تا آخر برود همه را چک می‌کند جواب بهینه را می‌دهد. فقط مزیتش این است که می‌تواند زودتر هرس کند.

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