جديد الصور
جديد البطاقات
جديد الصوتيات
المتواجدون الآن
تغذيات RSS
|
2012-08-14 01:25
نظرية التخطيط البياني Graph Theory
سنحكي اليوم قصة عالم رياضيات نمساوي اسمه Leonhard Eular كان السبب بعد إرادة الله سبحانه، في اختراع نظرية اسمها Graph Theory في أوائل القرن الثامن عشر، اخترع هذه النظرية لإيجاد حل للمشكلة التي واجهته حينما زار مدينة Königsberg في ألمانيا، هذه المدينة يخترقها نهر river عليه جزيرتين صغيرتين Island1 & Island2. ترتبط هاتان الجزيرتان بضفتي النهر Riverbank1 & Riverbank2 وببعضهما البعض عن طريق سبعة من الجسور Bridges،
أراد هذا العالم التجول في إرجاء هذه المدينة بكاملها بدون المرور على جسر أكثر من مرة!
لدراسة إمكانية ذلك؛ قام العالم برسم خريطة توضيحية بسيطة للمدينة، مثّل فيها الجهات التي يريد التنقل فيما بينها (كلاً من Is1, Is2, rb1 and rb2) كنقاط أو أطراف nodes، ثم مثَّل فيها كل جسر كوصلة link تربط بين هذه الأطراف كما هي موجودة في أرض الواقع، هذا التمثيل سمِّيَ Graph أو تمثيل بياني:
-حيث أن Is= Island, rb= Riverbank and b=bridge-
بعد ذلك أوجد مفهوم جديد يسمى Degree of the Node of the Graph أو درجة الطرف في التخطيط، حيث أن لكل طرف درجة هذه الدرجة هي عدد الوصلات التي تصل هذا الطرف مع الأطراف الأخرى المجاورة له، أي عدد الـlinks الداخلة أو الخارجة من هذا الطرف، من الممكن أن يكون هذا العدد فردي أو زوجي بطبيعة الحال.
لنوجد معاً درجة كل طرف في التخطيط:
Degree Node
5 Is1
3 Is2
3 rb1
3 rb2
توصل بعد ذلك إلى النظرية التي تقول:
يمكنك حل المشكلة والمشي في أرجاء المدينة مع العبور على كل جسر مرة واحدة فقط في حالتين:
إذا كان لديك طرفين فقط يحملون درجة فردية 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.
والآن بعد أن انتهينا من سرد القصة وتعرفنا على النظرية كاملة، ما رأيكم
بمثال آخر نطبّق النظرية عليه ونرى هل يمكننا حل مشكلته أم لا؟!
أول خطوة، نمثلها كـGraph:
ثم نوجد درجة كل node فيها:
Degree Node
5 Is1
2 Is2
3 rb1
2 rb2
ثم نحدد عدد الأطراف من الدرجة الفردية، يوجد لدينا طرفين من درجة فردية.
إذن المشكلة ممكنة الحل والمشي بدون العبور أكثر من مرة على كل جسر ممكن.
لنحدد معاً مسار المشي الذي لابد من أن يبدأ من أحد الأطراف ذات الدرجة الفردية (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
.
.
. وهكذا 
-=-=-=-=-=-=-
إليك مثال آخر:
يبدو أن مشكلته ممكنة الحل، هل يمكنك حلها؟! نعم أنا واثقة من ذلك، طبّق الدرس عليها مباشرة وأوجد المسارات، ستجد أن كل مسار يبدأ وينتهي في نفس الطرف node.
-=-=-=-=-=-=-
أرجو عزيزي القارئ أن يكون هذا الدرس قد أعطاك طريقة ذكية لحل مشكلات التنقل أثناء النظر إلى أي خريطة في حياتك اليومية، كما أرجو أن يكون قد وضع أقدامك على نقطة البداية في دراسة أساليب البحث في برامج الذكاء الاصطناعي.. والسلام عليكم
|
|
|
خدمات المحتوى
|
تقييم
|
|
|
الرئيسية
الصور
البطاقات
الأخبار
المقالات
الصوتيات
0 | 
0 | 
673
