عدد المجموعات في المكوّن

https://stackoverflow.com/questions/1154565

18-09-2019
|

سؤال

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

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

النوع الوحيد من القيود التي يمكن استخدامها هو القواعد التي تنص على أنه إذا تم تحديد خيار واحد، فلا يمكن تحديد خيار آخر.

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

لقد اتخذت نهجا ساذجا لحل هذه المشكلة باستخدام مبدأ الشمول والاستبعاد.ولكن بقدر ما أستطيع أن أرى، أي خوارزمية تعتمد على هذه الطريقة يجب أن تعمل في O(2^n) والتي لن تنجح.هناك بالطبع العديد من التحسينات الممكنة التي من شأنها أن توفر أوقات تشغيل مناسبة ولكن لا تزال هناك سيناريوهات أسوأ الحالات يمكن إنشاؤها بسهولة.

هذا إلى حد كبير حيث أنا الآن.أي اقتراحات؟

تحديث

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

هناك عدة مجموعات مع الخيارات.يجب تحديد خيار واحد فقط في كل مجموعة.يمكن أن يكون هناك خيار واحد أو أكثر في المجموعة.

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

لذلك سيكون المثال:

مجموعة 1:
×1 ×2 ×3 ×4 ×5

المجموعة 2:
y1 y2 y3

المجموعة 3:
z1 z2 z3 z4

قيود:
x1 <-> y2 *
x1 <-> z4
y2 <-> z2

* إذا تم تحديد الخيار x1 في المجموعة 1، فلا يمكن تحديد الخيار y2 في المجموعة 2.

باستخدام الاستبعاد التضمين سأقوم بحساب عدد المجموعات كـ

مجموعات = ج_{لا قواعد} - ج_ص[1] - ج_ص[2] - ج_ص[3] + ج_ص[1،2] + ج_ص[1،3] + ج_ص[2،3] - ج_ص[1,2,3]

أين

ج_{لا قواعد} = 5 * 3 * 4

ج_ص[a,b,c] = عدد المجموعات التي تنتهك القاعدة a وb وc.

تتطلب الطريقة للأسف 2^| القواعد | العمليات الحسابية.

المحلول

حسنًا، لا يمكنني الالتفاف حول 2 ^ N، لكن يمكنني تقليل مجموعة العينات.للقيام بذلك، سنقوم بحساب "القيود المركبة".القيد المركب هو قيد، إذا تم تحديد جميع الخيارات الموجودة على الجانب الأيسر، فلا يمكن تحديد أي من الخيارات الموجودة على الجانب الأيمن، ولكن قد لا يتم تطبيق أي قيد آخر يعتمد على خيارات الجانب الأيسر.

نحن بحاجة إلى حساب مجموعة من جميع القيود المركبة الممكنة من مجموعة من القيود.على الرغم من أن ذلك ليس ضروريًا، إلا أننا "سنصلح" القيود الحالية عن طريق تبديل اليد اليسرى واليمنى إذا كانت مجموعة اليد اليمنى أصغر من مجموعة اليد اليسرى.قد يؤدي هذا إلى تقليل بعض القيود المركبة، على الرغم من إمكانية إجراء استدلالات أفضل للمبادلة.

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

تتبع الخوارزمية، لكنني لا أثبت أنها تحسب CCs بشكل صحيح.وسأثبت أنه إذا حدث ذلك، فيمكن استخدامها لحساب عدد المجموعات الممكنة.

ثبت القيود بحيث تكون مجموعة اليد اليسرى أقل من مجموعة اليد اليمنى أو تساويها.
تأليف القيود:
1. فرز القيود باليد اليسرى
2. على التوالي، لكل قيد:
  1. قم بطي القيد مع كل القيود التي تتبعه بنفس اليد اليسرى، مع الدوران x1 <-> y1, x1 <-> y2 ... x1 <-> yN داخل Set(x1) <-> Set(y1 ... yN)
  2. قم بتكوين القيد المطوي مع كل قيد مطوي بالفعل، إذا:
    - x1 ليس في اليد اليمنى للقيد المطوي بالفعل
    - x1 ليس في نفس المجموعة لأي عنصر في اليد اليسرى
  3. أضف القيد المطوي وكل تركيباته إلى مجموعة القيود المطوية
قم بحساب الحد الأدنى للمجموعة، وذلك عن طريق أخذ جميع الخيارات وإزالة الخيارات التي تظهر في اليد اليسرى للقيود الثابتة.

يمكنك الآن حساب عدد المجموعات باستخدام الصيغة أدناه.دعنا نسمي CC قيدًا مؤلفًا.ثم عدد المجموعات هو:

C(Mininum Set) + CCC1 + ... + CCCn

أين:

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

لاحظ أن التعبير مضاف بحت.وهذا يعني أنه لكي يؤدي هذا التعبير إلى النتيجة المتوقعة، يجب أن يتحقق الشرطان التاليان:

