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

در قسمت قبل دیدیم که یک سری قید خطی (خط) داریم و می خواهیم در یک جهت اکسترمم (اینجا فرض کنید فقط مینیمم) را به دست بیاوریم.

0- الگوریتم بدیهی

برای شرط هایی که بالای یک خط را نشان می دهند upper envelop را حساب کنیم برای آن شرطهایی که زیر خط بودن رو نشان می دهند lower envelop بعد بین این دو اشتراک بگیریم.

زمان: O(nlogn)

1- الگوریتم هرس و جستجو (prune & search) در دو بعد

(*خودم حدس می زنم برای اینکه جواب O(n) بوده و زمان الگوریتم O(nlogn) سعی کردند که طوری بسازند که فقط حالت های مطلوب ساخته بشه)

فرض کنید می خواهیم x را مینیمم کنیم. (با تغییر متغیر می شود به این حالت رسید.)

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

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

حل: به جای اینکه همه ی خطها (شرطها) را با هم در نظر بگیریم، یک خط از آنهایی که جواب بالای آن است با یک خط از آنهایی که جواب پایین آن است را در نظر می گیریم و تقاطع آنها را حساب می کنیم. میانه ی این تقاطع ها را x می گیریم. تستی که گفته شد انجام می دهیم که ببینیم سمت راست را باید حذف کنیم یا سمت چپ. اگر جواب سمت چپ بود باید از سمت راست حذف کنیم. خط هایی که باید حذف کنیم آنهایی هستند که: جواب زیر آنهاست ولی خودشان زیر خط دیگر هستند، یا، جواب بالای آنهاست ولی خودشان بالای خط دیگر هستند. (قید اضافی هستند.)

همین کار را تکرار می کنیم تا جواب به دست بیاید.

زمان: T(n) = T(3n/4)+O(n)=O(n)

چون هر بار از نیمه ی سمت راست (یا چپ) نصف خطوط حذف می شوند.

تعمیم: برای ابعاد بالاتر هم همین کار را می توان انجام داد و زمان آن در دو به توان دو به توان d ضرب می شود. بهبود یافته ی آن در دو به توان d2 کار می کند. بهترین الگوریتم در n در دو به توان dlogd کار می کند. (d = تعداد ابعاد)