فهم حقيقة خوارزمية كارماركر

خوارزمية كارماركر هي خوارزمية قدمها ناريندرا كارماركر في عام 1984 لحل مسائل البرمجة الخطية . كانت أول خوارزمية ذات كفاءة معقولة لحل هذه المسائل في زمن متعدد الحدود . طريقة الإهليلجي هي أيضا متعددة الحدود لكنها أثبتت أنها غير فعالة عمليا.

بجعل







n





{\displaystyle n}



تدل على عدد المتغيرات و







L





{\displaystyle L}



على عدد وحدات بت في مدخلات الخوارزمية، خوارزمية كارماركر تحتاج إلى







O

(



n



3.5





L

)





{\displaystyle O(n^{3.5}L)}



عملية على خانات







O

(

L

)





{\displaystyle O(L)}



, في المقابل تحتاج إلى







O

(



n



6





L

)





{\displaystyle O(n^{6}L)}



عمليات بخوارزمية الاهليجي.

بالتالي زمن تشغيل خوارزمية كارماركر هو:









O

(



n



3.5







L



2





⋅

log

⁡

L

⋅

log

⁡

log

⁡

L

)





{\displaystyle O(n^{3.5}L^{2}\cdot \log L\cdot \log \log L)}





باستخدام الضرب القائم على FFT (انظر رمز O الكبير ).

تندرج خوارزمية كارماركر ضمن فئة أساليب النقاط الداخلية : لا يتبع التخمين الحالي للحل حدود المجموعة الممكنة كما هو الحال في طريقة simplex ، لكنه يتحرك بداخل المنطقة الممكنة، مما يحسن تقريب الحل الأمثل بكسر واضح مع كل التكرار، والوصول إلى الحل الأمثل مع البيانات المنطقية.