طيب بسم الله الرحمن الرحيم المحاضرة هذه هي
المحاضرة الأولى إن شاء الله في المساق هذا طبعًا
إحنا كنا عملنا مقدمة، جاب الـ هكام تعريف بالمادة و
تعريف بالـ syllabus تبعها، و الـ مطبق، و التطلبات الآن
إحنا بنبدأ في الـ topics تبع المساق، و الـ topic الأول
اللي عندنا اللي هو solving problems by searching
ذكرنا أيش دور الـ search في موضوع الذكاء
الاصطناعي، وقلنا إن كثير من المسائل يمكن صياغتها
بحيث إنّه ينطرح أو تنحصر كافة الاحتمالات، أو
الفرضيات الممكنة للتعامل مع المسألة، و التدرج في هذه
الاحتمالات بحثًا عن اللي هو الـ solution
طلبنا مثال، ولكن خلينا نرجع إلى هذا المثال اللي هو
مثال لعبة الـ 8 puzzle، بتذكروها؟ وكان في مثال آخر
لخريطة رومانية، خلينا نرجع عليهم بداية واحدة
للعبة الـ 8 puzzle، زي ما بتذكروا، أو زي ما الكل
بيعرف، عادةً، إنه يكون هنا وضع معين للعبة، و القطع
مُرتبة بترتيب عشوائي. إحنا مطلوب منا أن نرتبها بهذا
الترتيب، أو ممكن برضه كمان يكون بدل من أنه 1,2,3,4
,5,6 زي هيك، ممكن يكون الترتيب المطلوب هو يعني
دائر ما يدور اللوحة، المهم إن في عندنا initial
state أو start state، وفي عندنا goal state أو final
state. اللعبة هذه لو أنا بدي ألعبها، بألعبها عن طريق
إنّي أنا بحرك القطع الصغيرة، القطع المرقمة، حركات إلى
أن أعمل الترتيب. الـ computer لو إحنا بدنا الكلام
عن الـ computer system، الـ computer system برضه
هيعمل نفس الشيء، بأنه يعمل سلسلة من الحركات تؤدي من
الـ start state إلى الـ goal state، وهذه السلسلة من
الحركات هي أصلاً عبارة عن مسار. لو أنا جيت من الـ
start state، أخدت الـ start state، ما بديش أقسم
التفاصيل تبعها الآن، بس بدي أعبر عن التشعب في
الاحتمالات على شكل tree. هذه الـ start state، إيش
الاحتمالات اللي ممكن تنبثق منها؟ يعني مثلًا الآن
الستة ممكن تيجي هنا، الخمسة ممكن هنا، الاتنين ممكن هنا،
ممكن الثلاثة ممكنة، يعني أربع احتمالات بنعبر عنهم
ببساطة على أساس إنه مثلًا الاحتمال الأولاني أن
الاتنين تنزل تحت، الاحتمال الثاني
إنّ الخمسة تروح يمين، الاحتمال الثالث اللي هو الستة
تمشي شمال، الاحتمال الأخير إن الثلاثة تطلع لفوق. كل
واحد من احتمالات هذه بينتج عنه احتمالات نسميها
actions. كل واحد من الـ actions هذه بينتج عنه state
جديدة، مظبوط. الـ state هنا لما إحنا نحرك الاتنين
down، يصير الفرار هنا مظبوط، والاتنين تحت، والباقي
كله زي ما هو. ممكن
تتخيل أنت باقي الـ states الثانية للـ actions الأخرى
لأن كل واحدة من الـ states هذه الأربعة برضه ممكن
تفرع منها مجموعة من الاحتمالات. يعني مثلًا هذا الـ state
الآن، أنا إيش الاحتمالات اللي ممكن تنبثق منها؟ إنه
الأربعة تتحرك شمال، السبع تتحرك يمين، الاثنين تتحرك
ثاني لفوق زي ما كانت. هذا بنحطه إحنا كواحد من
الاحتمالات أو الـ actions. لكن
ممكن نعمل option في الـ system إنه نمنع إنه ياخد
نفس الـ action اللي رجعه على الـ parent state هذا.
الآن هذا الـ parent state تبعها ماشي. فـ… و يتخيل
بابه نفس الشيء اللي نعمله، و الـ states اللي جاية
هنا، و الـ states اللي جاية هنا من هنا. هذا الكلام
بيعطيني فضاء الاحتمالات اللي هو الـ state space.
state space، تمام. الـ tree هذه تُعبر عن الـ state
space لأن
الـ state space هذا، الكمبيوتر لو استطاع… لو إحنا
… يعني استطعنا… استطعنا نخلي الـ system يبني الـ
state space هذا. بعد هالكلام، نخليه أيضًا يعمل إيش؟
search، يبحث في هذا الـ state space، ببحث عن إيش؟ عن
الـ goal state. الـ goal state هذه ممكن تبقى في
حالتنا في اللعبة هذه، ممكن تبقى موجودة في مكان واحد
أو أكثر. يعني ممكن يلقاها من خلال مسار هذا
أو يلقاها من خلال مسار آخر. ليش؟ لأن في اللعبة هذه
بالتحديد، ممكن أكثر من سلسلة من الخطوات تؤدي إلى
ترتيب اللوحة، تؤدي إلى ترتيب اللوحة بالشكل المطلوب.
فأصبحت المسألة أن نحن نستطيع أن نحل مشكلة مثل هذه
المشكلة، الـ 8 puzzle، التي تتطلب ذكاء بشري، ممكن نجعل
الـ system يحلها بذكاء اصطناعي، من خلال أن الـ system
يعمل formulation للمشكلة على شكل tree من الـ start، من الـ
states، الـ possible states، وبعد كده يعمل بحث، يعمل
search في هذه الـ tree، بحثًا عن الـ goal state، و الـ
solution. الـ solution اللي مطلوب هو عبارة عن الـ
goal state، و عن سلسلة الخطوات اللي أدت إليها، بدايةً
من البداية
من الـ initial state. فهذه سلسلة الخطوات بتشكل
المسار، أو الـ path. فالـ path، تمام، هو في حالته الـ
solution، لأن الـ path يحمل في مضمونه الـ start و الـ
goal، ماشي؟ لأن في ممكن يكون في هذه أكثر من path،
أكثر من path يؤدي من الـ initial إلى الـ goal، فبنكون
معنيين بالـ shortest path، وهذه قضية إضافية. المهم في
الأول هي نطلع على آليات اللي ممكن إحنا نصممها أو
ندرسها لعملية البحث في حد ذاتها، عملية الـ
optimization، اللي هو إنه يكون الـ path أقصر ما يمكن،
أو أقل تكلفة. هذه نحكي عنها برضه كمان شوية. الآن هذه
الآليات البحث ممكن نصنفها إلى uninformed
و informed. نحن نحن نحن نحن نحن نحن نحن نحن نحن نحن
نحن نحن نحن نحن نحن نحن نحن نحن نحن نحن نحن
نحن نحن نحن
نحن
في الـ uninformed هنا. uninformed، ولا بدنا ما
نلخبطش ما بين uninformed هذه، وما بين uniform.
دائمًا أنا نفسي بتلخبط منها، ماهيها، بتلخبط منها
ماهيها، تمام؟ هنا uninformed، عشان أنا حطيت الـ dash
بمعنى غير، يعني لا تنظر إلى معلومات إضافية.
الـ Uninformed هي تستفيد من معلومات
إضافية لتحسين أدائها في عملية الـ Search. الـ
Uninformed Strategies التي كتبتموها يا تُوبينا في
منهم اثنتين نعرفهم مسبقًا.
الـ breadth first والـ depth first، صح؟ الـ breadth
first والـ depth first، هدول غالبًا ما بيمروا علينا
في مادة الـ data structure أو في مادة الـ algorithms.
ببساطة شديدة، الـ breadth first هذا بذكر كيف آلية
البحث في هذا الـ… خلي بالك وإحنا لما نقول الآن
strategy، هدول إيش؟ strategies، صح؟ strategy، ندفن على
إنهم search strategies. الآن كلمة Strategy يُقصد
بيها ترتيب زيارة الـ nodes. هدول متفقين على إنهم
nodes هم states، وهم nodes. بنذكر بالفرق بين ليش
أحيانًا بيسميهم states، و ليش أحيانًا بيسميهم nodes.
بنذكر… بس الآن وإحنا بنحكي عن الـ tree بنسميهم
nodes. التنقل من الـ node إلى اللي بعدها، اللي بيحكم
الانتقال من الـ parent إلى مين، أو من الـ node إلى مين،
هذا هو المقصود بالـ strategy. ففي الـ breadth first
strategy، الـ order بيكون من وين لوين؟ لو أنا واقف
على node، وفحصتها، ولقيت إن هي مش الـ goal، بروح
على مين؟ على الـ siblings تبعونها، ماشي؟ بنختار الـ
siblings، حتى وإن كان إلها children، بأجلهم. هذا هو
الفرق الأساسي بين الـ breadth والـ depth، ما بين على
الـ breadth. الـ depth إيش بيسوي؟ بيعطي أولوية للـ children
على الـ siblings، صح؟ وبالتالي الـ breadth بيمسح، بيعمل
scanning للـ tree بالشكل هذا، level by level، مظبوط.
level by level، بيبدأ في الـ initial state، طبعًا الـ
initial state نادرًا بتكون هي الـ goal، صح؟ فبينتقل منها
تلقائيًا، طبعًا هو هيفحصها، هل هي goal؟ لأ، مش goal، تمام.
بينتقل على طول على الـ children تبعونها. الانتقال
إلى الـ children، طبعًا بناء على مين؟ أو تحديد الـ
children بناء على أي actions possible هنا في هذا
الـ state، كان الـ actions أربع actions، بينما هنا
كانت ثلاثة بس، حسب الـ state، بيختلف الـ actions اللي
مسموحة. المهم إنه بعد ما خلص من الـ node هذه، استكشف
إنّها لها أربعة children، اللي أنا بدي آخدهم، بدي آخد
من الشمال، الأولى هذه، بعد هي… بعد ما… طبعًا ما
ياخدها، هيفحصها، هيلاقيها مش goal، فبدي انتقل إلى
واحدة بعدها، هينتقل إلى هذه، لأن breadth first طبعًا
فهينتقل إلى هذا، ثم إلى هذا، ثم إلى هذا. بعد ما يخلص
الـ level كله، بيبدأ في الـ children تبع الأولى، و
بياخدهم برضه كمان واحدة ورا الثانية، وما يخلصوا، و
بعد ما يخلصوا، بتيجي للـ children تبع واحد ثاني، طبعًا
بعدين الـ children تبع واحد ثالثة، إلى إلا إذا لقى
الـ goal موجودة هنا، صح؟ okay. الآن هذا الكلام إحنا
بنعرفه، مش جديد علينا، والـ depth أيضًا، ده عارف إنه مش
جديد علينا. الـ depth هيكون إيش؟ إنه بعد ما ينتقل من
هنا إلى هنا، مش هيشوف هذه، إيش؟ اللي بعد ما يخلص الـ
children تبعهم، فهينتقل على أول child. إذا أول child
برضه إله كمان children، مش هيشوف على أخته، مش
هيشوف أخته. هذا الـ child إيش؟ اللي برضه لما… واضح
فعشان هي اسمها الـ depth، العمق أولًا، depth first. هذه كـ
breadth، الاتساع أو العرض أولًا، صح؟ تمام. الآن قبل ما
ننتقل إلى الـ uniform cost، ولا الـ depth limited، و
لا الـ iterative deepening، اللي هم الـ other
strategies. يعني واحد، اثنين، ثلاثة، أربعة، خمسة
uninformed strategies. خلينا نتفق على بعض المصطلحات
اللي هو موجودة عندنا هنا على الـ slide، يسار فيها.
الـ nodes هذه هي states، قدامي من طلع الـ algorithms
الخوارزميات. بنوضح إيش يعني الفرق ما بين الـ state و
ما بين الـ node. الـ N، خليني أعتبره نفس الشيء. فالـ
node الواحدة هي الـ state، صح؟ الـ actions معروفين،
صاروا واضحين، اللي هو إيش يمكن عمله على الـ state، وكل
واحد من هذه الـ actions إيش بينتج عنه؟ طبعًا هينتج
عنه states جديدة. for each single action، هيطلع
single state. الـ goal test هو
عبارة عن اختبار بده يقع على الـ algorithm، بتوقعه
هذا الاختبار على… على أي واحد من الـ states، عشان بهدف
الفحص، إذا كانت هي الـ goal اللي إحنا بنبحث عنه، ولا
لا، ماشي؟ فالـ goal test هو عبارة عن اختبار بتوقعه الـ
algorithm على الـ state، بهدف إنه يعرف إذا كان هذه
الـ goal… هذه الـ state هي goal بتاعي، خلا
اللي بيوضح عندي أن في four possible actions، تمام
فبمجرد أن نعرف أن في كذا عدد معين من ال
actions، وكل action إيش الـ state اللي.. اللي بيدّي
إلها؟ فخلاص هدول الـ states برمجيا إحنا ممكن نخزنهم
في some data structure على أساس لما ييجي دورهم
للفحص نفحصهم، فهدول هم اللي أقصد أنا بكلمة أنه تم
استكشافهم، تم استكشافهم، ربما أيضا كمان هذه لما
نولّفنا عليها برضه تم استكشاف أن في إلها كذا
possible action بيعطيني كذا possible state، فهدول
أيضا ينضموا إلى مجموعة الـ states اللي تم استكشافها
هذا الاستكشاف هو المقصود هنا بكلمة expansion، فالـ
algorithm بصفة عامة بدها تعمل looping، في كل دورة
من دوراتها، في كل iteration بدها تشوف if there are no
candidates، هذا الـ termination، إذا لم يبقى كل ما تم
استكشافه تم فحصه، لأنه لم يبقى شيء، انتهينا من كل
اللي نريده، يبقى خلاص هذا return failure
لأننا لم نجده، الآن إذا هذا الكلام مش صحيح يعني لسه
ضايل فيه، فبنتقل هنا علشان إيش ناخد واحدة من اللي
ضايلين ونبحث عنها، choose a leaf node
هدول كلهم اللي تم استكشافهم الآن في هذه اللحظة هم
leaves بالنسبة للـ system مابن عرفش إشي وراهم، فهم
بالنسبة له leaves، تمام، choose هنا كلمة
choose هي اللي أشهر في مربط الفرص بالنسبة للـ
strategies، لأن الـ choice بيتمد على الـ strategy في
الـ breakfast بعمل choosing لمن؟ للـ siblings، بالدبف
بعمل للـ children، في غير هيكة حسب إيش الـ strategy
كلمة الآن بالنسبة لك، فـ choose a leaf node for a
strategy according to a strategy، الآن إذا هذا الـ
node contains a goal، هنا الآن إحنا بدنا نميز ما
بين الـ node وما بين الـ state
الـ Node هي أبعاد Data Structure، والـ Data
Structure هذه فيها عدة عناصر أو عدة Properties أو
عدة Data Items، من ضمنها الـ data تبع الـ state، من
ضمنها الوصف تبع الـ state، لكن أيضا في غير الـ state
في عندك مثلا الـ pointers تبعات من الـ parents، وفي
عندك الـ evaluation تبعها
النود هي عبارة عن data structure تحتوي على عدة
مضامين أو عدة content data items، من ضمن هذه وليس
كل شيء هو بيانات الـ state، إذا النود كنتز A goal
state، لو جلك A فلماذا ما جلش الـ V؟ إحنا بيجعلنا
واحدة goal، ولا في كمان added goals في اللعبة
تبعتنا دي؟ فش إلا goal واحد بنحدده إحنا من
البداية أن أنا بدي أرتب اللوحة بهذا الترتيب المحدد
لكن إذا أنا في اللعبة بدي أقبل أنه يرتب هيك أو
يرتب هيك، يعني يفوز اللاعب إذا كان رتبها هيك أو
رتبها هيك، يبقى صار عندي two possible goals، وفي بعض
المثالات الأخرى ممكن يبقى فيها أكثر من possible
goal، أكثر من state تحقق الهدف اللي أنا ببحث عنه، فـ
if the node contains a goal، قد يكون هنا تخيل أنت a
set of goals، وقد يكون هنا الـ set مافيش فيه إلا
state واحدة أو فيه multiple states، فأنا بفحص الـ
node أو الـ state اللي أمامي، بشوف بقارنها هل متطابقة
للـ goal أو أي واحد من الـ goals إذا هم مش متعددين،
multiple goals، else إذا مش مالاقيش الـ goal تبعي
يبقى إيش بده أعمل؟ further expansion، بدي المزيد من
التوسع، بمعنى أنه أشوف هذا الـ node اللي أنا فحصته
وطلعت مش goal، هل بيتفرع منها possible states ولا
لأ؟ هل ممكن في actions تطبق عليها وتعطيّني states؟
إذا ك.. إذا صحيح بنعمل هذا الكلام وبنحفظ الـ
states الجديدة في nodes وبنحطهم في الـ queue في
الـ data structure المعدة، هذه الـ data structure قد
تكون الـ queue، قد تكون stack، قد تكون list
هذا المثال الآن التالي بيطبق المفاهيم هذه اللي شفناها، بس للأسف الـ project مش واضح عشان فيه لون
أخضر ولون أصفر، بس مندي أرجعكم على الخريطة اللي
هي خريطة رومانيا اللي موجودة كمثال في الكتاب، بليست
من المجموعة من المدن، والمدن هذه موصولة البعض بخطوط
كل خط labelled بالرقم، الرقم هذا هو عبارة عن
المسافة، المسافة، ف أنا لو بدي أنا مقبل من هذه
المدينة اسمها Arad، وبدي أروح على هذه المدينة
اسمها Bucharest، ففي عندي طبعا أكثر من أكثر من
مسار، أنا لو بدي كإنسان بدي أدور على المسارات وأحسب
المسارات عشان أشوف مين أكثر واحد شكله بيقول
أنه أقصر واحد، لأن التلات خطوات بس الـ course مش عدد
الخطوات، لازم أحسب إجمالي الـ course تبعت كل الـ hubs
علشان أتأكد، وبعدين أشوف التاني، هاي واحد آخر صح؟
واحد ثالث ورابع، وفي إيش كمان؟ فيه هنا برضه كمان
هاي واحد هيك وهاي واحد هيك وهاي واحد هيك، صح؟ فيه
الـ various
الآن الـ system لو بدي ياخد هذه المسألة هيتعامل
معها برضه على أساس state space problem ويعمل
search في هذا الـ state space، بحث عن المدينة Bucharest
ويحسب كل مسار مُؤدية إلى Bucharest ويطلع الأفضل
لأن لو بدأ نمشي breadth first في عملية البحث هاي
Arad، إيش اللي هي الـ start state تبعتنا، إيش الـ
possible states، أنه ممكن أن أجه في هذا الاتجاه أو
في هذا أو في هذا الاتجاه، الأولاني يوديني إلى
Timisoara هيتم اختصارا، الخيار الثاني يوديني إلى
Sibiu هيتم اختصارا، الخيار الثالث يوديني إلى Zerind
هيتم اختصارا، كل واحدة منهم، يعني لو أنا روحت على
Timisoara، في عندي خيار واحد فقط، لكن لو روحت على
Sibiu، Sibiu في عندها واحد اثنين تلاتة خيارات، مظبوط
لو روحت على Zerind في خيار واحد فقط، صح، الآن نفس
القالب أن إحنا ممكن نتدرج من السلسلة في فضاء
الاحتمالات فيه كله، وطبعا فلا نصل Bucharest في أكثر من
مكان، صح، أكثر من مكان، وبالتالي في أكثر من مسار، هذا
الكلام، خليني أنا بس أضيف ملاحظة هيك على الجانب، إذا
بتذكروا الفرق بين الـ tree والـ graph، إذا
بتذكروا هذا الكلام من الـ data structure، إذا حد
بيذكره، الفرق بين الـ tree والـ graph، إحنا حتى الآن
كلّ رسمنا trees، لكن هذه الرسمة أقرب للـ graph
حد عنده جواب تاني؟ الـ tree زي ما يكون الـ tree
تمثيل لـ graph في حالة خاصة
..حالة خاصة؟ مين هو اللي حالة خاصة؟ الـ tree حالة
خاصة من مين؟ من الـ graph، كيف يعني؟ لأن الـ graph..
الـ graph two way، ممكن الـ child يكون parent، يعني
يكون في بينهم two way relation مع الـ parent أو
كذا parent، يعني ممكن نفس الـ child يكون له كذا
parent، بس في الـ tree لأ، الـ child يكون له parent
واحد، جميل، صحيح هذا الكلام، بنقوله بكلمة واحدة
بسيطة وهي أن في الـ tree مافيش loops، مافيش cycles
صحيح، لأ، يعني أنا هنا أصلا ليش سموها tree؟ الأغصان
ما بتلتقيش تتشبك مع بعض تاني، الأغصان بتتفرع وبتتفرع
ما في غصنين يلتقوا مع بعض أو يتجابلوا مع بعض في إيش
في node، وهذا لو تجابلوا مع بعض في node، معناه ده
أكثر من cycle، فهما في كلاهما عبارة عن مجموعة من
الـ graph والـ tree، مجموعة من الـ nodes مربوطين بـ links
بـ links، مظبوط، إنما ليش الـ tree الـ child له parent
واحد فقط؟ الـ graph ممكن الـ child، هاي الـ child يكون
له two parents، هدول وجودهم أصلا فتح المجال
لوجود إيش؟ الـ cycle، فإحنا الآن الـ search تبعنا
ممكن الـ state space ممكن يبقى tree، تفرعاته
مابتلتقيش، أو يكون إيش؟ graph تلتقى، وفي الحالتين
أنا بتعامل معه بكل الـ strategies هذه، شايف كيف يعني؟
أنا لو أنا الآن هنا على الـ siblings، بدأت أمشي depth
first، بخش بشوف إيش الـ children، وهدول إيش اللي
هتفرع منها، وأشوف هدول، الـ depth first، لو بدأت أدخل
breadth first، بخش على هدول وبستكشف إنهم فيهم الـ
children، بس بروحش أحصيهم بالأول، بروح على مين؟ الـ
siblings، وبعد هيك بأمشي على الـ children تبعهم للـ
siblings، ثم الـ children، فبغض النظر عن أي tree ولا
graph، الـ strategies
هذه ممكن تنطبق، طيب خلينا الآن نكمل في شغلة أخيرة
حسب الوقت اللي عندنا، اللي هو أن إحنا بدنا بعض
المعيار اللي نميز على أساسها ما بين الـ search
strategies
هذا slide يوضح الفرق بين مفهوم الـ state ومفهوم الـ
node، هذا يمثل الـ state، فهي مش أكثر من إيش؟ القطع
وكيف ترتيبها، هذه المعلومات في جزء من الـ data
structure اللي هي الـ node، الـ data structure اللي
بتحتوي على الـ level، والـ depth، والـ parent، وإيش؟
possible actions، خزانين embedded بداخل نفس الـ data
structure، طيب
إحنا المرحلة الـ search strategies اللي قلنا بدنا
نطلع الآن على بعض المعايير أو الـ measures اللي
بنقيم هذه الـ strategies على أساسها، فيه هنا
completeness، وtime complexity
هما بالأساس تلاتة، الـ completeness، والـ optimality،
و الـ complexity، بس الـ complexity، complexity
جمالها في منها إيش؟
completeness واضح من التعريف هنا، إيش معناه؟ هل
كل مرة تجد حل.. يعني هل بتضمن.. هل بتضمن أن تجد
الحل إذا.. إذا كان الحل موجود، إذا كان الـ goal
موجود في الـ tree، هل تضمن أنها تجده؟ ولا ممكن إيش؟ تتوه
عنه أو get stuck في حاجة مثلا local minima قدام
بنوضح هذا الكلام بس في strategies، ممكن في بحثها عن
الـ goal تقع في عند نقطة وما تعرفش لا ترجع عشان
تكمل ولا تجده إذا هو قدامك
هذا المقصود بالـ completeness، هل يجد دائما حل إذا
كان هناك حل؟ الـ optimality، هل الحل الذي تجده
يضمن أنه يكون الأفضل؟ وإلا ممكن تعطينا حل ويكون
في غيره موجود حل أفضل؟ فهذا معيار الحكم أو تقييم
أو evaluation للـ strategy، لأن ممكن نطلع على
التالت اللي نعرفه من الـ breadth first والـ depth
first كمثال، الـ time complexity والـ space
complexity، واضحة الـ time complexity اللي هي جداش
الزمن اللي بتستغرقه، صح صح، مش بالظبط جداش الزمن مش
هو هذا اللي نطلع عليه، لأن هذا الزمن جداش بيعتمد
على عدد الـ nodes وكده، بس نطلع على معدل التغير في
الزمن، وهذا اللي أهم، عينة من جداش الزمن، زي ما بقول
جداش الزمن بعتمد على، بس بيعتمد بأي.. بأي تصارع هل
بيعتمد هيك: كل ما زاد هذا واحد بزيد هذا واحد، كل ما
زاد هذا واحد بزيد هذا اثنين، هذا كله linear، تمام؟
depthوبنانا على الـ D التي هي depth of the least cost solution
ممكن احنا نكون نتصور الـ
complexity نقدر نحسبها، ونقدر الـ complexity سواء
الـ time complexity أو الـ space complexity تبع الـ
strategy طيب الآن احنا معانا بس حوالي خمس دقائق..
بدنا نتعرف فيهم على ليش بعض الاستراتيجيات الأخرى
جد ما نقدر احنا طبعًا اللي احنا صرنا بنعرف ليش أو
already بنعرف الـ depth-first و الـ depth-first، okay
بدنا ناخد فكرة عن ايش هم هدول، وبعدين في
المحاضرة الجاية إن شاء الله نبدأ ندرس.. ناخد
هدول ونحللهم، نعمل analysis لهم من ناحية ليش الـ
complexity والـ completeness والـ optimality يعني
أننا نرجع على الـ breadth-first ونشوف من خلال قليلة
عملها إن نسأل سؤال: هل هي optimal؟ هل هي complete؟
ايش الـ complexity تبعها؟ معدل ازديادها؟ كيف الحال؟ كل
شكله بس في الأول نتطرق على شو يعني uniform cost و
شو يعني depth-limited وشو يعني iterative
deepening
نبدأ بالـ Uniform Cost. في الـ Uniform Cost أنا لو
عندي الـ tree بتتشعب زي الـ tree تبع خريطة
رومانيا، وفي عندي كل node التكلفة
تبعتها معروفة، تكلفة الانتقال من كل link، تكلفة
الموضوع، تكلفة الانتقال من الـ node إلى الـ node
الأخرى، فأنا في الـ uniform cost باجي الانتقال بيكون
محكوم على أساس الـ cost، يعني كيف؟ يعني أنا الآن هنا
أنا
الآن في.. أنا كنت هنا وخلصت منها وماهيش الـ
goal، وصار في عندي ثلاثة children، okay. فحصت هذه الـ
cost هذه x وهذه y وهذه z. ايش هو x، y، z؟ دول الـ
cost. بختار الـ cost اللي أقل أولًا. الآن بعدين جيت
هنا وراجيت إن هذه الـ children ثلاثة، تمام. أنا هنا
خلصت منها، الـ link قفزت هذه، خلصت منها. الآن هل أقفز
هنا ولا هنا؟ وهذه خلصت منها، هل أقفز بعد هذه إلى
هذه ولا هذه ولا هذه ولا هذه ولا ارجع على واحدة
من الـ siblings، محكوم برضه بالـ ايش؟ بالـ total cost
cost هنا ماشي، ف أنا بمشي على اللي بيحكمني أو بيحكم
الـ strategy هذه اللي هو الـ least cost، okay. سمّينا بس
شوية. Expand the least cost. هدفه uniform uniform cost
search. Expand the least cost unexpanded node. الـ node
اللي لسه ما فحصناهاش، بنقيمهم على أساس ايش؟ الـ cost
الـ total إليها من الـ start إليها، وبنبدأ في الأقل
cost أولًا. أساسي عليك كده بتحكي.. بتشوف الأقل cost
دايمًا أقل cost. ممكن أنا موصلش للهدف إلا في الـ goal set
إلا في آخر احتمالية، جيد جدًا، وهذا برضه وارد في الـ
depth، ووارد في الـ.. يعني مثلًا أنا في الـ depth، تعرف
هاي tree عندي، ممكن الـ goal يكون هنا في الـ level
الثاني أو الثالث، صح؟ بس لأن أنا ماشي depth، هشوف
هأمر على كل العالم هذه إلى أن بعدين أشوف هذا، صح؟
فهذه القضية يعني واردة، واللي بده يطبق الـ strategy
هذه بده بناءً على معرفته بالمسألة، ومعرفته غالبًا
وين بيكون الـ goal، منحاز إلى أي جانب، إلى أي level
على هذا الأساس بيقرر: أستخدم هذه الـ strategy أو هذه
يعني إذا احنا بنعرف إن الـ goal إذا بتبقى دايمًا
قريبة تحت، يبقى الأنسب أمشي depth-first مش breadth-
first. إذا أنا بعرف إن الـ goal ما ببعدش كثير مسافة
في هذه الشجرة، ولا في هذه عن الـ initial، ممكن
أستخدم الـ uniform cost، بيوصلني. أنا لو جاش
عارف هو هنا ولا هنا ولا هنا، بس كأني يعني متخيل إنه
منطقة ضيقة هيك، فأستخدم الـ depth-first، الـ list كوصفة
والـ uniform واضح، بس خلينا في الأول نتأكد إن احنا
فهمنا ايش استراتيجية هذه. استراتيجية هذه بتعطي لكل
node سجل معاها رقم. الرقم هذا هو جداشها عن الـ
initial. جداشها الإجمالية بالـ cost مش بالقفزات، مش
بعدد الـ links، بالـ cost، صح؟ وبالتالي بتاخد على ايش؟
على أساس بتاخد الأقل أولًا. خلصنا من هذه الـ uniform.
الـ depth-limited. depth-limited حالة خاصة من الـ
depth-first. الـ depth-limited إنه أنا ببدأ مش زي الـ
depth-first، بس أنا بدي أحكم الـ algorithm إنها
ما تنزلش عن كذا n number of levels. اه يعني مثلًا أنا
كنت هنا وراجيت إن لها children، وخشيت على الـ
children، ثم على الـ children، ثم على الـ children
ما بضالنيش أكشف لما للنهاية، لأ لعند عدد n مثلًا
سواء ستة ولا خمسة من الـ levels، أوقف الـ depth وأبدأ
أرتد، أرتد. يعني بدل ما أتعمق في الـ children، أجي
أبدأ أشوف الـ siblings، مظبوط؟ يعني هاد الآن أنا
ما بجي فيها، هو إذا جيت لها child، بشوفه، بس إذا
هذه لها child، بدور عليه، لإن خلاص، هذه حدودي،
ببتدئ، بشوف الـ siblings هذه وهنا خلاصت، برجع بشوف،
فأنا فيه عندي ايش؟ limit للـ depth، limit للـ depth
عشان كده ايش اسمها؟ depth-limited، depth-limited
search. هي depth-first ولكن عند limit معين. طب أنا لو
خلصت كل اللي أخدت فيه بس ما وصلتش للـ goal، اه وجدتها
نزلت على الـ limit ووجدتها، يا إما أنا بكون حاطط
لنفسى termination condition، إني أنا ماعندي قدرة الـ
system ماعنده time ولا space إنه يتعمق، وبالتالي
بيقل إن أنا فشلت بغض النظر الـ goal موجود ولا لأ، بس فشلت
لأنه أنت حكمتها بـ time و space، فبدأنا على الـ time والـ
space اللي أنت محددينه لها. هو ما لقيش، طبعًا يا إما
بتقوله اشتغل iterative deepening. ايش الـ iterative
deepening؟ اللي هي إنه ابدا أنت في الـ phase
الأولاني امشي depth-first
بس لغاية ما تلاقيش، الـ level الأول، ما لقيتش الـ goal، عيد
الكرة من جديد، والـ limit تبعك اثنين. هنا الـ limit
تبعه واحد، ما لقيش
الـ goal، عيد الكرة من جديد، والـ limit تبعك اثنين.
ما لقيش الـ goal، عيد الكرة من جديد، والـ limit تبعك
اثنين، يعني مش الـ depth، بيبدأ يشوف الـ siblings، بيغطي
كل الـ tree هذه، ما لقيش الـ goal، بيبدأ من جديد، بيشوف
لحد العين ثلاثة، هذا اسمه iterative deepening، يعني
التعمق، deepening، deepening، يعني أنا بعمل
iteratively، يعني بتدرج، واضح؟ هعطيكم رسمة بس بتوضح
الفكرة بسرعة. المحاضرة الجاية بنرجع بنشوف التحليل
اللي هو الـ complexity تبعهم، هذا الـ depth-limited والـ
iterative deepening. طلع حياته، الـ limit هنا واحد
فاجى خش، وغَطّى، ما لقيش الـ goal في الـ iteration
الثانية، الـ depth تبعه اثنين، فراح بدأ من هنا ومشي
depth-first، صح؟
ما لقيش، الـ limit تبعه اثنين، يعني عشان من هنا وشاف
هذا لقيش goal، شاف الـ child تبعه، بس ايش؟ ما بتعمق مش
هيتعمق بعد هيك، بعد الـ child هذا مش هيتعمق أكثر، لأن الـ
limit تبعه خلاص وصل، الـ limit تبعه مظبوط، بيرجع
بيرجع، في الـ iteration اللي بعدها بيزيد الـ limit إلى
ايش؟ إلى ثلاثة. طبعًا التدرج في الـ deepening مش
بضرورة يكون واحد اثنين ثلاثة، يعني واحد limit واحد
level كل مرة، ممكن يعملها واحد اثنين أربعة ثمانية..
أحسب ايش اللي ممكن يفيّد عملية الوصول إلى الهدف
بس واضحة، هذه الفكرة، إن ايش يعني iterative deepening؟
يعني تعمق تدريجي، بس مش تعمق تدريجي بمعنى أنا بفحص
level هذا وبعدين بخش وبعدين بفحص اللي بعده وبعدين
بأخش لأ، برجع جوا، okay. برجع جوا، أبدأ من الـ
initial state في كل deepening stage أو deepening
phase. في عندي multiple iterations، صح ولا لأ؟
multiple iterations، يعني one iteration يعني كل
نقلة هي iteration. طيب الآن احنا المحاضرة الجاية إن
شاء الله بنمر على الكلام اللي هو عبارة عن ليش؟ الـ
Theoretical Analysis أو الـ Complexity Analysis
لأربع أو خمس strategies هذه، وهنطلع عليهم من ناحية
الـ Completeness، من ناحية الـ Optimality، ومن
ناحية طبعًا ليش الـ Complexity، Time، Space. أعطيكم
العافية. إذا في أي سؤال