• 0
Guest ( HASSAN )

State Space Search Strategies

سؤال

بســـــــم الله الرحـــمن الرحــــــيم

استراتيجيات البحث في الذكاء الاصطناعي

سيتم اظافة اي شرح لاي خوارزمية او طريقة بحث الى هذا الموضوع ان شاء الله منعا للتشتيت ..

==================================

في البدايه لنفرض انه لدينا مشكله معينه ونريد حلها فهذا يتطلب منا فهم واستيعاب لحيثيات هذه المشكله كأن نقول :-

1- تحديد المشكله من خلال تحديد الهدف المنشود من حل هذه المشكله , وماهي الخطوات التي يجب اتباعها للوصول الى الهدف المنشود ..

2- ومن ثم تمثيل المعارف التي نحتاجها لحل هذه المشكله ..

3- ثم اختيار افضل تقنيه او التقنيات المتوفره التي حلت مشاكل شبيه لهذه المشكله ..

لنطرح مثال بسيط ليوضح ما هو المقصود في المقدمه التي في الاعلى :-

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

اذا سالم يتوق للقيام بعدة نشاطات قبل اللحاق بموعد الطائره وهذا وما يسمى تحديد الخطوات التي يجب اتباعها للوصول الى الهدف المنشود وهو اللحاق بالطائره ..

الان للوصل على الموعد لديه عدة خيارات ( الذهاب الى المطار ) ونقطة انطلاقه تكون من مجمع النقليات ..

1- حافلة الزرقاء/ المطار .

2- حافلة جرش/المطار .

3- حافلة اربد / المطار .

4- حافلة عجلون / المطار .

لن يحقق اي من هذه الحافلات الهدف للوصول الى المطار اذا لم يكن لدى سالم خبره ومعرفه سابقه الاتجاهات وجغرافية المناطق وابعادها عن المطار ... لذالك يتوجب الحصول على معارف اضافيه جغرافيا , ليحدد اقصر وافضل وسيلة نقل تقله الى المطار ليلحق بموعد الطائره .. ومن هذه المعارف الاضافيه مثلا الخريطه التي يوجد بها الاتجاهات والابعاد بين المطار وباقي المناطق , فبهذه الطريقه يستطيع سالم الوصول الى هدفه وهو اللحاق بالطائره في اقرب وقت ..

ولكن بشكل عام اذا كان هنالك مشكله وهدف نريد الوصول له مع مجموعه من الخيارات الغير معلوم قيمها , يتم بفحص هذه الخيارات بشكل تسلسلي واختيار افضل واقصر حل .. ومجوموعة التجارب التي يقوم بها والتي تقود للحل تسمى بحث . حيث ان خوارزمية البحث تاخذ المشكلة كمدخل ويرجع بالحلول بكل خطوه تحدث تسلسليا .. وعند الوصول الى الحل باقصر وافضل طريقه يتخذ هذا الحل ويوصى به على انه افضل واقصر الحلول للوصول الى الهدف ..

اعلم ان هذا النوع من الشروحات قد يكون ممل للبعض وقد يجده البعض بسيط جدا او انه بديهي جدا والمفروض ان الجميع يعلم به , ولكن الهدف من هذا الشرح هو تبسيط الامور لاكبر قدر ممكن حتى نستطيع في ما بعد التعمق اكثر واكثر .... وبنفس المبد أ هذا تطبق فكرة البحث في لعبة الشطرنج مثلا ..

الان لنبدأ يوصف المشكله واجزاءها بشكل عام ..

اولا :- نحدد ما يسمى بفضاء المشكله .

ثانيا :- تحديد نقاط او وحدات او عقد الحل المبدأي .

ثالثا :- تحديدعقدة او نقطة الحل النهائي .

رابعا :- تحديد القواعد والخطوات التي تصف الاجراءات او التنقلات التي يمكن اتخاذها .

لنقوم بتمثيل هذه المشكله باستخدام Graph Theory

هذا المخطط او الرسم ( Graph ) يتكون من مجموعه من النقاط او العقد N والتي يربط بينها اقواس Arc

N1,N2,N3,…….,Ni تمثل العقد في فضاء المخطط او الرسم التمثيلي.

Arc يمثل القوس الذي يربط بين عقدتين مثلا N1, N2 .

لاحظ الرسم التالي :- post-168424-12658187338388_thumb.jpg

العقد ( Node ) = {a, b, c, d, e}-------------- الاقواس ( Arc) = {(a,b), (a,d), (d,a), (b,c), (c,b), (c,d), (d,e), (e,d), (e,c)}

==========================================

هنالك نقاط مهمه يجب توضيحها :-

*يكون الـــــ Graph مباشر او مستقيم الاتجاه عندما تكون هنالك Arc من N1 الى N2 باتجاه واحد ولكن لا يكون هنالك Arc من N2 الى N1 من خلال الرسمه السابقه حاول ان تحدد هذه العقد , فاتجاه السهم يمثل اتجاه القوس .. وطريقة ارتباطه بين العقد ..

