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


دروس الوزير العالمية - شرح - شروحات - درس » مكتبة دروس الذكاء الاصطناعي Library lessons of artificial intelligence » نظرية التخطيط البياني Graph Theory

 نظرية التخطيط البياني Graph Theory  أضيف في: 30-7-1430هـ
نظرية التخطيط البياني Graph Theory



سنحكي اليوم قصة عالم رياضيات نمساوي اسمه Leonhard Eular كان السبب بعد إرادة الله سبحانه، في اختراع نظرية اسمها Graph Theory في أوائل القرن الثامن عشر، اخترع هذه النظرية لإيجاد حل للمشكلة التي واجهته حينما زار مدينة Königsberg في ألمانيا، هذه المدينة يخترقها نهر river عليه جزيرتين صغيرتين Island1 & Island2. ترتبط هاتان الجزيرتان بضفتي النهر Riverbank1 & Riverbank2 وببعضهما البعض عن طريق سبعة من الجسور Bridges، كما توضح الصورة التالية:



http://www.c4arab.com/images/lessons/programming/AI/general/Graph/graph1.JPG



أراد هذا العالم التجول في إرجاء هذه المدينة بكاملها بدون المرور على جسر أكثر من مرة!
لدراسة إمكانية ذلك؛ قام العالم برسم خريطة توضيحية بسيطة للمدينة، مثّل فيها الجهات التي يريد التنقل فيما بينها (كلاً من Is1, Is2, rb1 and rb2) كنقاط أو أطراف nodes، ثم مثَّل فيها كل جسر كوصلة link تربط بين هذه الأطراف كما هي موجودة في أرض الواقع، هذا التمثيل سمِّيَ Graph أو تمثيل بياني:
-حيث أن Is= Island, rb= Riverbank and b=bridge-



http://www.c4arab.com/images/lessons/programming/AI/general/Graph/graph2.JPG

بعد ذلك أوجد مفهوم جديد يسمى Degree of the Node of the Graph أو درجة الطرف في التخطيط، حيث أن لكل طرف درجة هذه الدرجة هي عدد الوصلات التي تصل هذا الطرف مع الأطراف الأخرى المجاورة له، أي عدد الـlinks الداخلة أو الخارجة من هذا الطرف، من الممكن أن يكون هذا العدد فردي أو زوجي بطبيعة الحال.
لنوجد معاً درجة كل طرف في التخطيط:



DegreeNode5Is13Is23rb13rb2

توصل بعد ذلك إلى النظرية التي تقول:
يمكنك حل المشكلة والمشي في أرجاء المدينة مع العبور على كل جسر مرة واحدة فقط في حالتين:



إذا كان لديك طرفين فقط يحملون درجة فردية two odd degree nodes.
إذا لم يكن لديك ولا طرف من درجة فردية zero odd degree node بمعنى أن جميع الأطراف لديك من درجة زوجية.



عدا ذلك فإن المشكلة مستحيلة الحل ولا يمكنك المشي في أرجاء المدينة دون العبور على أحد الجسور أكثر من مرة!

