المشكلة زمرة تصميم خوارزمية

Question

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

الإصدار 1

المدخلات:الرسم البياني ممثلة في مجموعة A[0,...n-1], حجم k من بياني ثانوي العثور عليها.

الإخراج:صحيح إذا بياني ثانوي موجود كاذبة وإلا

خوارزمية (في بايثون مثل شبة الكود):

def clique(A, k):
    P = A x A x A //Cartesian product
    for tuple in P:
        if connected(tuple):
            return true
    return false

def connected(tuple):
    unconnected = tuple
    for vertex in tuple:
        for test_vertex in unconnected:
            if vertex is linked to test_vertex:
                remove test_vertex from unconnected
    if unconnected is empty:
        return true
    else:
        return false

الإصدار 2

المدخلات:تقارب مصفوفة حجمها n من n و k حجم بياني ثانوي للعثور على

الإخراج:كل كاملة subgraphs في الحجم k.

خوارزمية (في هذا الوقت وظيفية/بيثون شبة الكود):

//Base case:  return all vertices in a list since each
//one is a 1-clique
def clique(A, 1):
    S = new list
    for i in range(0 to n-1):
        add i to S
    return S

//Get a tuple representing all the cliques where
//k = k - 1, then find any cliques for k
def clique(A,k):
    C = clique(A, k-1)
    S = new list
    for tuple in C:
        for i in range(0 to n-1):
            //make sure the ith vertex is linked to each
            //vertex in tuple
            for j in tuple:
                if A[i,j] != 1:
                    break
            //This means that vertex i makes a clique
            if j is the last element:
                newtuple = (i | tuple) //make a new tuple with i added
                add newtuple to S
    //Return the list of k-cliques
    return S

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

الإصدار 3

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

المدخلات:الرسم البياني G = (V,E), حجم زمرة أن تجد k

الإخراج:صحيح إذا زمرة موجود كاذبة وإلا

خوارزمية:

1. العثور على المنتج الديكارتي V^k.
2. لكل tuple في نتيجة اختبار ما إذا كان كل قمة توصيل كل أخرى.إذا تم توصيل جميع, العودة الحقيقية والخروج.
3. Return false والخروج.

التحديث:تم إضافة الإصدار الثاني.أعتقد أن هذا هو الحصول على أفضل على الرغم من أنني لم أضيف أي يتوهم البرمجة الديناميكية (علمي).

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

Answer 1

بعض التعليقات:

• تحتاج فقط إلى النظر في n-اختيار-k مجموعات من القمم ، ليس كل k-الصفوف (ن^k منهم).
• connected(tuple) لا يبدو الحق.لا تحتاج إلى إعادة تعيين unconnected داخل الحلقة ؟
• كما اقترح آخرون ، هناك طرق أفضل من مجبرا هذا.النظر في المسائل التالية العودية العلاقة:A (k+1)-بياني ثانوي هو زمرة إذا كان أول ك القمم تشكيل عصبة الرأس (k+1) بجوار كل من أول ك القمم.يمكنك تطبيق هذا في اتجاهين:
  • تبدأ مع 1-زمرة والتوسع التدريجي في زمرة حتى تحصل على الحجم المطلوب.على سبيل المثال ، إذا م هو أكبر قمة في زمرة الحالية ، في محاولة لإضافة vertex {m+1, m+2, ..., n-1} على زمرة وهذا هو قمة واحدة أكبر.(هذا هو مماثل العمق أولا اجتياز شجرة ، شجرة العقدة هي القمم أكبر من أكبر قمة في زمرة الحالية.)
  • تبدأ مع بياني ثانوي من الحجم المطلوب و تحقق مما إذا كانت زمرة باستخدام العودية العلاقة.إعداد التحفيظ الجدول لتخزين النتائج على طول الطريق.
• (تنفيذ اقتراح) استخدام مصفوفة الجوار (0-1) لتمثيل حواف في الرسم البياني.
• (الأولي التقليم) رمي بعيدا كل القمم مع درجة أقل من ك.

Answer 2

أنا مرة تنفيذ خوارزمية إيجاد جميع القصوى الزمر في الرسم البياني ، وهي مشكلة مماثلة ليدكم.الطريقة التي فعلت ذلك كان على أساس هذه الورقة: http://portal.acm.org/citation.cfm?doid=362342.362367 - أنه وصف التراجع الحلول التي وجدتها مفيدة جدا كدليل على الرغم من أنني غيرت الكثير جدا من هذه الورقة.كنت في حاجة الى الاشتراك للحصول على ذلك ولكن أفترض الجامعة سيكون متاح.

شيء واحد حول هذا الورق على الرغم من أنني أعتقد أنهم يجب أن يكون اسم "لا" "بالفعل تعتبر مجموعة" لأنها مربكة جدا على خلاف ذلك.

Answer 3

الخوارزمية "لكل ك-tuple من القمم ، إذا زمرة ، ثم العودة الحقيقية" يعمل بالتأكيد.ومع ذلك ، فإنه من القوة الغاشمة التي ربما لا ما خوارزميات الحال هو البحث عن.بدلا من ذلك يجب مراعاة ما يلي:

1. كل vertex هو 1-زمرة.
2. مقابل كل 1-زمرة كل vertex أن يصل إلى الذروة في 1-زمرة يساهم في 2-زمرة.
3. كل 2-زمرة كل vertex أن يربط كل قمة في 2-زمرة يساهم في 3-زمرة.
4. ...
5. لكل (ك-1)-زمرة كل vertex أن يربط كل قمة في (ك-1) زمرة يساهم في k-زمرة.

هذه الفكرة قد تؤدي إلى أفضل نهج.

Answer 4

ربما في محاولة البرمجة الديناميكية تقنية.

Answer 5

إنه لأمر مدهش ما تكتب الأمور كما سؤال سوف تظهر لك حول ما كنت قد كتبت للتو.هذا السطر:

P = A x A x A  //Cartesian product

يجب أن يكون هذا:

P = A ^k //الديكارتي المنتج

ماذا تعني A^k ؟ هل أنت مع مصفوفة المنتجات ؟ إذا كان الأمر كذلك ، هو مصفوفة الجوار (قلت أنها مجموعة من n+1 العناصر)?

في setbuilder التدوين ، فإنها تبدو شيئا مثل هذا:

P = {(x0, x1, ...xk) | x0 ∈ A 1 x ∈ A ...و xk ∈ A}

انها في الاساس مجرد منتج الديكارتي من أخذ k مرات.على الورق كتبته ك كونه مرتفع من (أنا الآن فقط عرفت كيف تفعل ذلك عن طريق تخفيض السعر).

بالإضافة إلى مجرد مجموعة من كل vertex دون مراعاة الجوار.