لا يجوز أن يحتوي أي مصطلحين منه على نفس المجموعة.
يجب أن يتم حساب كافة المجموعات بموجب هذه الشروط.
لا يجوز أن يتم إنتاج أي مجموعات غير صالحة بواسطة أي مصطلح.

بالنسبة للدليل الأول، لاحظ أنه لا يوجد CCs مختلفان بنفس اليد اليسرى.إذا كان لمجموعتين CC نفس اليد اليسرى ولكن اليد اليمنى مختلفة، فهذا يعني أن هناك قيد إضافة يجب أن ينطبق على أحد CCs، أو قيد غير صالح يتم تطبيقه على الآخر.

نظرًا لعدم وجود CCs بنفس اليد اليسرى، ولا يحتوي الحد الأدنى للمجموعة على اليد اليسرى لأي CC حسب التعريف، فيمكن تمييز أي CCs من خلال خيار واحد على الأقل يتم تحديده لأحدهما ولكن ليس للآخر .لذلك، لا يجوز لأي CCs أن تنتج نفس المجموعة.

بالنسبة للدليل الثاني، لاحظ أن مجموعة CCs تحتوي، بحكم التعريف، على جميع المجموعات الصالحة للخيارات الموجودة على اليد اليسرى.

افترض أن هناك مجموعة واحدة لا تظهر في الحد الأدنى من المجموعة ولا في مجموعة CCs.إذا كانت هذه المجموعة لا تحتوي على أي خيار أيسر، فيجب أن تكون مجموعة من الحد الأدنى، بحكم التعريف.ولذلك، يجب أن تحتوي على خيارات من اليد اليسرى.

نظرًا لأن مجموعة CCs تحتوي على جميع المجموعات الصالحة لليد اليسرى، فهناك CC واحدة بنفس خيارات اليد اليسرى.لذلك، يجب أن تحتوي هذه المجموعة على خيار غير مضمن في أي مجموعة خاصة بـ CC.لكن الخيارات الوحيدة غير المدرجة في CC هي تلك التي تظهر في اليد اليسرى للCCs الأخرى، وتلك التي يجب استبعادها منها عن طريق القيود.وبما أن الأمر قد لا يكون كذلك، فإن هذا الجمع لا يمكن أن يوجد.

بالنسبة للدليل الثالث، دعونا نفكر أولاً في الحد الأدنى للمجموعة.الحد الأدنى للمجموعة لا يحتوي على أي خيار في اليد اليسرى لأي مجموعة.نظرًا لأن جميع القيود تقع بين خيار واحد لليد اليسرى وآخر لليد اليمنى، فلا يوجد قيد ينطبق على الحد الأدنى للمجموعة.

الآن دعونا نفكر في CCs.لدى CC مجموعة صالحة من خيارات اليد اليسرى حسب التعريف.أي خيار غير متوافق مع تلك اليد اليسرى يجب أن يظهر في اليد اليمنى، ويجب إزالة أي خيار من تلك اليد اليمنى من الحد الأدنى للمجموعة.نظرًا لعدم وجود خيارات في الحد الأدنى المحدد حيث تكون غير متوافقة فيما بينها في البداية، فلا يمكن أن يكون هناك قيد غير مُرضي في أي مجموعة على CC.

وبهذا ينتهي الدليل.

دعونا نرى كيف ينطبق هذا مع مثال من التعليقات:

G1: x1, x2, x3 
G2: y1, y2 
G3: z1, z2, z3 

R1: x1 <-> y2 
R2: x3 <-> y2 
R3: y1 <-> z1 
R4: y2 <-> z2 
R5: y2 <-> z3

CC1: {x1} <-> {y2}
CC2: {x3} <-> {y2}
CC3: {y1} <-> {z1}
CC4: {x1, y1} <-> {y2, z1}
CC5: {x3, y1} <-> {y2, z1}
CC6: {y2} <-> {z2, z3}

دعونا نفكر بإيجاز في المجموعات المؤلفة غير الموجودة في القائمة:

R1&R2: {x1, x3} <-> {y2} -- not in the list because x1 and x3 belongs to the same
                            group
R1&R5: {x1, y2} <-> {y2} -- not in the list because the left hand of R2, y2
                            appears in the right hand of R1

الآن، دعونا نرى ما هي الخيارات الممكنة في كل مجموعة:

Minimum Set: (x2), (), (z1, z2, z3)    
CC1: (x1), (), (z1, z2, z3) -- replace G1 with x1, remove y2 from G2
CC2: (x3), (), (z1, z2, z3) -- replace G1 with x3, remove y2 from G2
CC3: (x2), (y1), (z2, z3)   -- replace G2 with y1, remove z1 from G3
CC4: (x1), (y1), (z2, z3)   -- replace G1 with x1, G2 with y1, remove y2 and z1
CC5: (x3), (y1), (z2, z3)   -- replace G1 with x3, G2 with y1, remove y2 and z1
CC6: (x2), (y2), (z1)       -- replace G2 with y2, remove z2 and z3 from G3

