• ماهو المنتدى؟ المنتدى هو مكان يجتمع فيه الاشخاص لتبادل الافكار والنقاشات وكان له تاريخ في بناء اجيال عملاقة في مجالات امن المعلومات وتاريخ ضخم كان يضم ترياق العرب وكان يضم منتديات العاصفة وكان يضم ترايدنت وكان يضم نقطة التطوير وكان يضم امان العرب وكان يضم الصاعقة وغيرها الكثيير..

    وما شبكة شل الا فكرة قديمة جاءت بعد الاختفاء للمنتديات العملاقة وما هدفنا الا الارتقاء بمجالات التكنولوجيا عموماً ومجال أمن المعلومات خصوصاً كما كان الحال في الماضي مع عدم تكرار الاخطاء.

شرح خوارزمية coloring لإيجاد عدم التوافق

Mina

./عضو

  • التقييمات: 0
  • #1
بسم الله الرحمن الرحيم
لنفرض أن شركة مختصة في صنع محاليل كيمياىية مختلفة ولنفرض أنها ستة مواد (p1,p2,p3,p4,p5,p6) يجب عليها ضمان نقل وتسليم هذه المحاليل عن طريق قطار بكميات ليست كبيرة , تحذير!! هناك بعض المحاليل لا يجب أن تتواجد في نفس الشحنة مع محاليل أخرى ضماناً للسلامة (فبعض المحاليل في حالة ملامستها مع محاليل أخرى قد تؤدي إلى احتراقٍ شديد أو حتى انفجار ).

فهذه قائمة المعطيات:
  1. p1 لايجب أن يُنقل مع p, 2p3 أوp4
  2. p2 لايجب أن يُنقل مع 1p,p3 أو p5
  3. p3 لايجب أن يُنقل مع 1p,p2 أو p4
  4. p5 لايجب أن يُنقل مع 2p أو p6
فكم تحتاج الشركة من مقطورة لنقل هذه المحاليل الستة ؟ فهنا يمكننا استعمال خوارزمية coloring algorithm واه زي اسمها ما بيوحي بتعتمد على التلوين , هي خوارزمية كثير ممتعة ويمكن استعمالها في أي مشكل فيه incompatibility أو مايعرف بعدم التوافق فخلونا نحلها على بركة الله :

فهون ببساطة نرسم المواد الموجودة ونربط كل مادة مع المادة التي لا يجب أن تنقل معها مثلاً p1 نربطها مع كل من p2,p3,p4 (وعلاقة p1 لا يجب أن تكون مع p2 هي نفسها p2 لا يجب أن تكون معp1 فتمثل مرة واحدة )كما هو موضح بالصورة.

captheo.PNG
ثم نرتبها على هذا الشكل بحيث نبدأ من أكبر node (التي يخرج منها أكثر عدد من الأسهم) إلى أقله كما هو موضح:

Trie.PNG
ثم الجزء الممتع نبدأ في التلوين بحيث نعطي في كل مرة لون من البداية ونبحث عن أول node غير مجاور (أي غير متصل) لنعطيه نفس اللون, لايمكن إعطاء نفس اللون لعنصرين متجاورين :
coloring.PNG

في البداية من p1 مروراً على p2: لا يمكن إعطائه ,p3: لايمكن ,p4: لايمكن,p5: نعم يمكن, من ثم نعود ل p2 ونقوم بنفس العملية ولا يمكن زيارة العناصر التي أُخذت مسبقاً لون ونكرر العملية إلى نهاية كل العناصر:
Final.PNG

وهنا خلصنا طلعت عندنا ثلاث مجموعات :
  • يمكن نقل p1 مع p5
  • يمكن نقل p2 مع p4
  • يمكن نقل p3 معp6
وبالتالي ثلاث مقطورات يمكن استعمال هذه الخوارزمية في حل العديد والكثير من المشاكل كوضع إشارات المرور , وضع جدول امتحانات , حتى أنه رح يعطيكم تكلفة أقل فمثلاً هذه الشركة لو استعملت أكثر من ثلاث مقطورات فرح تكون التكلفة أكثر ولا يمكن استخدام عدد أقل من عدد الألوان الذي نتج
ملاحظة: يوجد خطا بسيط فدرجة p4=2 ,p5=2,p6=1 ولكن الترتيب يبقى نفسه
وبالعافية عليكم
(++C)Source Code
3Colors.PNG
-حل التمرين نفس التمرين السابق بنفس المعطيات-
Color6.PNG
ملاحظة يرجى التاكد ان IDE المستعمل يتحمل استعمال الالوان
 

