لا غداء مجاني (في البحث والتحسين)
من ويكيبيديا، الموسوعة encyclopedia
في التعقيد الحسابي والتحسين ، تنص نظرية لا غداء مجاني على أن التكلفة الحسابية لإيجاد حل والتي يتم حسابها عبر إيجاد المتوسط الحسابي لجميع المشكلات في الفئة، هي نفسها بالنسبة لأي طريقة حل. لذا لا يوجد حل مختصر. في الحوسبة، تحت ظروف معينة تكون المخرجات الناتجة من الإجراءات لحل نوع معين من المشاكل متطابقة إحصائياً. هناك طريقة لوصف ظرف كهذا، قدمه ديفيد ولبرت وويليام ج. ماكردي فيما يتعلق بمشاكل البحث [1] والتحسين ، [2] تتمثل بالقول بأنه لا يوجد غداء مجاني . استخلص ولبرت نظرية لا غداء مجاني للتعلم الآلي ( الاستدلال الإحصائي ).[3] لكن قبله، أثبت كولين شافير (Cullen Schaffer) نسخة مقيدة لنظريات ولبرت واستخدمها في نقد الوضع الحالي لأبحاث التعلم الآلي حول مشكلة الاستقراء.[4]
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b0/No_free_lunch_theorems_figure.png/320px-No_free_lunch_theorems_figure.png)
في استعارة «لا غداء مجاني» ، تمثل اجراءات حل المشكلات بأنها مطاعم، لكل منها قائمة طعام، يكون الطعام هنا هو المشكلة، والسعر هو الكلفة الحاسوبية لحلها. قوائم المطاعم متطابقة إلا في جانب واحد - حيث تختلط الاسعار من مطعم إلى آخر. بالنسبة لمن يأكلون اللحوم، والذين يُمكن أن يطلبوا أي طبق من القائمة، فإن متوسط تكلفة الغداء لا تعتمد على اختيار المطعم. ولكن النباتيون الذين يذهبون لتناول الغداء بانتظام مع من يأكلون اللحوم (والذين ستكون خياراتهم أكثر اقتصادية) قد يدفع متوسط تكلفة عالية لتناول طعام الغداء. لتقليل متوسط التكلفة بشكل ممنهج، يجب استخدام المعرفة المسبقة عن أ) ما سيطلبه الشخص و ب) كلفة الطلب في المطاعم المختلفة. وهذا يعني أن تحسين الأداء في حل المشكلات يتوقف على استخدام المعلومات السابقة لمطابقة الإجراءات مع المشاكل.[2][4]
رسمياً، لا يوجد غداء مجاني عندما يكون توزيع الاحتمالية على المشاكل المماثلة بكيفية يكون لدى اجراءات حل المشاكل جميعها حلول متطابقة، حيث ستكون جميع الاجراءات متساوية. في حالة البحث ، تعد المشكلة دالة موضوعية ، والنتيجة هي سلسلة من القيم التي يتم الحصول عليها عبر تقييم الحلول المرشحة في مجال الدالة.