الآن، دعونا نضيف الأشياء:

C(Minimum Set) = 1 * 0 *3 = 0
CCC1 = 1 * 0 * 3 = 0
CCC2 = 1 * 0 * 3 = 0
CCC3 = 1 * 1 * 2 = 2
CCC4 = 1 * 1 * 2 = 2
CCC5 = 1 * 1 * 2 = 2
CCC6 = 1 * 1 * 1 = 1

C(Minimum Set) + CCC1 + CCC2  + CCC3 + CCC4 + CCC5 + CCC6
0              + 0    + 0     + 2    + 2    + 2    + 1    = 7

سأضيف فكرة أخرى هنا.على الرغم من وجود 6 شهادات أساسية أساسية فقط لـ 5 قواعد، أي أقل بكثير من 32 مصطلحًا متوقعًا بخلاف ذلك، يتم حساب هذه الالتزامات الأساسية المشتركة (CCCs) بأسوأ وقت يبلغ 2^N، لأنه بالنسبة لكل قاعدة، يجب عليك مقارنتها ودمجها مع جميع التزامات الالتزام الأساسية (CCC) التي تم إنشاؤها حتى الآن.قد تفكر فيها كأرقام ثنائية، حيث يتم تعيين البت إذا تم دمج القاعدة، ولا يتم تعيينها إذا لم يتم دمجها.

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

كما يوضح هذا المثال تحديدًا، يمكن أن يكون متوسط الوقت أفضل بكثير من 2^N.

الخوارزميات والاعتبارات البديلة

هناك بعض الحديث عن 2-SAT و3-SAT.يبدو لي أن هذه مشكلة 2-SAT، بمعنى أن كل قيد a <-> b هو في الواقع عبارة "!a || !b".لذلك يمكن كتابة جميع القيود معًا كـ "(!x1 || !y2) && (!x1 || !z4) && (!y2 && !z3)"، وما إلى ذلك.وهذا يعني أنه يمكنك "حلها". بمعنى أنه يمكنك معرفة ما إذا كان هناك تعيين منطقي لكل خيار من شأنه أن يحول هذا إلى حقيقة.توجد خوارزمية خطية لهذا الأمر من تأليف Aspall وPlass وTarjan، مع عرض تقديمي للشرائح هنا.

ولكن معرفة هل يمكن حل المعوقات أم لا ليس ما طلب.ما سئل هو رقم من الطرق التي يمكن من خلالها ضبط جميع الخيارات مع الحفاظ على حقيقة مشكلة 2-SAT.

توجد الآن خوارزميات فعالة لحساب عدد الطرق لحل مسألة 2-SAT.على سبيل المثال، هذه الورقة يقدم خوارزمية تعمل في 1.2561^ن.لكن حتى هذا لن يساعدنا، كما نحتاج أن نعرف ماذا يجب أن تكون الحلول قادرة على حساب عدد المجموعات التي تلبي هذا الحل.

وفقا لويكيبيديا، هذه الورقة لديه خوارزمية تعداد جميع الحلول بكفاءة، وهذا ما نريده.ولكن إذا كان العد أسيًا بالفعل، فسيكون التعداد كذلك.أفضل من 2^ن, ربما، ولكن لا يزال الأسي.

إذا قمنا بتعداد جميع الحلول لمشكلة 2-SAT، فسيتم إعطاء عدد المجموعات لكل مجموعة بـ 1 مضروبًا في عدد الخيارات المجانية، وهي الخيارات التي لا تظهر في أي قيد، لكل مجموعة لم يتم تحديد خيار لها بالحل.

على سبيل المثال، أخذ المجموعة السابقة من المجموعات والقيود.مشكلة 2-SAT، بما في ذلك الاستبعاد المتبادل، هي:

