طيب بسم الله الرحمن الرحيم المحاضرة هذه هي
المحاضرة الأولى ان شاء الله في المساق هذا طبعا
احنا كنا عملنا مقدم جاب الهكام تعريف بالمادة و
تعريف بال 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 من الاشمن ال
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الـ 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 ففي ال bred first
strategy ال order بيكون من وين ل وين لو أنا واقف
على node و فحصتها و لاجئتي أن هي مش ال goal بروح
على مين على ال siblings تبعونها ماشي بنتخل ال
siblings حتى وإن كان إلها children بأجلهمو هذا هو
الفرق الأساسي بين ال breadth و ال depth مابين على
الصدر ال depth ايش بيسوي بيهضي أولوية لل children
على ال siblings صح وبالتالي ال breadth بيمسح بيعمل
scanning لل tree بالشكل هذا level by level مصبوط
level by level بيبدأ في ال initial state طبعا ال
initial stateنادر بتكون هي a goal صح فبينتقل منها
تلقائيا طبعا هو هيفحصها هل هي goal لأ مش goal تمام
بينتقل على طول على ال children تبعونها الانتقال
الى ال children طبعا بناء على مين او تحديد ال
children بناء على اي actions possible هنا في هذا
ال state كان ال actions اربع actions بينما هنا
كانت تلاتة بسعسب ال state بختلف ال actions اللي
مسموحة المهم انه بعد ما خلص من ال node هذه استكشف
انه لها اربعة children اللي انا بدي اخدهم بدي اخد
من الشمال الاولى هذه بعد هي كان بعد ما .. طبعا ما
ياخدها هيفحصها هيلاجيها مش goal فبدي انتقل الى
واحدة بعدها هينتقل الى هذه لانه breath firstطبعا
فهينتقل إلى هذا ثم إلى هذا ثم إلى هذا بعد ما يخلص
ال level كله بيبدأ في ال children تبع الأولى و
بياخدهم برضه كمان واحدة ورا التانية و ما يخلصوا و
بعد ما يخلصوا بتيجي لل children تبع واحد تاني طبعا
بعدين ال children تبع واحد تالتة إلى إلا إذا لجأ
ال goal موجودة هنا صح؟ okay الآن هذا الكلام احنا
بنعرفه مش جديد عليناو ال depth أيضا ده عارف انه مش
جديد علينا ال depth هيكون إيش أنه بعد ما ينتبل من
هنا إلى هنا مش هيشوف هذه إيه اللي بعد ما يخلص ال
children تبعهم فهينتقل على أول child إذا أول child
برضه إيه له كمان children مش هيشوف على أخته مش
هيشوف أخته هذا ال child إيه اللي برضه لما .. واضح
فعشان هي اسمها الغمق أولا 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 و بتاعي خلاص
انتهينا لجنة البنية ولا لا ال path cost ماحكي
ناشطي path cost اللي هو التكلفة الإجماليةللمسار
الواصل ما بين ال initial و ال goal لما نلاقيه
مظبوط طبعا غالبا في لعبة زي هذه ال path cost هيكون
ايش مجرد عدد actions عدد ال actions او عدد القفزات
ال hops تمام او النجلات مظبوط او ال moves انما في
مسائل اخرى ممكن النقلة يعني مثلا زي المثال الاخر
تبع خريطة رمانيالانتقال من مدينة إلى المدن الأخرى
اللى ده كل مدينة الانتقال اللى تكلفة مختلفة هنا كل
ال actions له نفس ال cost صح بينما هناك ال action
لو أنا أخد action و روحت على هذه المدينة هتكون
التكلفة غير عن لو أنا أخد action و روحت على
المدينة الأخرىفهيصير ال total cost الإجمالية لو
أنا وصلت للمدينة اللي أنا بديها ال target city لو
وصلت لها من مصار و كان في هناك مصار آخر و مش
بضرورة يكون المصارين إيش متساويين في التكلفة صح
okay هذا مثل الأخر عن السريع بس نبص عليه اللي هو
أنه لو أنا فيه عندي robotic arm دراعوالمطلوب من
هذا الروبوت انه يرتب القطع من الكبير إلى الصغير
ففي هذه المسألة برضه كمان انا ممكن انظر اليها على
اساس state space search صح ولا لأ صح ولا لأ يعني
انا بيكون فيه عند القطع على الطاولة هذه ال initial
state لو هو عمل action ومسك قطعة ونجلها من مكان
لمكان صار في عنده state جديدةال action هو ان ياخد
قطعة و ينجلها اما بيحطها فوق قطعة اخرى او بيحطها
في مكان اخر على الطاولة فكل action بينتج عنه state
جديدة ال state المطلوبة ال goal state هتكون هي ال
state اللي بتكون القطع كلها جاعدة فوق بعض من
الصغير للكبيرفهو عند كل state بيبقى فيه عنده
multiple actions ممكن ياخدها انه يجيب الجطع هذه و
لا الجطع هذه ياخدها يحطها فوق هذه و لا يحطها فوق
هذه تمام ففي عنده ايش various actions ممكن يعملها
عند كل واحدة من ال states فهنا ال states بتكون
عبارة عن coordinates لكل الجطع كل جطعة و ايش
احداتها تبعها على الطاولةوالـ Action إنه إن يحرك
الـ Arm من مكان لمكان و ينقل فيه يشيطانو ال test
هو هل جمع القطع أو ركّب القطع في بعض ولا لأ و ال
path cost اللي هي الزمن مظبوط الزمن الإجمالي
للترتيب طبعا هنا المسألة هذه ممكن يكون يعمل ترتيب
القطع بطرق مختلفة وكل طريقة تكون التكلفة مختلفة عن
الطريقة الأخرى
أحنا الآن بنطلع على ال algorithm هذه اللي هي
general search algorithm بتغطي كل ال strategies
المختلفة طيب الآن احنا العملية ال search من
الطبيعي انها تكون loop مظبوط ل loop من action ل
action كل action بيعطي status جديدة فتخيل
انه الال states أو ال nodes اللي أمامه أثناء عملية
ال search هيكون بعض منها تم استكشافه استكشافه غير
عن فحصه و البعض منها لسه احنا مادراش عنها مثلا انا
لما ارجع واقف على ال initial state
اللي بيواضح عندي ان في 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 return failure
لأننا لم نجده الآن إذا هذا الكلام مش صحيح يعني لسه
ضايل فيه فبنتقل هنا علشان إيشناخد واحدة من اللي
ضايلين و نبحث عنها choose a leaf node leaf node
هدولة كلهم اللي تم استكشافهم الآن في هذا اللحظة هم
leaves بالنسبة لل system مابنعرفش اشي وراهم فهم
بالنسبة له leaves 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 و بنحطهم في الاش في
ال data structure المعدة هذه ال data structure قد
تكون ال queue قد تكون stack قد تكون list
هذا المثال الآن التالي بيطبق المفاهيم هذه اللي دول
شفناها بس للأسف ال project مش واضح عشان فيه لون
أخضر و لون أسفر بس ماندي أرجعكوا على الخريطة اللي
هي خريطة رومانيا اللي موجودة كمثال في الكتاب بليست
من المجموعة من المدن و المدن هذهو نوصل البعض بخطوط
كل خط labelled بالرقم الرقم هذا هو عبارة عن
المسافة المسافة فانا لو بدى انا مقبل من هذه
المدينة اسمها Qarad و بدى اروح على هذه المدينة
اسمها Bucharest ففي عندى طبعا اش اكتر من اكتر من
مسار انا لو بدى كانسان بدى ادور على المسارات و
احسب المسارات عشان اشوف مين اكثر واحدشكله بيقول
انه اقصر واحد لان تلتاش نجلات بس ال course مش عدد
النجلات لازم احسب اجمالي ال course تبقى كل ال hubs
علشان اتأكد و بعدين اشوف التاني هاي واحد اخر صح؟
واحد تالت و رابع و في ايش كمان؟ في هنا برضه كمان
هاي واحد هيك و هاي واحد هيك و هاي واحد هيك صح؟ في
ال various
الان ال system لو بدى ياخد هذا المسألة هيتعامل
معاها برضه على اساس state spaceproblem ويعمل
search في هذا ال state space بحث عن المدينة بوخرست
ويحسب كل مسارقة المؤدية الى بوخرست ويطلع الأفضل
لأن لو بدأ نمشي bread first في عملية البحث هاي
قرات ايش اللي هي ال star state تبعتنا ايش ال
possible states انه ممكن ان تجه في هذا الاتجاه او
في هذاأو في هذه التجارة الأولانية يودّيني الى
تماسورة هيتم اختصارا الخيار التاني يودّيني الى
سيبيو هيتم اختصارا الخيار التالت يودّيني الى زرند
هيتم اختصارا كل واحدة منهم يعني لو انا روحت على
تماسورة في عندى خيار واحد فقط لكن لو روحت على
سيبيو سيبيو في عندها واحد اتنينتلات خيارات مظبوط
لو روحت على زرند في خيار واحد فقط صح الان نفس
القالية ان احنا ممكن نتدرج من السلسل في فضاء
الاحتمالات فيه كله و طبعا فلاجي بخرست في اكثر من
مكان صح اكثر من مكان وبالتالي في اكتر من مسار هذا
الكلام خليني انا بس اجف ملاحظة هيك على الجانبإذا
بتذكروا الفرق بين ال tree و ال graph اذا
بتذكروا هذا الكلام من ال data structure اذا حد
بيذكره الفرق بين ال tree و ال graph احنا حتى الآن
كل رسمنا trees لكن هذه الرسمة أقرب لل graph
حد عنده جواب تاني ال three زي ما يكون ال three
تمثيل ل graph في حالة خاصة
.. حالة خاصة؟ مين هو اللي حالة خاصة؟ ال three حالة
خاصة من مين؟ من ال 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الـ 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 طيب
احنا المرحلة ال monster strategies اللي قلنا بدنا
نطلع الآن على بعض المعايير او ال measures اللي
بنقيم هذه ال strategies على اساسها فيه هنا
completeness و time complexity
هما بالأساس تلاتة ال completeness و ال optimality
و ال complexity بس ال complexity complexity
جمالها في منها ياشي
completeness واضح من التعريف هنا، إيش معناته؟ هل
كل مرة تجد حل .. يعني هل بتضمن .. هل بتضمن أن تجد
الحل إذا .. إذا كان الحل موجود، إذا كان ال tree
موجود في الحلهل تضمن انها تجده ولا ممكن ايش تتوه
عنه او get stuck في حاجة مثلا local minima قدام
بنوضح هذا الكلام بس في strategies ممكن في بحثها عن
ال goal تجه في عند نقطة وما تعرفش لا ترجع عشان
تكمل ولا تجده اذا هو قدامك
هذا المقصود بالcompleteness هل يجد دائمًا حلوة إذا
كان هناك حلوة؟ الoptimality هل الحلوة التي تجدها
تضمن أنه يكون الأفضل؟ وإلا ممكن تعطينا حلوة ويكون
في غيره موجود حل أفضل؟ فهذا معيار الحكم أو تقييم
أو evaluation لل strategyلأن ممكن نطلع على
التالتين اللي نعرفه من ال breadth first و ال depth
first كبثال ال time complexity و ال space
complexity واضحة ال time complexity اللي هي جداش
الزمن اللي بتستغرقه صح صح مش بالظبط جداش الزمن مش
هو هذا اللي نطلع عليه لأن هذا الزمن جداش باعتمد
على عدد ال nodes و كده بس نطلع على معدل التغير في
الزمنهو هذا اللي أهم عينة من جداش الزمن زى ما بقول
جداش الزمن بعتمد على بس بيعتمد بأى .. بأى تصارع هل
بيعتمد هيك كل ما زاد هذا واحد بزيد هذا واحد كل ما
زاد هذا واحد بزيد هذا اتنين هذا كله linear تمام؟
لكن ممكن يبدأ وهذا اشي ماشي كويس بس ممكن يبقى زى
هيكإن عند حد معين عند حد معين من الزيادة في عدد ال
notes بتلاقي الزمن بدأ يتسارع بشكل إيش فاحنا اللي
بهمنا في ال time complexity هو معدل التسارع في
الزمن مش ال هذا و كذلك حال معدل التزايد بالنسبة لل
space معدل التزايد في ال إيشفي حجم ال memory
المطلوب معدل التزايد هل بتزايد linear ولا بتزايد
some other function تكون مثلا exponential أو
logarithmic او square فإحنا ال linear هو ألطف معدل
تمام تقريبا
ماشي ال ال ال ال ال ال ال ال ال ال ال ال ال ال ال
ال ال ال ال ال ال ال ال ال ال ال ال ال ال ال ال ال
ال ال ال ال ال ال ال ال ال ال ال ال ال ال ممكن نقي
و ال tree هذه او حتى ال graph يعني و بتتفرع تمام
طبعا ممكن بعض ال notes يتفرع يبقى فيه إلى زي ما
شوفنا تاوي two children بعضهم يلهم one single
children بعض تلاتة بعض ممكن يبقى اربعة ممكن اكتر
فاحنا لو جينا حسبنا اه جينا عملنا جربت لك كافة ال
notes هي واحد هي اتنين هي تلت هي اربع هي خمسةواحد
اتنين تلاتة اربعة خمسة وكل واحدة عملنا عملية جرد
عملية احصائية جداش فيه الها children number او
children هذا اله جداش اربعة لان هو الأولى هنا
اتنين اله خليني اقول تلاتة و تلاتة الها اربعة و
اربعة اله child واحد و اتنين خمسة خمسة الها two
childrenفجمعنا هذا الكلام كله كم طلعت؟ اربعة عشر
على خمسة اربعة عشر وعددهم هذوله عددهم مش .. هذا مش
مجميع هذي هذا ترقيم اربعة عشر على خمسة عدد ال
children على عدد الأباء بتطلحه ال branching factor
يعني متوسط التفرق متوسط ال branching هذا ذو دلالة
بيعطيني دلالة على كيف ال tree بتكبر تتوسع اذا صغير
مابجهاشtemplate tree نحيفة صح إذا كبير تبلتري
بتتفرع
بشكل بتسعة كبيرة ال depth of هنا ال maximum depth
of the space جداش ممكن يمد معايا أنا انتجلت للأوصل
التالت التالت حتجعلهالأولى قررنا منه التالت اللى
هو كدهش ال maximum depth فى بعض ال search spaces
مالهاش maximum infinite depth ممكن يمدى لما لانها
و هذا سائق جدا طبعا بس بعض ال problems بعض المسائل
ممكن نقدر ال maximum depth تبعها لحد معين okay هذا
ال maximum غير عن الاشالـ least cost solution الـ
depth تبعه احنا ممكن برضه نكون هناك قدر من التقدير
لوين ال solution ممكن يكون واقع على الأربع levels
الأولى جوال عند مثلا العشر levels العشرين level
بال average يعني طبعا هذا التقدير على حسب المسألة
وعلى حسب تجارب سابقة يعني تمام فبنان على ال
pricing factor وبنان على ال M اللي هي maximum
depthوبنانا على ال D التي هي depth of الاياش least
cost solution ممكن احنا نكون هي نتصور ال
complexity نقدر نحسبها و نقدر ال complexity سواء
ال time complexity او ال space complexity تبع ال
strategy طيب الآن احنا معانا بس حوال خمس دقايقب ..
بدنا نتعرف فيهم على ليش بعض الاستراتيجيات الأخرى
جد ما نقدر احنا طبعا اللي انا صارنا بنعرف ليش او
already بنعرف ال dead first و ال dead 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 محكم برضه بال إيش بال cost ال total
cost هنا ماشي فانا بمشي على اللي بيحكمني او بيحكم
ال strategy هذه اللي هو ال least cost okay سمان بس
شويةExpand ال least cost هدفه Uniform Uniform cost
search Expand ال least cost Unexpanded note النوت
اللي لسه ما فحصناهاش بنقيمهم على أساس إيش ال 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 ممكن
أستخدم ال mean ال uniform cost بيوصللي أنا لو جاش
عارف هو هنا ولا هنا ولا هنا بس كإني يعني متخيل إنه
منطقة بضار هيكفبس أخدم ال depth first ال list كوصة
و ال uniform واضح بس خلينا في الأول نتأكد ان احنا
فهمنا ايش استراتيجية هذه استراتيجية هذه بتعطي لكل
note سجل معاها رقم الرقم هذا هو جداش بعضها عن ال
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 limiteddepth limited
search هي depth fast ولكن عند limit معين طب انا لو
خلصت كل اللي اخدت بس ماوصلت عشان ال goal اه وجدتها
انزلت على ال limit وجدتها يا اما انا بكون حاطط
لنفسي termination condition انه انا ماعندي قدرة ال
system ماعنده time ولا space انه يتعمق وبالتالي
بيقل ان انا فشل بغض نظر ال goal موجود ولا لأبس فشل
لأنه انت حكمته ب time و space فبدأنا على ال time و
space اللي انت مقاطعينه ليه هو مالجهش طبعا يا اما
بتقوله اشتغل iterative deepening ايش ال iterative
deepening اللي هي انه ابدا انت في ال phase
الأولاني امشي depressed
بس لغاية تلاقيش ال level الأول مالجتش ال goal عيد
الكرة من جديد و ال limit تبعك اتنين هنا ال limit
تبعهم one مالجتش
ال goal عيد الكرة من جديد و ال limit تبعك اتنين
مالجتش ال goal عيد الكرة من جديد و ال limit تبعك
اتنين يعني مش ال depthبيبدأ يشوف ال siblings بيغطي
كل ال tree هذه مالجاش ال goal بيبدأ من جديد بيشوف
ليش العين تلاتة هذا اسمه iterative deepening يعني
التعمق deepening deepening يعني انا بتعمل
iteratively يعني بتدرج واضح؟ هعطيكوا رسمه بس بتوضح
الفكرة السريعو المحاضرة الجاية بنرجع بنشوف التحليل
اللي هو ال complexity تبعهم هذا ال depth limited و
ال iterative deepening طلع حياته ال limit هنا one
فأجى خش و أغطى مالجاش ال goal في ال iteration
التانية ال depth تبع اتنين فراح بدأ من هنا ومشي
depth first صح؟
مالجهش ال limit تبعه اتنين يعني عشان من هنا وشاف
هذا لجه مش goal شاف ال child تبعه بس ايش بتعمق مش
هتعمق بعد هيك بعد ال child ده مش هتعمق اكتر لأن ال
limit تبعه خلاص وصل ال limit تبعه مظبوط بيرجع
بيرجع في ال iteration اللي بعدها بزيد ال limit الى
ايش الى تلاتة طبعا التدرج في ال deepening مش
بضرورة يكونواحد اتنين تلاتة يعني واحد limit واحد
level كل مرة ممكن يعملها واحد اتنين اربعة تمانية
احسب ايش اللي ممكن ي feed عملية الوصول الى الهدف
بس واضحة ده الفكرة ان ايش يعني 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 Timespace أعطيكم
العافية إذا في أي سؤال