الخوارزمية/التقريب لمجموعة مستقلة/مسافة مستقلة

Question

الإدخال: الرسم البياني G الإخراج: عدة مجموعات مستقلة ، بحيث تكون عضوية العقدة في جميع المجموعات المستقلة فريدة من نوعها. وبالتالي فإن العقدة لا تحتوي على اتصالات لأي عقدة في مجموعتها الخاصة. هنا مثال مسار.

منذ أن تم استدعاء التوضيح هنا إعادة الرحلة الأخرى:

قسّم رسم بياني معين إلى مجموعات بحيث

1. أستطيع أن أخبر عقدة من جميع الآخرين من خلال عضويتها في المجموعات على سبيل المثال ، إذا كانت العقدة I موجودة فقط في تعيين عقدة أخرى يجب أن تكون موجودة في تعيين A فقط

   إذا كانت العقدة J موجودة في المجموعة A و B ، فلا يجب أن تكون هناك عقدة أخرى في المجموعة A و B فقط. إذا تم ترميز عضوية العقد بواسطة نمط قليلاً ، فإن أنماط البت هذه لها مسافة هش على الأقل واحدة

2. إذا كانت العقدتان مجاورتان في الرسم البياني ، فلا ينبغي أن تكون موجودة في نفس المجموعة ، وبالتالي تكون مجموعة مستقلة

مثال: B ليس له عقد مجاورة d => a ، a => d

المحلول:

1. AB /
2. / BD

A Bit Pattern 10 ولا توجد عقدة مجاورة في مجموعتها. B له نمط بت 11 وليس العقدة المجاورة ، D لديه 01 لذلك جميع العقد لديها مسافة haming لا تقل عن 1 عقد لا توجد عقد مجاورة => صحيح

خطأ ، لأن D و A متصلون:

1. ADB
2. / ديسيبل

A HAS Bit Pattern 10 و D في مجموعته ، فهي مجاورة. B له نمط بت 11 ولا توجد عقدة مجاورة ، D لديها 11 كما لديها B ، لذلك هناك خطأان في هذا الحل وبالتالي لا يتم قبوله.

بالطبع يجب أن يمتد هذا إلى مجموعات أكثر مع زيادة عدد العقد في الرسم البياني ، حيث تحتاج على الأقل log(n) مجموعات.

لقد كتبت بالفعل تحولًا إلى Max-Sat ، لاستخدام حل SAT لهذا الغرض. لكن عدد الجمل هو فقط إلى حد كبير. سيكون النهج المباشر أكثر لطيفة. حتى الآن لدي تقريب ، لكني أرغب في حل دقيق أو على الأقل تقريبًا.

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

Answer 1

ليست إجابة كاملة ، ولا أعرف مدى فائدة ذلك لك. لكن هنا يذهب:

المسافة الهامينغ تضربني كرنجة حمراء. يقول بيان المشكل الخاص بك أنه يجب أن يكون على الأقل 1 ولكن قد يكون 1000. إنه يكفي أن نقول إن الترميز لتشفير عضوية كل عقدة فريد من نوعه.

إن بيان المشكل الخاص بك لا يتهجى ذلك ، لكن الحل الخاص بك أعلاه يشير إلى أن كل عقدة يجب أن تكون عضوًا في مجموعة واحدة على الأقل. بمعنى آخر. لا يُسمح بتشفير كل 0 قليلاً لعضوية أي عقدة.

تجاهل العقد المتصلة للحظة ، فإن العقد المفككة سهلة: ما عليك سوى ترقيمها بالتتابع مع ترميز بت غير مستخدم. حفظ هؤلاء لآخر.

يستخدم مثالك أعلاه الحواف الموجهة ، ولكن مرة أخرى ، والتي تثيرني كرنجة حمراء. إذا كان لا يمكن أن يكون A في نفس المجموعة مثل D لأن A => D ، لا يمكن أن يكون D في نفس المجموعة مثل ما إذا كان D => A.

ذكرت الحاجة إلى مجموعات سجل (N) على الأقل. سيكون لديك أيضا في معظم مجموعات n. سيتطلب رسم بياني متصل بالكامل (مع (N^2-N)/2 حواف غير موجهة) مجموعات N تحتوي على عقدة واحدة.

في الواقع ، إذا كان الرسم البياني الخاص بك يحتوي على بسيطة متصلة بالكامل من أبعاد M (M في 1..n-1) مع رؤوس M+1 و (M^2+M)/2 حواف غير موجهة ، ستتطلب على الأقل M+1 مجموعات.

في المثال الخاص بك أعلاه ، لديك واحد بسيط (M = 1) مع 2 رؤوس {A ، D} و 1 (غير موجه) EDGE {(A ، D)}.

يبدو أن مشكلتك تتلخص في العثور على أكبر Simplexes متصلة بالكامل في الرسم البياني الخاص بك. ذكرت بشكل مختلف ، لديك مشكلة في التوجيه: كم عدد الأبعاد التي تحتاجها لتوجيه حوافك حتى لا تقاطع أي شيء؟ لا يبدو مثل مشكلة قابلة للتطوير للغاية.

أول Simplex وجدت سهلة. تحصل كل عقدة قمة على مجموعة جديدة مع بتها.

العقد المفككة سهلة. بمجرد التعامل مع العقد المتصلة ، ما عليك سوى ترقيم العقد المنفصلة عن تخطي أي أنماط بت المستخدمة مسبقًا. من مثالك أعلاه ، نظرًا لأن A و D يستغرقان 01 و 10 ، فإن نمط البت التالي المتاح لـ B هو 11.