(! x1 ||! y2) && (! x3 ||! y2) && (! y1 ||! z1) && (! y2 ||! z2) && (! y2 ||! z3) && (! x1 || ! x3) && (! y1 ||! y2) && (! z1 ||! z2) && (! z1 ||

السطر الأول هو القواعد الخمس.السطر الثاني هو الاستبعاد المتبادل لجميع الخيارات في نفس المجموعة التي تظهر في قواعد القيد.

حلول مشاكل 2-SAT هي:

x1    x3    y1    y2    z1    z2    z3    Combinations
true  false true  false false true  false 1
true  false true  false false false true  1
true  false true  false false false false 0
true  false false false true  false false 0
true  false false false false true  false 0
true  false false false false false true  0
true  false false false false false false 0
false true  true  false false true  false 1
false true  true  false false false true  1
false true  true  false false false false 0
false true  false false true  false false 0
false true  false false false true  false 0
false true  false false false false true  0
false true  false false false false false 0
false false true  false false true  false 1
false false true  false false false true  1
false false true  false false false false 0
false false false true  true  false false 1
false false false true  false false false 0
false false false false true  false false 0
false false false false false true  false 0
false false false false false false true  0
false false false false false false false 0

في الحلين الأولين، لا توجد مجموعات بدون خيار محدد، وبالتالي فإن عدد المجموعات هو 1.الحل الثالث ليس له خيار محدد للمجموعة G3، لذلك نضرب 1 في 0.في السطور التي تبدأ بـ "false false"، لا يوجد خيار محدد للمجموعة G1، وخيار واحد مجاني:×2.لذلك نضربهم بـ 1 في 1، وفي 0 إذا لم يكن هناك خيار محدد لـ G2 أو G3 (وفي هذه الحالة يكون عدد الخيارات المجانية 0).

الآن، هناك سؤال حول كيفية فرض خيار واحد يتم اختياره في كل مجموعة وما زلت أدعي أنه 2-SAT.المشكلة، كما ذكرنا، لها قيدين ضمنيين:لكل مجموعة، يجب أن يكون هناك خيار واحد فقط محدد.يمكن كتابة هذين القيدين على النحو التالي:

س₁ || x₂ || x₃ (للمجموعة x مع الخيارات x₁ ..س₃)
(!x₁ || ! x₂) && (!x₁ || ! x₃) && (!x₂ || ! x₃)

القيد الأخير هو 2-SAT، والقيد الأول هو 3-SAT لأي حالة غير تافهة.وفي الواقع، أنا لا أفرض القيد الأول، ولكن يصبح العدد بعد ذلك 0.يجب أن تسير خوارزمية العد على النحو التالي:

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

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

يبدو هذا وكأنه غش في المشكلة من خلال قيد صالح> 2-SAT.بعد كل شيء، إذا كان هذا ممكنًا، فيمكن حل مشكلة 3-SAT فقط عن طريق تعداد الحلول للجزء 2-SAT منها، ثم التخلص من كل حل لا يفي بالجزء 3-SAT منه.للأسف، هناك اختلاف أساسي واحد يمكنني تحديده:

جميع المسندات التي لم يتم حلها بواسطة الجزء 2-SAT من المشكلة خالية من أي قيود أخرى.

بالنظر إلى هذا القيد المقيد إلى حد ما على البنود، يمكننا حل هذه المشكلة عن طريق تعداد الحلول للقيود الصريحة 2-SAT.

إذا كان أي شخص يريد متابعة هذا الأمر أبعد من ذلك، فليمضي قدمًا.أنا راضٍ عن التحسن في 2^ن الحل الذي اقترحته.

نصائح أخرى

اذا كنت تمتلك N مجموعات الخيارات، كل مع Xi والخيارات (0<=i<N) ومن بعد

X0*X1*...*X(N-1)

يمنحك الإجابة التي تريدها. بمعنى آخر، اضرب حجم كل مجموعة من الخيارات.

اذا كنت تمتلك n المعلمات مع Ci القيم المحتملة لكل معلمة و m القيود، الحد العلوي لعدد التكوينات هو ما يلي (تجاهل القيود).

N0 = C1 * C2 * ... * Cn

عائق واحد من النموذج ci == x => cj != y لا يذكر العدد التالي من التكوينات.

        N
Dk = -------
     Ci * Cj

وبالتالي يتم الحصول على عدد التكوين عن طريق طرح التكوينات غير المسموح بها من العلوي الملزم تجاهل القيود.

N = prod(Ci, i = 1...n) * (1 - sum(1 / (Cxj * Cyj), j = 1...m))

هنا xj و yj هي كلا مؤشرات المعلمة من jالقيد.

مثال

Parameters    n = 4

Parameter 1   C1 = 4   0 1 2 3 
Parameter 2   C2 = 3   4 5 6 
Parameter 3   C3 = 2   X Y
Parameter 4   C4 = 3   7 8 9

Constraints   m = 2

Constraint 1  c2 == 4 => c3 != X
Constraint 2  c3 == X => c4 != 9

N0 = 4 * 3 * 2 * 3 = 72

D1 = 72 / (3 * 2) = 12
D2 = 72 / (2 * 3) = 12

N = 72 - (12 + 12) = 48

تحديث

أعتقد أن هذا ليس صحيحا بعد تماما لأنه لا يمثل تبعا من القيود.

~~لا توجد اختصارات هنا للحالة العامة.~~ انها ليست سيئة كما تظن. انظر "إعادة التفكير" أدناه.

هو 2 ^ ن حقا سيئة للغاية؟ كم عدد قواعد الاستبعاد التي نتحدث عنها هنا؟ عليك حقا القيام بذلك مرة واحدة فقط لكل Confecturator، ما لم تتغير مجموعة القواعد / الخيارات باستمرار على الطيران وتتطلب إعادة الحساب الديناميكي. إذا كان هناك بالفعل عدد كبير من القواعد، فلن أبحث عن حل دقيق - فلا فكر فقط بين تقاطعات طلب KTH وقل "عدد المجموعات على الأقل / أكثر ...". قد تكون هناك طرق غربال أخرى ستتيح لك استخلاص الحدود بسرعة على الإجابة.

ضع أيضا في الاعتبار: إذا كنت تنظر فقط في الاستثناءات التي تحتاجها فعليا، فإن 2 ^ n هي مجرد حد كبير، وقد يكون عدد العمليات الفعلية الخاصة بك أقل بكثير لأي سيناريوهات فعلية. وهذا هو، إذا كان C [1،2] صفر، فذلك هو C [1،2، ...]. النظر في هذا: لكل قيد، مجموعات "مجموعات" من القيود معا إذا كانوا يشاركون أي خيارات مشتركة. من الواضح أن وقت التشغيل الحقيقي الخاص بك سيتم تعريفه بحجم أكبر "clump" (الذي، نعم، قد يكون كبيرا مثل n).

إعادة التفكير: C [X، Y] سيكون صفر عظم حالات. يمكن أن يتداخل القيد إلا مع القيود الأخرى التي تنطوي على مختلف مجموعة. بمعنى آخر، (X1 <-> y1) يمكن أن تتداخل فقط مع (x1 <-> z1) أو (y1 <-> z2) أو أي شيء، وليس (x1 <-> y2). وبالمثل، يمكن أن تتداخل مجموعة من القيود إلا مع مجموعة جديدة: مزيج من (X1 <-> Y1) مع (Y1 <- z2) لا يوجد لديه تفاعل مع (x3 <-> z2) (تم إصلاح مجموعة X بالفعل في X1). يجب عليك فقط التفكير في إدراج / الاستبعاد حيث تضيف كل قاعدة تضيفها إلى المجموعة مجموعة غير مسقط مسبقا إلى المزيج. لذلك أنت في الواقع O (2^جيم)، حيث G هو عدد المجموعات (وربما أيضا ملزمة مختلفة بناء على حجم المجموعات). أكثر قابلية للإدارة!

تعديل

هذه الخوارزمية غير صحيحة. لقد قدمت إجابة بديلة في منشور آخر لا يزال 2 ^ ن في الحالة الأسوأ، ولكن قد يعطي نتائج أفضل وإلا.

يعمل هذا واحد في المثال الذي تختاره لأن Y2 جزء من مجموعة الاستبعاد من X1، ويستند المقيدان الأولان على X1. ومع ذلك، أرى الآن ما يجب القيام به. لا يزال قريبا من 2 ^ n، ولكن هناك تحسينات يمكن أن تؤدي إلى مكاسب كبيرة.

لإصلاح هذه الخوارزمية، يجب أن تكون القواعد المكونة من مجموعة النموذج (OX) <-> تعيين (OY). لتكوينها، لكل تقييد مع الثور اليد اليسرى، يمكنك أيضا إنشاء تركيبات أخرى لها مع كل قاعدة تتكون بالفعل، إذا لم يكن الثور جزءا من الجانب الأيمن من القاعدة المكونة، فهو المجموعة هي نفسها الجانب الأيسر من المجموعة.

لقيود مستقلة تماما، هذا هو 2 ^ n. خلاف ذلك، أنت تقلل من N من خلال:

موحد يقيد مع اليد اليسرى المشتركة
لا تحكم مجموعات القاعدة التي هي حصرية متبادلة، وهذا منقسم في:
- عدم الجمع بين قواعد الخيارات في نفس المجموعة
- عدم الجمع بين القواعد التي يظهر الجانب الأيسر من المرء على الجانب الأيمن من الآخر

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

End Edit.

دعونا ندرج هذا حولها. ماذا عن هذا لخلع الخوارزمية:

إصلاح القواعد حسب الضرورة للتأكد من أن القاعدة o1 <-> o2, group(o1) < group(o2)
حساب القواعد "المكونة" عن طريق قابلة للطي جميع القواعد oX <-> o? في قاعدة واحدة oX <-> Set(o?)
حساب مجموعة "نظيفة" من المجموعات عن طريق إزالة منهم الخيار الأيسر لكل قاعدة
حساب مجموعات بديلة من المجموعة النظيفة، واحدة لكل قاعدة مكونة، عن طريق استبدال مجموعة الخيار الأيسر مع الخيار الأيسر نفسه، والطرح من المجموعات الأخرى خيارات اليد اليمنى للقاعدة.
لكل مجموعة من المجموعات، حساب عدد المجموعات بضرب عدد الخيارات في كل مجموعة في المجموعة.
أضف جميع النتائج من الخطوة 5.

دعونا نرى هذا في العمل:

Group 1:
x1 x2 x3 x4 x5

Group 2:
y1 y2 y3

Group 3:
z1 z2 z3 z4

Constraints (already fixed):
x1 <-> y2 *
x1 <-> z4
y2 <-> z2

Composed rules:
x1 <-> (y2, z4)
y2 <-> (z2)

Clean set of groups:
x2x3x4x5, y1y3, z1z2z3z4

Alternate sets:
x1, y1y3, z1z2z3 (first composed rule)
x2x3x4x5, y2, z1z3z4 (second composed rule)

Totals:
4 * 2 * 4 = 32
1 * 2 * 3 = 6
4 * 1 * 3 = 12

Total: 50

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

c(no rules) = 60
c1 => 4
c2 => 3
c3 => 5
c12 => 1
c13 => 1
c23 => 0
c123 => 0

c(no rules) - c1 - c2 - c3 + c12 + c13 + c23 - c123 = 50

إذا كانت خوارزمية صحيحة، يبدو أنها كثير الحدود. مرة أخرى، الآن لا أستطيع التفكير بوضوح بما فيه الكفاية، وسأحتاج إلى النظر في Big-O من التلاعب في المجموعات.

فيما يلي تنفيذ Scala لذلك:

case class GroupOption(id: Int, option: Int)
case class Group(id: Int, options: Set[Int])
case class Rule(op1: GroupOption, op2: GroupOption)
case class ComposedRule(op: GroupOption, set: Set[GroupOption])

object ComputeCombinations {
  def fixRules(rules: Set[Rule]) = {
    rules map (rule => if (rule.op1.id > rule.op2.id) Rule(rule.op2, rule.op1) else rule)
  }

  def ruledOptions(id: Int, rules: Set[Rule]): Set[Int] = (
    rules 
    filter (rule => rule.op1.id == id)
    map (rule => rule.op1.option)
  )

  def cleanseSet(groups: Set[Group], rules: Set[Rule]) = {
    groups map (group => 
      Group(group.id, group.options -- ruledOptions(group.id, rules)))
  }

  def composeRules(rules: Set[Rule]): Set[ComposedRule] = Set(
    (
      rules.toList
      sort (_.op1.id < _.op1.id)
      foldLeft (List[ComposedRule]())
      ) { (list, rule) => list match {
        case ComposedRule(option, set) :: tail if option == rule.op1 =>
          ComposedRule(option, set + rule.op2) :: tail
        case _ => ComposedRule(rule.op1, Set(rule.op2)) :: list
      }} : _*
  )

  def subset(groups: Set[Group], composedRule: ComposedRule) = (
    groups
    filter (_.id != composedRule.op.id)
    map (group => Group(group.id, group.options -- 
                                  (composedRule.set 
                                   filter (_.id == group.id)
                                   map (_.option)
                                  )))
  )

  def subsets(groups: Set[Group], composedRules: Set[ComposedRule]) = (
    composedRules map (composedRule => subset(groups, composedRule))
  )

  def combinations(groups: Set[Group]) = (
    groups.toList map (_.options.size) reduceLeft (_*_)
  )

  def allCombinations(groups: Set[Group], rules: Set[Rule]) = {
    val fixedRules = fixRules(rules)
    val composedRules = composeRules(fixedRules)
    val cleanSet = cleanseSet(groups, fixedRules)
    val otherSets = subsets(cleanSet, composedRules)
    val allSets = otherSets + cleanSet
    val totalCombinations = allSets.toList map (set => combinations(set)) reduceLeft (_+_)
    totalCombinations
  }
}

object TestCombinations {
  val groups = Set(Group(1, Set(1, 2, 3, 4, 5)),
                   Group(2, Set(1, 2, 3)),
                   Group(3, Set(1, 2, 3, 4)))
  val rules = Set(Rule(GroupOption(1, 1), GroupOption(2, 2)),
                  Rule(GroupOption(1, 1), GroupOption(3, 4)),
                  Rule(GroupOption(2, 2), GroupOption(3, 2)))
  def test = ComputeCombinations.allCombinations(groups, rules)
}

قد لا يكون هذا إجابة مفيدة مباشرة، لذلك لا تتردد في تجاهلها ... ومع ذلك؛ أنا أعمل حاليا نظاما مماثلا بنفسي؛ وبصراحة بخلاف أمثلة تافهة لست متأكدا من أنه من المفيد محاولة حساب عدد المجموعات الصحيحة. كمثال، تكون النماذج التي أعمل فيها في الوقت الحالي (على سبيل المثال) 18000 عنصر مرشح نشر أكثر من 80 اختيارا، وبعضها اختيار / بعض متعدد المحدد. وراء أصغر النماذج، لا يوجد المنفعة في معرفة الرقم، كما تفعل ببساطة أبدا كتابة ذلك كجدول حقيقي بالكامل؛ أنت جميلة كثيرا قسري لتشغيل القواعد (أي إزالة أي شيء لم يعد صالحا، حدد أي شيء تلقائي حسب الاقتضاء، وتحقق من عدم كسر أي قواعد) عند الطلب. التي ليست بالضرورة مشكلة؛ يعالج الرمز الحالي الخاص بي هذا النموذج (كخدمة ويب) في ~ 450ms، ومعظم ذلك هو في الواقع الوقت الذي يقضيه في معالجة XML للإدخال / الإخراج. إذا لم يكن الإدخال / الإخراج XML، أعتقد أنه سيكون ~ 150 مللي ثانية، وهو رائع.

أحب إقناع صاحب العمل بفتح المصدر؛ هذه معركة ليوم آخر، رغم ذلك.

لن يكون فقط x ^ n، حيث n هو عدد الخيارات و x هو عدد الخيارات لكل خيار؟

أعتقد أن ZAC يفكر في الاتجاه الصحيح. بالنظر إلى تعبيرك عن عدد المجموعات، فإنك ترى أن شروط الترتيب الثاني كروية [i، j] أصغر بكثير من شروط C [K]. تخيل مكعب حيث كل محور هو مجموعة من الخيارات. كل نقطة في المكعب يمثل مزيج معين من الخيارات. الترتيب الأول C [K] تصحيح يستبعد خط الخيارات بين سطوحين للمكعب. يحدث تصحيح الترتيب الثاني C [I، J] فقط عندما تلتقي سطران من هذا القبيل عند نقطة واحدة (مزيج من الخيارات) في الفضاء في المكعب. لذلك بغض النظر عن عدد المجموعات التي لديك، فإن تصحيحات الترتيب العالي هي دائما أصغر بشكل متزايد. إذا التمسك

مجموعات = ج (لا توجد قواعد) - CR [1] - CR [2] - CR [3

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

معلق وظيفة دانيال:

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

على سبيل المثال، النظر في هذه الحالة:

Group 1:
a1 a2 a3 a4 a5

Group 2:
b1 b2 b3

Group 3:
c1 c2 c3 c4

Group 4:
d1 d2 d3 d4 d5

Rules:
a1 <-> b2
a1 <-> c2
b2 <-> c2
b2 <-> d1
a2 <-> d2

لقد قمت بتكوين خوارزمية غربال الأساسية الخاصة بي مع هذا التكوين وحصلت على النتائج التالية (227 مجموعات):

بدون قواعد => 300 القواعد: [1] => 20 القواعد: [2] => 15 القواعد: [3] => 25 القواعد: [4] => 20 القواعد: [5] => 12 طلب: 1 => 1 => 1 => 1 => 208 (DIFF: -92) القواعد: [1، 2] => 5 القواعد: [1، 3] => 5 القواعد: [2، 3] => 5 القواعد: [1، 4] => 4 القواعد: [ 2، 4] => 1 قواعد: [3، 4] => 5 القواعد: [1، 5] => 0 القواعد: [2، 5] => 0 القواعد: [3، 5] => 1 القواعد: [ 4، 5] => 0 الترتيب: 2 => 234 (فرق: 26) القواعد: [1، 2، 3] => 5 القواعد: [1، 2، 4] => 1 القواعد: [1، 3، 4 ] => 1 قواعد: [2، 3، 4] => 1 القواعد: [1، 2، 5] => 0 القواعد: [1، 3، 5] => 0 القواعد: [2، 3، 5] > 0 القواعد: [1، 4، 5] => 0 القواعد: [2، 4، 5] => 0 القواعد: [3، 4، 5] => 0 الترتيب: 3 => 226 (diff: -8) القواعد: [1، 2، 3، 4] => 1 القواعد: [1، 2، 3، 5] => 0 القواعد: [1، 2، 4، 5] => 0 القواعد: [1، 3، 4 ، 5] => 0 القواعد: [2، 3، 4، 5] = * 0 الترتيب: 4 => 227 (فرق: 1) القواعد: [1، 2، 3، 4، 5] = 0 الترتيب: 5 => 227 (فرق: 0) *** مجموعات: 227 ***

ومع ذلك باستخدام هذا الرمز في Scala:

 مجموعات VAL = SET (مجموعة (1، تعيين (1، 2، 3، 4، 5))، المجموعة (2، مجموعة (1، 2، 3))، المجموعة (3، تعيين (1، 2، 3، 4 ))، المجموعة (4، تعيين (1، 2، 3، 3، 4، 5))) VAL قواعد = مجموعة (القاعدة (GroupOption (1، 1)، groupoption (2، 2))، القاعدة (groupoption (1، 1 )، groupoption (3، 2))، القاعدة (groupoption (2، 2)، groupoption (3، 2))، القاعدة (groupoption (2، 2)، groupoption (4، 1))، القاعدة (groupoption (1، 2)، groupoption (4، 2)))

حصلت على الجواب 258.

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

مشكلتك غير صالحة إلى حد ما.

عد عدد الحلول غير كاملة، حتى لو قمت بتقييد كل مجموعة من الأشعة الراديو إلى خيارين
التحقق مما إذا كان هناك أي خيار للخيارات المستمرة مع القيود كاملة
التحقق مما إذا كان هناك أي خيار من الخيارات المتسقة مع القيود يمكن أن يتم بسرعة كبيرة، إذا قمت بتقييد كل مجموعة من الأشعة الراديو إلى خيارين (2SAT)

لذلك بشكل عام لا تحسب في خوارزمية متعددة الحدود؛ إن وجود هذه الخوارزميات سوف يعني P = NP.

ما تستطيع فعله:

استخدم خوارزمية تقريبية. وفقا لمقال Wikipedia الذي ربطته، فهي غالبا ما تكون معتمونة لهم.
استخدام SAT SLEVER http://en.wikipedia.org/wiki/sat_solver. أو أداة ذات صلة للعد (للأسف لا أعرف أي)؛ أنشأ الناس العديد من الاستدلال وأن البرامج ستكون بشكل عام أسرع بكثير من الحل الخاص بك محلية الصنع. حتى هناك مسابقات SAT، لذلك يتوسع هذا الحقل سريعا جدا.
تحقق مما إذا كنت بحاجة إلى هذه العمال. ربما مشكلتك لديها افتراضات إضافية، وهذا سيغير تعقيده.

البراهين:

يعتبر حساب عدد الحلول بسهولة #P، لذلك يكفي الحد من 2SAT إلى هذا. تأخذ بعض 2sat مثيل، مثل

(p1 أم لا p2) و (p2 أم لا p3)

اسمح للمستخدم باختيار قيم P1، P2، P3. يمكنك بسهولة تكوين القيود التي ستجبر هذا على أن تكون قابلة للحل. لذلك عدد التكوينات المحتملة = عدد المهام المحتملة ل P1، P2، P3 جعل الصيغة المنطقية صحيحة.

يمكنك بسهولة التحقق من ذلك ما إذا كان هناك بعض الخيارات المسموح بها أم لا، لذلك هذا هو NP، لذلك يكفي الحد من 3SAT لهذا. خذ بعض مثيل 3SAT، مثل

(p1 أو p2 أم لا p3) و (p2 أم لا p1 أو p4)

إعطاء الخيارات:

المجموعة P1. p1true p1false.

مجموعة P2. P2FALSE P2TRUE.

مجموعة P3. P3FALSE P3TRUE.

مجموعة P4. P4FALSE P4TRUE.

مجموعة جماعية_1. C1A C1B C1C.

مجموعة جماعية_2. C2A C2B C2C.

سيتم التحكم في Clause_1 بالبند الأول: (p1 أو p2 أو ليس p3). على وجه التحديد، ستكون C1A قابلة للتحقق إذا تم اختيار P1True، وسوف تكون C1B قابلة للتحقق إذا تم اختيار P2True، فستكون C1C قابلة للتحقق إذا تم اختيار P3FALSE. لذلك القيود هي:

P1FALSE <-> C1A

P2FALSE <-> C1B

P3TRUE <-> C1C

نفسه مع Cluse_2، القنادسين

P2FALSE <-> C2A

P1True <-> C2B

P4FALSE <-> C2C

إذا كان المستخدم قادرا على اختيار جميع الإجابات (حتى يكون عدد التكوينات> 0)، فسيثبت أن هناك بعض تقييم المتغيرات P1، ...، P4 الذي يجعل مثيل 3SAT صحيحا. وعلى العكس، إذا لن يتمكن المستخدم من اختيار الإجابات المتسقة مع الافتراضات (عدد التكوينات المتاحة = 0)، فلن يكون مثيل 3SAT. لذلك معرفة ما إذا كانت الإجابة> 0 تعني معرفة ما إذا كانت مثيل 3SAT قابل للحل.

بالطبع هذا التخفيض هو وقت متعدد الحدود. نهاية الإثبات.

إذا لم تكن راضيا عن حقيقة أن الإجابة قد تكون 0: لا يزال من الصعب NP إذا تجاهل مثل هذا التكوين. (ستضيف بعض خيار "وهمية" لجميع المجموعات والسماح بخيارات كثيرة للعديد من الخيارات إذا لم يتم اختيار "Bogus". هذا أكثر تعقيدا لشرح، لذلك سأفعل ذلك عند الطلب.)

تم ذكر ذلك لفترة وجيزة في إجابة SDCVVC الممتازة أعلاه، ولكن قد يكون تقريب مونت كارلو جيدا بما فيه الكفاية؟ قم بإنشاء تكوينات عشوائية N (حيث يتم اختيار N بحيث تكون قوة تجربتك مرتفعة بما فيه الكفاية: لا أعرف ما يكفي لمساعدتك هنا)، ثم اختبار عدد قليل منهم متوافقين مع قيودك. استقراء تتناسب مع بقية مساحة التكوين الخاصة بك.

مرخصة بموجب: CC-BY-SA مع الإسناد

لا تنتمي إلى StackOverflow