* rooted graph بحتوي هذا النوع على عقده مميزجدا تسمى الجذر , كأن يكون هنالك مسار واتصال من هذه العقده وجميع العقد والنقاط الاخرى في هذا الرسم او المخطط .

* اما الشجري فهو مخطط يكون به مسار مميز بين كل زوج من العقد ..

=============================================

اما استرتيجيات البحث فتكون في اتجاهين :-

1) من البيانات وحتى الهدف (data driven search ( وتسمى عملية البحث هذه بــــ

forward chaining

2) من الهدف والعوده للبيانات (goal driven search ) وتسمة عملية البحث هذه بــــ

backward chaining

وكلتا الاستراتيجتان تعملان في نفس المخطط مع اختلاف النظام والترتيب في البحث .

امثلة على انظمه وطرق البحث :- والتي يتم بها تحديد ترتيب العقد في المخطط المراد البحث به ..

Breath-first search

Depth first search

لاحقا ساكمل الشرح ان شاء الله ...

تم تعديل بواسطه ( HASSAN )
1

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

11 إجابة على هذا السؤال .

  • 0

تابع ..

لايجاد الطريق من الجبيل ( نقطة البدايه) الى المدينه المنوره ( نقطة النهاية او الهدف ) .

الخطوات :-

اولا:- تحديد نقطة البدايه .

ثانيا:- التحقق مما اذا كانت نقطة البدايه هي الهدف .

ثالثا :- التوسع في الطرق والنقاط من خلال توليد مجموعه من النقاط الجديده .

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

post-168424-12662734959596_thumb.jpg

والشكل التالي يمثل كيفية انشاء الحل :-

post-168424-12662735286367_thumb.jpg

smile.gifان شاء الله تكون الطرق صحيحه ...

===================

لنبدأ في شرح الخوارزميات و طرق البحث ..

Breadth first search

post-168424-12663067337028_thumb.gif

الصوره من ويكابيديا

Breadth first search يبدأ في استكشاف النقاط والعقد من مستوى الى مستوى اخر والذي يمثل نقطه او مجوعه من النقاط

, وهنا تتم البدايه من النقطه او العقده التي تمثل الجذر الاساسي ويتم انشاء وتوليد عقد ونقط اخرى منها اي من الجذر وهلما جرا ,

وعندما لا يكون هنالك اي نقاط اخرى تتولد في هذا المستوى , يتم الانتقال الى المستوى الجديد ...

وترتيب العقد والنقاط تكون على الشكل التالي :-

post-168424-12662749585955_thumb.jpg

وخوارزميات البحث هنا تستخدم قائمتين --- مفتوحه ومغلقه لتتبع مسار البحث .

مفتوحه (Open ) :- وتحتوي على النقاط التي تم انشائها , وبطلق عليها الابناء الذين لم يتم فحصهم للأن .

مغلقه (Closed) :- تحتوي على النقاط التي تم فحصها من قبل .

كيفية تتبع الخوارزميه والتي توضح مبدأ عمل القوائم المفتوجه والمغلقه ( لاحظ الصوره التاليه ) :-

post-168424-1266278142501_thumb.jpg

سافرد طريقة البحث على شكل نقاط :-

1:- الترتيب يبدأ من خلال ازالة العقد او النقط من القائمة المفتوحة الى القائمة المغلقه على حسب ترتيب البحث في العقد .

2:- توليد الابناء من العقد والنقط بواسطة تطبيق قواعد الاستدلال او خطوات الانتقال بين النقاط الاخرى ( المسارات المعطاه ) .

3:- في كل عملية تكرار يتم انشاء الابناء من النقطه X ثم اظافتهم الى القائمة المفتوحه .

4:- القائمه المفتوحه تحفظ بها النقاط على شكل صفوف انتظار , طبعا هنا يتم استكشاف النقاط الاقدم في القائمة المفتوحه اولا .

5:- وتنتهي الخوارزميه في عملية البحث اذا كانت القائمه المفتوحه = فارغه بمعنى ان الخوارزميه بحثت دون الوصول الى الهدف ..

للاستظاحه اكثر عن ما سبق ارفقت ملف يوضح ما تم شرحه في الاعلى من مبدأ عمل الخوارزميه , اتمنى ان يتم

الاطلاع عليه .

لاحقا نكمل ان شاء الله

51demo-bfs.rar

تم تعديل بواسطه ( HASSAN )
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

اخ واستاذي حسان ..

جميل ما اراه الان ..

لكن حزنت كثير عليه ..

الموضوع انت كتبته يوم 10 -2 .. وامتحاني لمادة الذكاء كان 9 - 2 .. وهي ماموجود في هذه المقاله .. اااااااااه ..

كنت بالتأكيد ساستفيد الكثير منها ..

شكرا لك اخي وانتظرك ان تكمل ..

تحياتي العطرة ..

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

لكن حزنت كثير عليه ..

الموضوع انت كتبته يوم 10 -2 .. وامتحاني لمادة الذكاء كان 9 - 2 .. وهي ماموجود في هذه المقاله .. اااااااااه ..

كنت بالتأكيد ساستفيد الكثير منها ..

اشكرك اخي سنان , وابعد الله الحزن عنك وعن من تحب , اتمنى لك التوفيق دائما ..

واعذرني لتأخري عنك , فانا مقصر في المنتدى هنا , ومعك ايظا , لكن الله اعلم بالظروف .

بالتوفيق ان شاء الله

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0
واعذرني لتأخري عنك , فانا مقصر في المنتدى هنا , ومعك ايظا , لكن الله اعلم بالظروف .

بالتوفيق ان شاء الله

اشكرك اخي حسان ..

من ناحية التقصير .. (( ايش اسوي )) ؟؟؟

اعانك الله على مالديك ..

ملاحظه .. ايضا وليست ( ايظا ) !!!!

تحياتي العطرة ..

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

السلام عليكم

شكرا جدا لك على هذا الشرح الرائع لكن يا ريت تكمله

ارجو ان تكمل الشرح عن depth first search

, using the state space to represnt reasoning with the propositional and predicate calculus

الرجاء بالسرعة الممكنة

لأنو الدكتور قسم علينا المادة لنشرحها ويوم الخميس دوري في هذا المجال

انا استفدت كتير من درسك

ارجو ان لا تحرمنا الفائدة

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

أخي حسان هذه طرق البحث العمياء اي أن هذه الطرق ليست ذكية في البحث هل هذا صحيح ؟؟

الأمر الأخر قمت بتمثيل ال BFS على شكل شجرة , في البرمجة هل نستعمل ال tree مثل ما هي أم انها مجرد تمثيل ؟؟!

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

أخي حسان هذه طرق البحث العمياء اي أن هذه الطرق ليست ذكية في البحث هل هذا صحيح ؟؟

الأمر الأخر قمت بتمثيل ال BFS على شكل شجرة , في البرمجة هل نستعمل ال tree مثل ما هي أم انها مجرد تمثيل ؟؟!

وعليكم السلام ورحمة الله وبركاته ..

طرق البحث العمياء هي طرق لا يكون بها معلومات اظافيه عن نطاق المشكله المشار الى حلها , لا نقول انها ليست ذكيه انما هي طرق بحث لا يوجد بها معلومات اضافيه عن مسار البحث او نطاق المشكله , مكوناتها فقط

state, succesor function, goal test and the path cost

هنا انواع المشاكل هي التي تحددنا , طبعا ملاحظه مهمه هذه الطرق تعتبر فقيره وضعيفه في حل المشاكل الضخمه او الكبيره وكما تعلم هذه الطرق مثل :- BFS و DF

الجزء الاخر من سؤالك لم افهمه بالضبط اخي ولكن تمثيل المشكله على شكل شجره يساعدنا في حل المشكله برمجيا مع الاختلاف بصياغتها على حسب الطريقه طبعا , اتمنى ان اكون فهمت قصدك ..  

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

وعليكم السلام ورحمة الله وبركاته ..

طرق البحث العمياء هي طرق لا يكون بها معلومات اظافيه عن نطاق المشكله المشار الى حلها , لا نقول انها ليست ذكيه انما هي طرق بحث لا يوجد بها معلومات اضافيه عن مسار البحث او نطاق المشكله , مكوناتها فقط

state, succesor function, goal test and the path cost

هنا انواع المشاكل هي التي تحددنا , طبعا ملاحظه مهمه هذه الطرق تعتبر فقيره وضعيفه في حل المشاكل الضخمه او الكبيره وكما تعلم هذه الطرق مثل :- BFS و DF

الجزء الاخر من سؤالك لم افهمه بالضبط اخي ولكن تمثيل المشكله على شكل شجره يساعدنا في حل المشكله برمجيا مع الاختلاف بصياغتها على حسب الطريقه طبعا , اتمنى ان اكون فهمت قصدك ..  

جزاك الله خيرا , اجابتك شافية وكافية بارك الله فيك .

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

الله يجزيك كل خير أخي حسان

مواضيع رائعة .. ومفيدة كتيييييييييييير

ربي يرضى عنك ..

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

موضوع جميل جدا وشرح واضح جدا جزاك الله خيرا في انتظار المزيد

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

من فضلك سجل دخول لتتمكن من التعليق

ستتمكن من اضافه تعليقات بعد التسجيل



سجل دخولك الان

  • يستعرض القسم حالياً   0 members

    لا يوجد أعضاء مسجلين يشاهدون هذه الصفحة .