كتب تجريبية خوارزميات

تعريف وتوطئة

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

المقايضات في استخدام التجريبية

عندما نقف أمام مسألة ونريد أن نعرف إن كان استخدام التجريبيات سيفيد أما لا يجب أن ننظر إلى ماذا سنخسر مقابل ماذا سنربح عند استخدام التجريبية وهذه المقايضات هي :

• الأمثلية: اي عندما يوجد عدة حلول لمسألة ما معطاة، هل تضمن لنا التجريبية الوصول إلى الحل الأمثل ؟ هل من المجدي الوصول إلى الحل الأمثل ؟
• الكمال (completeness) : اي عندما يوجد أكثر من حل للمسألة هل تستطيع التجربيات إيجاد كافة الحلول ؟ هل نحن بحاجة لإيجاد كافة الحلول؟العديد من التجريبيات تصمم للحصول على حل وحيد.
• الدقة: اي هل سيكون مقدار الخطأ الناتج عن استخدام التجريبية كبيراً جداً؟
• وقت التنفيذ : هل هذه أفضل تجريبية لحل هذا النوع من المشاكل؟ حيث أن بعض التجريبيات تتقارب أسرع من تجريبيات أخرى.

في بغض الحالات من الصعب جداً معرفة إن كان استخدام التجريبية جيد بما فيه الكفاية حيث أن القسم النظري أثبت أن التجريبية ليست دقيقة.

أمثلة

استخدام مسائل أبسط

أحد طرق الحصول على أداء حاسوبي أفضل في حل المشاكل هو حل المشكلة عن طريق حل مشكلة أسهل منها يكون حلها هو أيضاً حل للمشكلة الابتدائية. إن هذا النوع من التجريبيات غير قادرة على إيجاد كافة الحلول للمشكلة الأساسية لكن يمكنها أن تجد حلاً بسرعة وذلك لسهولة حل المسألة الأبسط التي تشبه المسألة الأساسية

مسألة البائع الجوال الشهيرة

مثال عن إيجاد حل تقريبي لحل مسألةالبائع الجوال تم طرحه من قبل جون بينتلي و هو عبارة عن ايجاد الترتيب الملائم للتجوال بين المدن كمالو أننا أردنا رسم الخارطة باستخدام طابعة pen plotter. مسألة البائع الجوال تعتبر من نوع المسائل ذات الصعوبة مسألة كثيرة حدود غير قطعية كاملة لذلك أيجاد حل أمثل لهذا النوع من المسائل حتى لو كانت على حجم صغير هو شيء صعب. يمكن استخدام الخوارزمية الطموحة لإيجاد حل لكنه لن يكون الحل الأمثل بل هو تقريب للحل الأمثل ضمن وقت منطقي . حيث أن التجريبية في الخوارزمية الطموحة تعتمد على اختيار الطريق الأفضل في الخطوة التالية في كلل مرحلة . التجريبية هذه تعطي حلاً جيداً بما فيه الكفاية لكن الدراسة النظرية تبرهن على وجود حل أفضل.

مسائل البحث

مثال آخر على استخدام التجريبية لجعل الوصول إلى الحل أسرع هو في مثال البحث. بدايةً, التجريبية تقوم بتجريب كل الاحتمالات الممكنة في كل خطوة لكنها قادرة على إيقاف عملية البحث في أي لحظة إذا كانت الاحتمالية التي وصلت إليها أسوأ من الحل الأفضل . في المثال المشابهة تستخدم التجريبية لإيجاد الحلول الأفضل أولاً. مثال ( تقليم من نوع ألفا بيتا )

نويل وسايمون : فرضية تجريبية البحث

خلال حفل استلامهما لجائزة تورينغ ناقش العالمان آلن نويل وهربرت سايمون فرضية تجريبية البحث : باستخدام نظام معالجة الرموز سيتم توليد وتعديل الرموز المعروفة حتى تكون البنى المنشأة مطابقة لبنية الحل.( يشار إلى أن نظام معالجة الرموز المذكور هو من إنشاء العالمين وهو تعد آلية عمله جزءاً من فلسفة الذكاء الصنعي). كل دورة تعاقبية من مراحل العمل تعتمد على الخطوة السابقة لها بالتالي تجريبية البحث تتعلم السب التي يجب اتباعها والسبل التي يجب الابتعاد عنها وذلك من خلال حساب بعد الدور الحالي عن الحل بعض الاحتماليات لن يتم حسابها أبداً إذ أنها بعيداً جداً عن الهدف المرجوّ. تستطيع التجريبية إتمام المهمة الخاصة بها من خلال أشجار البحث . لسنا بحاجة إلى توليد كل العقد في شجرة البحث حيث أن التجريبية تختار العقد التي نحتاجها في البحث عن حل فقط.

البحث عن الفيروسات

العديد من برامج البحث عن التطبيقات الخبيثة كالفيروسات تستخدم تجريبيات في البحث . هذا النوع من البحث يتعمد البحث عن أجزاء من برامج معينة تدعى (block of code) أو طابع مميز لنوع معين من أنواع البرمجيات الخبيثة . عند إيجاد تطابق بين الخواص التي نبحث عنها وجزء من مكونات ملف معين أو مهمة معينة يتم تنفيذها عندها يرسل البرنامج المضاد رسالة بوجود تطبيق غير آمن. أهم خاصية للتجريبيات المبنية على السلوك هو أنها تسطيع التعامل مع فيروسات مبنية بشكل عشوائي عالي وبطريقة تدعى (polymorphic ) حيث أن الفيروسات المبينة بهذا الأسلوب تغير بنيتها البرمجية بشكل مستمر علماً أن الخوارزمية تبقيى ذاتها.

أخطاء ومزالق

إن استخدام نجريبية معينة في مجالات متعددة فقط لأنه بدا أنها تعمل في مجال معين دون البرهان الرياضي على مدى فاعليتها على متطلبات المسألة يجعل الحلول الناتجة عن هذا الاستخدام الخاطئ قريبة من الضجيج