يصبح الجزء الصعب بعد ذلك كيفية طي أي Simplexes المتبقية قدر الإمكان في النطاق الحالي قبل إنشاء أي مجموعات جديدة مع أجزاء جديدة. عند الطي ، يجب أن يستخدم المرء 2 أو أكثر (مجموعات) لكل عقدة ، ويجب ألا تتقاطع البتات (مجموعات) مع البتات (مجموعات) لأي عقدة مجاورة.

ضع في اعتبارك ما يحدث لمثالك أعلاه عندما يضيف أحدهم عقدة أخرى ، C ، إلى المثال:

إذا كانت C متصلة مباشرة بكل من A و D ، فإن المشكلة الأولية تصبح إيجاد 2 simplex مع 3 رؤوس {A ، C ، D} و 3 حواف {(A ، C) ، (A ، D) ، (C ، D )}. بمجرد أن تأخذ A و C و D أنماط البت 001 و 010 و 100 ، فإن أدنى نمط بت متاح للتفكيك B هو 011.

إذا ، من ناحية أخرى ، C يربط C مباشرة أو D ولكن ليس كلاهما ، فإن الرسم البياني له اثنين من simplexes. لنفترض أننا نجد 1 simplex مع رؤى {a ، d} أولاً منحهم أنماط البت 01 و 10 ، ثم تصبح المشكلة كيفية طي c في هذا النطاق. نمط البت الوحيد مع ما لا يقل عن 2 بت هو 11 ، ولكن هذا يتقاطع مع أي عقدة C التي يتصل بها لذلك يتعين علينا إنشاء مجموعة جديدة ووضع C فيه. عند هذه النقطة ، يشبه الحل المذكور أعلاه.

إذا كان C مفككًا ، فسيحصل إما B أو C على نمط البت 11 وسيحتاج النموذج المتبقي إلى مجموعة جديدة والحصول على نمط بت 100.

لنفترض أن C يتصل بـ B ولكن ليس بـ A أو D. مرة أخرى ، يحتوي الرسم البياني على اثنين من simplexes ولكن هذه المرة مفككة. افترض أن {a ، d} موجود أولاً على النحو الوارد أعلاه مع إعطاء أنماط البت 10 و 01. يمكننا طي b أو c في النطاق الحالي. نمط البت الوحيد المتاح في النطاق هو 11 وإما أن يحصل B أو C على هذا النمط لأن أي منهما لا يكون مجاورًا لـ A أو D. بمجرد استخدام 11 مجموعة جديدة للعقدة المتبقية مما يعطيها نمط بت 100.

لنفترض أن C يتصل بجميع 3 A و B و D. في هذه الحالة ، يحتوي الرسم البياني على 2-simplex مع 3 قاطعات {a ، c ، d} و 1 simplex مع قمة 2 {b ، c}. المتابعة على النحو الوارد أعلاه ، بعد معالجة أكبر Simplex ، سيكون A و C و D أنماط بت 001 و 010 و 100. للطي في هذا النطاق ، فإن أنماط البت المتاحة مع مجموعة بتات أو أكثر هي: 011 ، 101 ، 110 ، 111. كل هذه باستثناء 101 تتقاطع مع C لذلك B سوف تحصل على نمط البت 101.

يصبح السؤال ثم: ما مدى كفاءة يمكنك العثور على أكبر Simplexes متصلة بالكامل؟

إذا كان العثور على أكبر Simplex أكبر مكلفًا للغاية, ، يمكن للمرء أن يضع الحد الأعلى التقريبي على البسيط المحتملة المتصلة بالكامل من خلال إيجاد الحد الأدنى القصوى من حيث الاتصالات:

1. اجتاح الحواف تحديث القمم مع عدد من حواف التوصيل.

2. لكل عقدة متصلة ، قم بإنشاء مجموعة من CN Tourts في البداية صفر حيث CN هو عدد الحواف المتصلة بالعقدة n.

3. اجتاح الحواف مرة أخرى ، للعقد المتصلة N1 و N2 ، زيادة العدد في N1 المقابلة لـ CN2 والعكس صحيح. إذا كان CN2> CN1 ، قم بتحديث العدد الأخير في صفيف N1 والعكس بالعكس.

4. اكتسح العقد المتصلة مرة أخرى ، يمكن أن يكون حساب الحد الأعلى على أكبر Simplex جزءًا من. يمكنك إنشاء مجموعة ثقب للحمام مع قائمة من القمم لكل حد أعلى أثناء اكتساح العقد.

5. اعمل من خلال صفيف ثقب الحمام من أكبر إلى أصغر العقد الاستخراج والطي في مجموعات فريدة من نوعها.

إذا كانت العقد الخاصة بك في مجموعة n وحوافك في مجموعة e ، فسيكون التعقيد: o (| n |+| e |+o (الخطوة 5))

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

Answer 2

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

إذا كانت هذه المشكلة مثل ما أفترض ، يمكن العثور على مجموعات مستقلة بواسطة هذه الخوارزمية: 1. قم بالبحث الأول في العمق على الرسم البياني الموجه ، حيث يتم اجتياز وقت الشجرة المتجذرة بواسطة هذه العقدة. 2. ثم عكس جميع الحواف في هذا الرسم البياني 3. قم بالبحث في DEPTH-FRIST مرة أخرى على الرسم البياني المعدل. يتم شرح الخوارزف بدقة بالكتاب "مقدمة في Alogrithm"