المرفقات

  • Graphe_Coloring.cpp
    7 KB · المشاهدات: 12
التعديل الأخير:

الظاهر تعبتوا بالمنشور
فالله يعطيكم الف عافية
و مبارك أول منشور لكم بالمنتدى 😁
 
  • Love
التفاعلات: Mina


لنفرض ان شركة مختصة في صنع محاليل كيمياىية مختلفة ولنفرض انها ستة مواد
(p1,p2,p3,p4,p5,p6)
يجب عليها ضمان نقل وتسليم هذه المحاليل عن طريق قطار بكميات ليست كبيرة ,تحذير!! هناك بعض المحاليل لا يجب ان تتواجد في نفس الشحنة مع محاليل اخرى
ضمانا للسلامة (فبعض المحاليل في حالة ملامستها مع محاليل اخرى ىقد تؤدي الى احتراق شديد او حتى انفجار )
فهذه قائمة المعطيات:
p1 لايجب ان ينقل معp, 2p3 اوp4
p2 لايجب ان ينقل مع1p,p3 اوp5
p3 لايجب ان ينقل مع1p,p2 اوp4
p5 لايجب ان ينقل مع 2p اوp6
فكم تحتاج الشركة من مقطورة لنقل هاذه المحاليل الستة?
فهنا يمككننا استعمال خوارزمية
coloring algorithm
واه زي اسمها ما بيوحي بتعتمد على التلوين
هيا خوارزمية كثير ممتعة ويمكن استعمالها في اي مشكل فيه
incompatibility او مايعرف بعدم التوافق فخلونا نحلها على بركة الله :
فهون ببساطة نرسم المواد الموجودة ونربط كل مادة مع المادة التي لا يجب ان تنقل معها مثلا p1 نربطها مع كل من p2,p3,p4 (و العلاقة p1 لا يجب ان تكون مع p2 هيا نفسها p2لا يجب ان كون معp1 فتمثل مرة واحدة )كما هوا موضح
مشاهدة المرفق 8058
ثم نرتبها على هاذا الشكل بحيث نبدا من اكبر node طالع منو اكثر عدد من الاسهم الى اقله كما هو موضح:


مشاهدة المرفق 8059
ثم الجزء الممتع نبدا في التلوين بحيث نعطي في كل مرة لون من البداية ونبحث عن اول nodeغير مجاور(اي غير متصل) لنعطيه نفس اللون لايمكن اعطاء نفس اللون لعنصرين متجاورين :مشاهدة المرفق 8060
ففبداية من p1 مرورا على p2:لا يمكن اعطائه ,p3: لايمكن ,p4:لايمكن,p5:نعم يمكن من ثم نعود ل p2 ونقوم بنفس العملية ولا يمكن زيارة العناصر التي اخذت مسبقا لون ونكرر العملية لحين نهاية كل العناصر:مشاهدة المرفق 8061
تيدادا ✨وهنا خلصنا طلعت عندنا ثلاث مجموعات اي يمكن نقل p1مع p5 وp2معp4 واخيرا p3معp6 وبالتالي ثلاث مقطورات
يمكن استعمال هذه الخوارزمية في حل العديد والكثير من المشاكل كوضع اشارات المرور , وضع جدول امتحانات , حتى انه رح يعطيكم تكلفة اقل فمثلا هاذه الشركة لو استعملت اكثر من ثلاث مقطورات فرح تكون التكلفة اكثر ولا يمكن استخدام عدد اقل من عدد الالوان الي نتج
ملاحظة: يوجد خطا بسيط فدرجة p4=2 ,p5=2,p6=1 ولكن الترتيب يبقى نفسه
وبالعافية عليكم
بارك الله فيكِ على هذا الطرح وهي خوارزمية فعلاً مهمة ولليوم العلماء يدرسوا فيها ههه
ننتظر جديدك بإذن الله
تحياتي
 

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

شكرا كتير على وقتك فعلان خورزمي ممتعه
 
  • Love
التفاعلات: Mina

بارك الله فيكِ على هذا الطرح وهي خوارزمية فعلاً مهمة ولليوم العلماء يدرسوا فيها ههه
ننتظر جديدك بإذن الله

بارك الله فيكِ على هذا الطرح وهي خوارزمية فعلاً مهمة ولليوم العلماء يدرسوا فيها ههه
ننتظر جديدك بإذن الله
تحياتي
وفيكم بارك الله
 
  • Love
التفاعلات: STORM

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

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

عودة
أعلى