هل هذا البديل من مشكلة مجموع المجموعة الفرعية أسهل في حلها؟

Question

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

بالنظر إلى قيمة V ، وحجم محدد L ، وتسلسل الأرقام [1 ، n] ، كم عدد مجموعات S Signal L من S Sum إلى أقل من V؟

هذا يختلف عن مشكلة مجموع المجموعة الفرعية بثلاث طرق:

1. أهتم كم عدد المجموعات الفرعية أقل من قيمة معينة ، وليس عددهم مساو.
2. يتم إصلاح أحجام المجموعة الفرعية.
3. يهمني كم العدد يحدد مبلغًا أقل من V ، وليس فقط ما إذا كان هناك أي شيء.

هل هناك أي خوارزمية فعالة بشكل معقول لحل هذا؟

تحرير: من الواضح ، يمكن القيام بذلك في O (n اختر L) باستخدام خوارزمية توليد مجموعة. ما يهمني حقًا هو الاختراقات الذكية لتسريعها بشكل كبير.

Answer 1

(إصدار القرار) لا تزال مشكلتك مكتملة NP. الفكرة هي أنه إذا تمكنا من حل مشكلتك ، (لكل حجم مجموعة فرعية ، على سبيل المثال) ، يمكننا أن نسأل عدد المجموعات إلى أقل من V وعدد المبلغ إلى أقل من V-1 ، وفرق هذين الرقمين أخبرنا ما إذا كانت مجموعات فرعية تتجه إلى V بالضبط - وبالتالي يمكننا حل مشكلة مجموع المجموعة الفرعية. [هذا ليس دليلًا كاملاً ، لأنه ملف تقليل تورينج, ، ليس أ العديد من تخفيض واحد.]

ومع ذلك ، هناك بسيط البرمجة الديناميكية الحل الذي يعمل في الوقت O (NLV). [السبب في أن هذا لا يثبت أن p = np هو أن v يمكن أن يكون أسيًا في حجم الإدخال: مع بت n ، يمكنك تمثيل القيم حتى 2^ن. لكن على افتراض أن V ليس أسيًا ، فهذه ليست مشكلة.

دع num [v] [k] [i] يشير إلى عدد مجموعات الحجم الفرعية من العناصر الأولى من S that sum to v. يمكنك حسابها على أنها (لكل i):

    num[0][0][i] = 1
    for v = 1 to V:
        for k = 1 to L:
            num[v][k][i] = num[v][k][i-1] + num[v-S[i]][k-1][i-1]

حيث S [i] هو عنصر ITH في تسلسلك. (أي مجموعة من الحجم k تلخص V إلى V لا تستخدم S [i] ، لذلك يتم حسابها في num [v] [k] [i-1] ، أو يستخدم S [i] مما يعني أن بقية تحتوي المجموعة الفرعية على عناصر K-1 ، وتستخدم فقط أرقام I-1 الأولى في التسلسل ، ومبالغ لـ VS [i].) أخيرًا ، عد num [v] [l] [| s |] لكل V أقل من v ؛ هذا هو إجابتك.

أيضًا ، يمكنك حذف المركز الثالث إذا قمت بذلك بعناية (قم بتشغيل حلقتك لأسفل لكل I ، إلخ) ؛ أنا فقط أدرجته من أجل الوضوح.

Answer 2

لست مستعدًا لتقديم دليل ، لكن هذا يبدو أنه قد يكون قابلاً لنظام البرمجة الديناميكية: قم بتجديد قائمة المجموعات الفرعية من الحجم 2 باستخدام مجموعات فرعية من الحاسوب من الحجم 3 ، إلخ ، بحيث تحتاج Hyou فقط إلى فحص أ مجموعة صغيرة من الاحتمالات.

Answer 3

أحد التحسينات التي تتبادر إلى الذهن هي: اطلب تسلسلك (إذا لم يكن Alerady كذلك). اختر أول عناصر L-1 من بداية ذلك ، ثم اختر العنصر الأخير من هذا القبيل ، فهو أكبر قيمة ممكنة (ستوفر القيمة الأكبر التالية في التسلسل مبلغًا كبيرًا جدًا). تجاهل بقية التسلسل ، لأن هذه العناصر لا يمكن أن تكون أبدًا جزءًا من مجموعة فرعية صالحة على أي حال.

بعد ذلك أعتقد أنه بحث كامل مرة أخرى. ولكن مرة أخرى قد يكون هناك تحسينات أخرى ممكنة أيضًا.

Answer 4

يولد حل البرمجة الديناميكي لمشكلة مجموعة المجموعة الفرعية جدولًا يحتوي على هذه الإجابة (أي جدول Boolean of V بواسطة n حيث يكون V هو عدد الأقصى للعناصر و N هو عدد الأقصى من العناصر التي يمكن أن تكون في مجموعة تُنصح القيود ؛ كل منطقية تكون صحيحة إذا كان <= n العناصر يتجمع إلى <= v). لذلك إذا لم تكن N * V كبيرة جدًا بالنسبة لك ، فستجتمع خوارزمية سريعة مقبولة. يعد حل Sub Sum Sum فقط هو أعلى عنصر في هذا الجدول الذي يكون عدد العناصر <= N/2.

Answer 5

إذا كانت أعداد صحيحة إيجابية فقط ، فيمكنك القيام بخطوة التحقق اذا احتجت;

خذ مجموع L-1 أصغر الأعداد الصحيحة في المجموعة. إذا كان هذا مبلغًا X ، فيجب أن يكون NX أقل من العنصر الأكبر إذا كانت المشكلة مفترض للحصول على حل. تعال إلى التفكير في الأمر ، يمكنك القضاء على L الأخرى بهذه الطريقة ...

Answer 6

حسنًا ، لسبب واحد نظرًا لأنك تحدد الحجم = l ثم حتى لو لم تتمكن من n ^^ l (حسنًا ، L+1 ، كما كنت تقوم بعد ذلك بتلخيص كل مجموعة فرعية).

Answer 7

هذا يبدو وكأنه n اختيار k فئة من المشكلة. يتم تغطية إنشاء K-subsets من N في دليل تصميم خوارزمية Skiena ، ويشير الكتاب إلى تعداد المجموعات الفرعية ذات الصلة بالترتيب المعجم (على سبيل المثال ، على سبيل المثال). ثم قم بمجموعك ومقارنة كل مجموعة فرعية.

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

Answer 8

ربما تكون صياغة البرمجة الديناميكية هي Amenamble ل PTAs من FPTAs.