بســم اللــه الرحمــن الرحيـــم
السلام عليكم و رحمة الله و بركاته
ولدي أحب أن يشارك باسم أبيه أرجو أن يكون الموضوع ذا فائدة كما أرجو التفاعل :
ربما كانت آخرُ مشاركاتي في المنتدى منذ ما يقارب الستة أشهر
ولكن كان ذلك بسبب الانشغال بالدراسه و الآن أشارك بموضوع أعتقد
أنه مهم لكل محب للبرمجة و لعشّاق حل المسائل المعقدة بواسطة الحاسب
و رغم أني مبببببتدئ جدددداً جدددداً إلا أني سأضع ما في جعبتي ليستفيد
منه الجميع و لعل و عسى أن يوجد أحدآخر يزيد فأستفيد و يستفيد الجميع
قبل البدء بالأمثلة سأبدأ بتعريف بسيط لما يدعى بالخوارزميات التراجعية
هي عبارة عن خوارزميات بسيطة تعتمد مبدأ التجريب و الخطأ في حل المسائل
أي بمعنى آخر الحصول على جميع الإحتمالات الممكنة لمسألة...
{و تتلخص بإيجاد الحل النهائي لمسألة باتباع مجموعة من الخطوات}
أي لدينا مسألة معينة و لدينا مجموعة من الخيارات مثلاً تحريك حصان على رقعة شطرنج
بحيث يتحرك الحصان على كل الرقعة و لا يمر بنفس المربع مرتين طبعا الحصان يكون في المسقط (1,1) في البداية
لدينا مجموعة من الخيارات لتحريك الحصان نختارها واحدا تلو الآخر
مثلا ليكن لدينا حالتين نختار الأولى ثم نعيد المناقشة كما سبق حيث نرى الحالات الممكنة لحركة
الحصان من هذاالمربع إلى بقية المربعات و هكذا...
و نناقش في كل انتقالة امكانية القيام بها أو لا
للتوضيح أكثر:
لاحظ الشكل المرفق رقم 1 لوحة شطرنج نلاحظ وجود 8 احتمالات لحركة الحصان
نفرض أن الحصان قام بواحدة من هذة الحركات ثم نسأل هل مر الحصان مسبقا على هذا المربع
نعم===> تراجع و اختر الحركة التالية
لا=====> أوجد احتمالات حركة الحصان من هذه النقطة ونعيد المناقشة السابقة
بشكل عام سوف نمر بجميع الاحتمالات و نحصل على مخطط شجري كما في الشكل 2
لدينا ثمانية أفرع رئيسية يتفرع من كل منها 8 فرعية و من كل واحدة من الفروع الفرعية يتفرع ثمانية
وهكذا ... 64 مستوى في لوحة الشطرنج النظامية 8*8 =64
طبعا ربما لن يستوعب معظم القراء 100% مما قلت لأنني أنا نفسي لم أستوعب ذلك إلا بعد القراءة و
التفكير و التدبر و التمحيص
لساعات و ساعات طبعا كل هذا الكلام نظري و السبيل العملي لتطبيقه على الحاسب هو استخدام
الخوارزميات التراجعية و التي أعرفها أخيرا بأنها التطبيق العملي لعلم الاحتمالات على الحاسب فهي
تسمح لهذه الآلة بالوصول إلى كل الاحتمالات الممكنة و معالجتها...
ولكن قبل البدء بحل مثال الحصان سنبدأ بمثال بسيط يبين أبسط شكل للخوارزميات التراجعية
حساب عاملي عدد موجب
إن التعريف الرياضي لدالة العاملي هو
س!=
*) 0!=1 :س=0
*) 1!=1 :س=1
*) س!=س(س-1)! : س لايساوي 1 و0
لو عرضنا هذه المسألة على شخص لإيجاد عاملي 5 مثلا يقول:5!=5*4*3*2*1
و أي مبرمج يحلها بواسطة حلقة for مع وضع شروط من أجل الصفر
مثال بيسك:
s=1
for n = 1 to 5
s=s*n
next
print n
لكن و بواسطة الخوارزميات التراجعية يمكن حلها كمايلي
مثال باسكال
program a;
var
c:integer;
var b:integer;
procedure cal(x:integer);
var
b1:integer;
begin
b:=1;
if ( x<>1 ) and (x<>0) then
begin
b1,cal(x-1);
b:=b1*x;
end
end;
begin
c,cal(5);
writeln©
end.
ربما ترى أن هذه الطريقة صعبة للفهم و الكتابة و لكنها علمية أكثر لأنها تطبيق عملي للتعريف النظري
للعاملي و هي الطريقة المنهجية الصحيحة.
الآن سأذكر المخطط العام لهذا النوع من الخوارزميات في حل المسائل
الإجراء
procedure try(مجموعة من متحولات الادخال و الاخراج);
{تسبق متحولات الإخراج ب var }
var
المتحولات المحلية المستخدمة داخل الإجراء فقط
begin
مجموعة من القيم الابتدائية
repeat
if (شرط محقق للقيام بخطوة) then
قم بخطوة(مجموعة من التعليمات(
if ليست آخر خطوة then
try(مجموعة من القيم+متحول إخراج)
if (متحول اخراج لا يحقق شرط ) then
تراجع عن الخطوة التي قمت بها
else
توصلنا إلى أحد الحلول;
until متحول الاخراج يحقق شرط معين أو أن جميع الاحتمالات التالية لهذه الخطوة قد انتهت
end;
لناخذ كل خطوة من المخطط العام السابق و نستنتج تفصيلاتها على مسألة الحصان
1) متحولات الادخال هي رقم الخطوة التي سيخطوها الحصان و احداثيات الخطوة السابقة
و متحول إخراج ليبين لنا هل يمكن المتابعة في هذا الخيار أم لا
و بالتالي يصبح كما يلي:
procedure try (i:integer;x,y:integer;var q:boolean);
2) المتحولات المحلية المستخدمة داخل الإجراء فقط
أنت مخير في استخدامها حسب الحاجة هنا في هذا المثال سنعرف متحول صحيح k يعبر عن عدد الحركات التي يمكن أن يقوم بها الحصان 8
حركات القيمة الابتدائية 1 و تزداد مع التكرار إلى أن تصل إلى 8 لتعبر عن فرع الشجرة الذي اخترناه
ونعرف متحولان يعبران عن الاحداثيات الجديدة هما u للسينات و v للعينات (الصادات)
إضافة إلى متحول منطقي q1 من النوع boolean يساعد في عملية المحاكمة لمعرفة النجاح في الوصول إلى حل أو لا
3)شرط محقق للقيام بخطوة
1)هذا الشرط يتلخص بعدم مرور الحصان على المربع من قبل و أن إحداثيات المربع ليست خارج لوحة الشطرنج
يتبادر إلى الذهن سؤال كيف يتم حساب الاحداثي الجديد للحصان بعد الانتقال
2)أي كيف ستخبر الحاسب بطريقة انتقال الحصان و التي هي على شكل حرف L
هنا نصمم مصفوفتين(a1,a2( أثنار بدء البرنامج من ثمانية حقول كل منهما إحداهما للسينات و الأخرى للعينات
باعتبار لوحة الشطرنج لها محورين احداثيين فمن أجل النتقال من الاحداثي x كما في الشكل 1 إلى الاحداثي (1)
نضيف لعينات(صادات) x اثنين(2) و لسينات x سالب واحد(-1)
3)الشروط: السينات و العينات(الصادات) الجديدة بين 1 و 8 و المربع لم يمر عليه مسبقاً
للقيام بآخر شرط نكوّن مصفوفة تحتوي على مساقط لوحة الشطرنج هي h(n,n)
حيث في لوحة الشطرنج النظامية n=8 كما هو معلوم حيث أن عناصرها هي من النوع integer
و يصرح عنها في بداية البرنامج فاحتواء أحد عناصرها على القيمة صفر يدل أن الحصان لم يمر على
المربع الموافق بعد أو أن يحتوي على رقم يدل على رقم الخطوة التي مر بها الحصان على المكعب
للتعبير عن الشرطين الأولين يمكننا إنشاء مجموعة تحوي الأرقام 1 إلى 8 مثل s و اختبار شرط انتماء v وu
إلى هذه المجموعة أو اتباع أدوات المقارنة >,<,= فنصل إلى ذات النتيجة و بالتالي يكون ملخص ما ذكرته حتى الآن
procedure try (i:integer;x,y:integer;var q:boolean);
var
q1:boolean
k:integer
v,u:integer;
begin
k:=0;
repeat
q1:=false;
k:=k+1;
v:=y+a2[k;]u:=x+a1[k];
if (u in s) and (v in s) and (h[u,v]=0) then
هنا i تدل على رقم الخطوة
4)قم بخطوة:
إن عملية قم بخطوة تعني استبدال الصفر في عنصر المصفوفة h ذي الاحداثيات u,v
برقم الخطوة التي سيقوم بها الحصان وذلك من خلال التعليمة h(u,v)=i;
5)ليست آخر خطوة
بما أن الحصان سوف يمر على كل مربع في لوحة الشطرنج و لمرة واحدة فقط إذا عدد جميع الخطوات
هو n*n حيث n=8 ======> آخر خطوة هي n*n و بالتالي إذا كانت i < n*n ====> ليست آخر خطوة
أما إذا كانت آخر خطوة و بما أن هذا المكعب لم يمر عليه الحصان مسبقاً لذلكفإننا نختارة مباشرة و
نعطي لـ ض1 قيمة true
6)try(مجموعة من القيم+متحول إخراج)
ندخل إلى الإجراء من داخل الإجراء نفسه و هذا هو لب الموضوع و السر الذي يجعل الخوارزمية تعالج
جميع الحالات و تأخذ المعالجة شكل شجري شبية بأسلوب حل بعض المسائل في الاحتمال
q1,v,u,try(i+1);
7) عندما يعود متحول الاخراج q1 بقيمة false ====>وصول الاجراءات أثناء الاستدعاءات المتتالية إلى طريق مسدود
و هو حالتين :
*)إما أن نكون قد و صلنا إلى مربع على اللوحة لايمكن الانتقال منه إلى غيره لأنها جميعا
قد مر عليها مسبقا
*)أو أن المربع المراد الانقال إليه قد مر عليه مسبقاً
وهنا نتراجع عن الحركة الأخيرة بإعطاء عنصر المصفوفة المقابل للمربع القيمة صفر
8)شرط التكرار حتى الوصول إلى إحدى الحالتين :
*)إما انتهاء حالات الحركة من المربع إلى المربعات الأخرى و هي بشكل عام ثمانية كما ذكرنا سابقا
*)أو أن نصل إلى قيمة true لـ q1 أي و صلنا إلى حل مرحلي لعقدة في الشجرة أو نهائي كما في الحالة المذكورة
في البند رقم 5
إن هدف التكرار هو المرور على جميع الحالات العامة الثمانية لحركة الحصان من مربع على رقعة الشطرنج
إلى مربع آخر.
sqrn=n*n في مثالي و ضعته هو و n كثوابت في بداية البرنامج
فيكون الشكل النهائي للاجراء
procedure try (i:integer;x,y:integer;var q:boolean);
var
q1:boolean
k:integer
v,u:integer;
begin
k:=0;
repeat
q1:=false;
k:=k+1;
v:=y+a2[k;]u:=x+a1[k];
if (u in s) and (v in s) and (h[u,v]=0) then
begin
h[u,v]:=i;
if ibegin
try(i+1,u,v,q1);
if not q1 then h[u,v]:=0;
end
else
q1:=true;
end;
until(q1) or (k=8);
q:=q1;
end;
يتبع