ثم حدد مسار السير في الحالات التي يمكن حل المشكلة فيها، كالتالي:
إذا كان لديك طرفين من درجة فردية، فإن السير سيبدأ من الطرف ذو الدرجة الفردية الأول، وينتهي عند الطرف ذو الدرجة الفردية الثاني.
إذا لم يكن لديك ولا طرف من درجة فردية، بمعنى أن كل الأطراف من درجة زوجية، فإن المشي سيبدأ من أحد هذه الأطراف وينتهي عند نفس الطرف!
ثم أقرّ بأنه لا يمكنه التجوال في أرجاء مدينة Königsberg بدون العبور على جسر أكثر من مرة، لأنه يوجد أربعة أطراف من درجة فردية في graph هذه المدينة!!
-=-=-=-=-=-=-
عرفت هذه المشكلة باسم "Bridge of Königsberg problem" ومؤخراً أصبحت معروفة باسم العالم: "Finding an Eular path through a graph"، وهي تعتبر حجر الأساس وأول نظرية في عالم الـGraph.
وهذا يقودنا للسؤال: ما معنة كلمة Graph؟!
الـGraph كما رأينا هو مجموعة من الأطراف nodes تربط ما بينهما مجموعة من الوصلات links، من الممكن أن نعتبر كل طرف يمثّل حالة، وللإنتقال من حالة إلى أخرى نستخدم الوصلة التي تصل بينهما.
يفيد تمثيل المشاكل بهذه الطريقة في اختزال واحتواء المشكلة، وزيادة فهمها مما يسهل الطريق إلى حلها، كما تعتبرGraph Theory أفضل أداة للتعليل reasoning في أي تركيب structure يحوي مجموعة من الكائنات objects بينهما مجموعة من العلاقات relations.
في علوم الذكاء الاصطناعي، تستخدم هذه النظرية في تقنيات البحث وخصوصاً في State-space search بنوعيها Depth-first and Breadth-first.

والآن بعد أن انتهينا من سرد القصة وتعرفنا على النظرية كاملة، ما رأيكم بمثال آخر نطبّق النظرية عليه ونرى هل يمكننا حل مشكلته أم لا؟!
إليكم هذه الخريطة:
http://www.c4arab.com/images/lessons/programming/AI/general/Graph/graph3.JPG

أول خطوة، نمثلها كـGraph:



http://www.c4arab.com/images/lessons/programming/AI/general/Graph/graph4.JPG

ثم نوجد درجة كل node فيها:





DegreeNode5Is12Is23rb12rb2

ثم نحدد عدد الأطراف من الدرجة الفردية، يوجد لدينا طرفين من درجة فردية.
إذن المشكلة ممكنة الحل والمشي بدون العبور أكثر من مرة على كل جسر ممكن.
لنحدد معاً مسار المشي الذي لابد من أن يبدأ من أحد الأطراف ذات الدرجة الفردية (Is1 or rb1) وينتهي عند الطرف الآخر، من الممكن أن يكون أحد المسارات التالية:



Is1(through b5) --> rb2(b6) --> Is1(b2) --> rb1(b3) --> Is1(b1) --> Is2(b4) --> rb1



Is1(b1) --> Is2(b4) --> rb1(b3) --> Is1(b5) --> rb2(b6)--> Is1(b2) --> rb1



Is1(b2) --> rb1(b3) --> Is1(b5) --> rb2(b6) --> Is1(b1) --> Is2(b4) --> rb1



rb1(b2) --> Is1(b5) --> rb2(b6) --> Is1(b3) --> rb1(b4) --> Is2(b1) --> Is1



rb1(b4) --> Is2(b1) --> Is1(b5) --> rb2(b6) --> Is1(b2) --> rb1(b3) --> Is1
.
.
.
وهكذا :)



-=-=-=-=-=-=-

إليك مثال آخر:



http://www.c4arab.com/images/lessons/programming/AI/general/Graph/graph5.JPG

يبدو أن مشكلته ممكنة الحل، هل يمكنك حلها؟! نعم أنا واثقة من ذلك، طبّق الدرس عليها مباشرة وأوجد المسارات، ستجد أن كل مسار يبدأ وينتهي في نفس الطرف node.



-=-=-=-=-=-=-



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


الكاتب: الوزير انقر هنا لمراسلة الوزير أنقر هنا للإنتقال إلى موقع الوزير إضافة للمفضلة إضافة لمفضلة Google إضافة لمفضلة Delicious إضافة لمفضلة Digg إضافة لمفضلة Facebook
خيارات الدرس : ارسل الدرس لصديق ارسل الدرس لصديق  طباعة الدرس طباعة الدرس  حفظ الدرس كملف Word حفظ الدرس كملف Word  حفظ الدرس كملف PDF حفظ الدرس كملف PDF

التعليقات
لا يـوجـد تـعليـقات على هـذا الـدرس