برمجه عوديه
Recursive programming -

البرمجة العوديّة

راكان رزوق

الخوارزميّة العوديّة

مثال على برنامج عوديّ

حل المسائل بطريقة التجريب والاستفادة من الأخطاء باستخدام البرامج العوديّة

 

يقال عن شيء إنه ذو بنية عوديّة recursive إذا كان مؤلفاً من مجموعة مكونات بعضها مُعرّف تعريف الشيء الأصلي. يقال مثلاً إنّ الشجرة هي بنية عوديّة لأنها مؤلفة من مجموعة من الفروع كلٌّ منها يحوي فروعاً جديدة، ومن ثَم يكون له بنية الشجرة نفسها، أو يحمل مجموعة من الأوراق. يبين الشكل (1) بعض الأشياء الطبيعية التي يمكن تعريفها تعريفاً عوديّاً.

الشكل (1) بعض الأشياء الطبيعية التي يمكن تعريفها تعريفاً عوديّاً.

إنّ أكثر من اهتمّ بموضوع العوديّة هم الرياضيون الذين استخدموها أداةً فعّالة في التعاريف الرياضية ولا سيما في المجموعات غير المنتهية. ومن الأمثلة الشهيرة لاستخدام العَوديّة في التعاريف مايلي :

1- تعريف الأعداد الطبيعيّة : تُعرّف الأعداد الطبيعية كما يلي:

أ-العدد صفر هو عدد طبيعي

ب-كل عدد يلي عدداً طبيعياً هو عدد طبيعي

2- تعريف بنية الشجرة الثنائية: تُعرّف الشجرة الثنائية كما يلي:

أ-الشجرة O لا تحتوي على أي عقدة، وتدعى الشجرة الفارغة.

ب-إذا كانت A وB شجرتين ثنائيتين فإن هي شجرة ثنائية جذرها X، وشجرتها الجزئية اليسارية A، وشجرتها الجزئية اليمينية B.

3- تعريف العاملي لعدد صحيح غير سالب :

أ- -0!= 1

ب- إذا كان فإنّ

4- تعريف متتالية أعداد فيبوناتشي Fibonacci: تُعرّف هذه المتتالية كما يلي:

أ- ,

ب- إذا كان فإنّ

تكمن أهمية العوديّة في إمكانية تعريف مجموعة غير منتهية من الأشياء بواسطة مجموعة منتهية من التعليمات. وبالطريقة نفسها يمكن تعريف عمليات حسابية غير منتهية بواسطة خوارزميّة عوديّة، وتكون الخوارزميّات العوديّة أكثر ملاءمة عندما تكون المسألة المطلوب حلها، أو بنية المعطيات الواجب معالجتها معرّفة عوديّاً.

1- الخوارزميّة العوديّة:

يمكن التعبير بوجه عام عن خوارزميّة عوديّة P بواسطة تركيب C لمجموعة عمليات أساسية Si (لا تحوي P) مع P نفسها:

إنّ الأداة المناسبة والكافية للتعبير عن برنامج معيّن عوديّاً هي الإجرائية Procedure ، لأنها تسمح بإعطاء اسم معين لمجموعة تعليمات مما يسمح باستدعاء هذه التعليمات عوديّاً، يمكن التفريق بين نوعين من الإجرائيات العوديّة:

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

    2- مثال على برنامج عوديّ:

    لدى التمعن بالأشكال الزخرفية المبينة في الشكل (2) يتبين أنها تتألف من خمسة خطوط منكسرة تتبع منهجاً في الرسم يمكن برمجته بعد تحديده بدقة.

    الشكل (2) منحنيات هلبرت من H1 إلى H5

    لو أعيد النظر مرة أخرى في هذه الخطوط مع محاولة عزل الثلاثة الأولى منها يتبين أن لها شكلاً مبيناً بالشكل (3)، يُرمز إلى هذه الأشكال بـ H1، H2، H3 على الترتيب وتسمى منحنيات هلبرت Hilbert curves.

    يُظهر الشكل (3) كيف يمكن الحصول على المنحني بتركيب أربعة منحنيات Hi أصغر حجماً بعد تدويرها باتجاهات معينة، والوصل بينها بثلاث قطع مستقيمة رُسمت بخط عريض.

    الشكل (3) طريقة تركيب منحنيات هلبرت من H1 إلى H3

    وبفرض أن الأدوات الأساسية المتوفرة للرسم هي :

    • جملة إحداثيات XOY.
    • إجرائية Setplot تقوم بنقل قلم الرسم إلى الموقع .
    • إجرائية Plot تقوم برسم خط مستقيم من موقع قلم الرسم إلى الموقع .

      ولما كان كل منحنٍ (منكسر) Hi يتألف من أربعة منحنيات Hi-1 متصلة، فيمكن التعبير عن إجرائية رسم Hi كتركيب لأربع إجرائيات تقوم كل منها برسم Hi-1 بالاتجاه والقياس المناسبين. إذا رُمز إلى هذه الإجرائيات الأربع بالأحرف Aو Bو Cو D ، وإذا رُمز بأسهم إلى عمليات رسم الوصلات يمكن التعبير عن المخطط العوديّ لهذه الإجرائيات كما يلي :

      إذا كانت h طول القطعة المُستخدمة في رسم الخط المنكسر فإن كتابة الإجرائية A ستأخذ التركيب التالي لـ D و B مع A:

      لتحديد نقطة بداية الرسم يفترض أن منطقة الرسم مربع طول ضلعه h0، ويلاحظ عندئذٍ أن رسم الخط Hi سيبدأ من الموقع :

      أما طول القطعة المُستخدمة في رسم الخط Hi فهو :

       

      وبهذا يصبح برنامج رسم منحنيات هلبرت كما يلي :





      3- حل المسائل بطريقة التجريب والاستفادة من الأخطاء باستخدام البرامج العوديّة:

      يُستفاد من البرامج العوديّة في حل العديد من المسائل، خاصة تلك التي ربما لاتوجد طريقة مباشرة لحلها، إنما تستدعي التجريب والاستفادة من الأخطاء. تُسمى الخوارزميات التي تستخدم هذا المبدأ خوارزميات تراجعية backtracking algorithms، ويستفاد منها فيما يلي :

      1- إيجاد حل واحد لمسألة معينة.

      2- إيجاد جميع حلول مسألة.

      3- إيجاد أفضل حل.

      3-1- إيجاد حل واحد لمسألة معينة - مسألة جولة الحصان:

      ثمة رقعة شطرنج فيها n x n مربعاً، يوضع الحصان في موقع معين من الرقعة حيث:
      , والمطلوب إيجاد طريقة لتغطية الرقعة (إذا كان ذلك ممكناً)، أي أن تكون هناك متتالية من الحركات عددها بحيث يتمّ المرور بكل مربع مرة واحدة.

      لحل المسألة يجب الاهتمام فقط بالحركة التالية: يفرض في كل مرحلة القيام بعدد من الحركات، وثمة مجموعة من الإمكانات التي يجب تجريبها. في كل مرحلة ثمة عدد من الحركات الممكنة، تجرّب إحدى هذه الحركات وتناقَش: هل تؤدي إلى حل أو إلى طريق مسدود. يمكن التعبير عن ذلك بالخوارزميّة العوديّة المبسطة التالية:

       
       

      لتفصيل الخوارزميّة لا بد من تعريف بنية المعطيات المستخدمة ومعاملات الإجرائية. تُمثل الرقعة بمصفوفة h معرفة كما يلي:

       
       

      حيث:

      لم يتمّ المرور في المربع .

      تمّ المرور في المربع في الخطوة i.

      معاملات الخوارزميّة :

      - الموقع الذي يراد تطبيق الخوارزميّة عليه .

      - رقم الخطوة: i .

      - متحول خرج q يعطي نتيجة المناقشة : نجاح أو إخفاق.

      بناءً على ذلك يمكن تبسيط العبارة “board is full” كما يلي: .

      وباستعمال متحولين موضعيين u,v لتمثيل أحد المواقع الممكنة (طبعاً وفق طريقة حركة الحصان) فإنّ العبارة “acceptable” يمكن التعبير عنها كما يلي:

       

      أخيراً يُستخدم متحول موضعي آخر q1 لمراقبة الاستدعاء العوديّ للإجرائية، فتصبح الإجرائية كما يلي:

      المرحلة الأخيرة من تبسيط الخوارزميّة هي تحديد الحركات الممكنة التي يمكن إجراؤها من موقع معين ، وفق قواعد لعبة الشطرنج يستطيع الحصان في الحالة العامة الانتقال إلى ثمانية مواقع يبينها الشكل (4).

       
      الشكل (4) إمكانيات انتقال الحصان 
       

      يمكن الحصول على إحداثيات هذه المواقع بإضافة فروق للإحداثيات، تخزن هذه الفروق في جدولين a وb يُعرّفان كما يلي:

       
       

      ويمكن استخدام عداد k لترقيم إمكانيات الانتقال التالي. عند استدعاء الإجرائية يحدد المعاملان اللذان يمثلان الموقع البدائي للحصان وتسند القيمة واحد لــ.


       
       

      يبين الشكل (5) حلّين تم الحصول عليهما مع المعطيات:

      1 -

      2 -

      الشكل (5) حلان لمسألة جولة الحصان

      3-2- إيجاد جميع حلول مسألة - مسألة الوزراء الثمانية:

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

      وفق قواعد لعبة الشطرنج يمكن للوزير أن يهدد جميع المربعات الموجودة في العمود أو السطر أو القطر نفسه؛ لذا يجب وضع وزير واحد في كل عمود، وتؤدي عملية تحديد موقع الوزير رقم i إلى تحديد رقم السطر الذي سيوضع فيه ضمن العمود رقم i.

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

      إنّ المهم هو موقع كل وزير ضمن العمود الموافق، ومعرفة: هل يحوي سطر معين أو قطر معين وزيراً أم لا؛ لذا يكفي استخدام بنية المعطيات التالية:

      حيث :

      تحوي رقم السطر الذي يوضع فيه الوزير رقم i.

       

      ó  السطر j لا يحوي أيَّ وزير.

      ó القطر المباشر رقم j لا يحوي أيَّ وزير (يبين الشكل 6 طريقة ترقيم الأقطار).

      ó القطر المتعامد رقم j لا يحوي أيَّ وزير.

      الشكل (6) طريقة ترقيم أقطار رقعة الشطرنج

      بعد تحديد بنية المعطيات المُستخدمة يمكن المضيّ في تفصيل الخوارزميّة، فيلاحظ أن المواقع الممكنة للوزير رقم i هي كل مربعات العمود رقم i (عددها ثمانية). لاختبار هذه المواقع يستعمل عدّاد j يكون في البداية صفراً ويزداد في كل مرة واحداً حتى يصل إلى القيمة 8. تكافئ عملية وضع الوزير رقم i في السطرj تنفيذ التعليمات التالية:

      وتكافئ عملية رفع الوزير رقم i من السطر j تنفيذ التعليمات التالية :

      ويمكن التعبير عن القضية “ position is safe” كما يلي:

      تنتهي بذلك عمليات تفصيل الخوارزميّة. يعطي هذا البرنامج الحل

      الممثل بالشكل (7).

      الشكل (7) أحد حلول مسألة الوزراء الثمانية

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

      في حالة مسألة الوزراء الثمانية تصبح إجرائية البحث عن الحلول كالتالي :

      حيث يتم إظهار الحلول بالإجرائية:

      بهذا يمكن إيجاد جميع الحلول وعددها 92، من بين هذه الحلول اثنا عشر حلاً مستقلاً (لا ينجم أحدها عن الآخر بتدوير الرقعة أو بالتناظر) يبينها الشكل (8).

      الشكل (8) الحلول المستقلة لمسألة الوزراء الثمانية

      3-3 إيجاد أفضل حل - مسألة الخيار الأمثل:

      يمكن استخدام المخطّط العام للخوارزميّات التراجعية في مقارنة الحلول التي يمكن إيجادها لمسألة معيّنة. لإيجاد الحل الأمثل لمسألة معيّنة يجب إيجاد جميع الحلول الممكنة والاحتفاظ دوماً بحل واحد يعد أمثليّاً بحسب معيار معيّن. يجري عادة مقارنة الحلول بواسطة تابع موجب (F(S، حيث S أحد الحلول، عندئذٍ يمكن الحصول على الحل الأمثل بتعديل المخطّط العام للخوارزميّات التي توجد جميع الحلول بحيث تُستبدل بعملية إظهار الحل التعليمات التالية:

      وبذلك يجري الاحتفاظ في كل لحظة بأفضل حل تمّ الحصول عليه في المتحوّل Optimal .

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

      لتكن مجموعة من الأشياء، لكل منها وزن W وقيمةv، والمطلوب بناء مجموعة جزئية من A بحيث يكون مجموع أوزان عناصرها أقل من حد معيّن، ومجموع أسعارها أعظمياً. تصادف هذه المسألة أي مسافر يستعد للسفر بالطائرة، ويقوم بإعداد حقيبته، وعليه اختيار مجموعة صغيرة من الأشياء لا يتجاوز وزنها الإجمالي الوزن المسموح به في المطار.

      عند فحص فائدة عنصر معيّن يستنتج أحد أمرين: إمّا أن يضم هذا العنصر إلى الخيار الآني المزمع بناؤه، أو يستبعد هذا العنصر ويتابع الاختيار من دونه. ويجب مناقشة هذين الاحتمالين كل منهما على حدة، فتكون خوارزميّة الحل كما يلي:

      تبيّن دراسة هذه الخوارزميّة أن هناك اختياراً ممكناً (عدد أجزاء مجموعة مؤلّفة من n عنصراً) لذلك يجب الاستفادة من معايير القبول في الحد استفادة كبيرة من هذا العدد.

      للتعبير عن طريقة المحاكمة السابقة على شكل خوارزميّة يجري بناء المجموعة S التي ستحوي حلاً مقبولاً. في كل خطوة يناقش ضمّ عنصر واحد إلى S وبفرض أن العناصر مرقّمة من 1 إلى n .

      بفرض tw الوزن الكلّي لعناصر S، وأن av هو مجموع قيم عناصر S إضافة إلى قيم العناصر التي لم يُناقش بعدُ ضمّها إلى S. بفرض i رقم العنصر الذي تجري معالجته حاليّاً:

      في البداية :

      ,

      عندما تصبح يكون

      ,

      عندئذٍ يمكن التعبير عن الشرط «الضم مقبول» بالقضية:

      ويمكن التعبير عن الشرط «الاستبعاد مقبول» بالقضية:

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

      يبيّن الشكل (9) نتائج تنفيذ هذا البرنامج على مجموعة تحوي 12 عنصراً حيث أعطيت الأوزان العظمى قيماً تراوح بين 10 و150 كيلوغراماً.

      الشكل (9) مثال لتنفيذ برنامج الاختيار الأمثل

      مراجع للاستزادة:

      - راكان رزوق، مادلين عبود، عمار خيربك، الخوارزميات وبنى المعطيات، جامعة دمشق 2000.

      -J. Arsac, Les bases de la programmation, Dunod
      Informatique 1983.

      - S. Baase, Computer algorithms : introduction to design and analysis, Addison-Wesley 1983.

      - B. Berliox, Ph. Bizard, Construction, preuve et évaluation des programmes, Dunod Informatique 1983.

      - N. Wirth, Algorithms + Data Structures = programs,
      Prentice-Hall, 1975.


- التصنيف : العلوم الهندسية وتقاناتها - النوع : العلوم الهندسية وتقاناتها - المجلد : المجلد الرابع مشاركة :

بحث ضمن الموسوعة

من نحن ؟

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