خوارزمية كارماركر
Sign in to savelinear programing method
Wikidata facts
- Instance of
- algorithm
- Named after
- Narendra Karmarkar
Show 1 more fact
- maintained by WikiProject
- WikiProject Mathematics
Sources (1)
via Wikidata · CC0
Article · العربية
خوارزمية كارماركر هي خوارزمية قدمها ناريندرا كارماركر في عام 1984 لحل مسائل البرمجة الخطية . كانت أول خوارزمية ذات كفاءة معقولة لحل هذه المسائل في زمن متعدد الحدود . طريقة الإهليلجي هي أيضا متعددة الحدود لكنها أثبتت أنها غير فعالة عمليا. بجعل تدل على عدد المتغيرات و على عدد وحدات بت في مدخلات الخوارزمية، خوارزمية كارماركر تحتاج إلى عملية على خانات , في المقابل تحتاج إلى عمليات بخوارزمية الاهليجي. بالتالي زمن تشغيل خوارزمية كارماركر هو: باستخدام الضرب القائم على FFT (انظر رمز O الكبير ). تندرج خوارزمية كارماركر ضمن فئة أساليب النقاط الداخلية : لا يتبع التخمين الحالي للحل حدود المجموعة الممكنة كما هو الحال في طريقة simplex ، لكنه يتحرك بداخل المنطقة الممكنة، مما يحسن تقريب الحل الأمثل بكسر واضح مع كل التكرار، والوصول إلى الحل الأمثل مع البيانات المنطقية.
Abstract from DBpedia / Wikipedia · CC BY-SA