حساب الحلول لعدم المساواة الخطية [مغلقة

Question

أحاول حل مشكلة انخفضت إلى حساب عدد عدد صحيح حلول لعدد من عدم المساواة الخطية. يجب أن أكون قادرًا على حساب عدد الحلول لأي عدد من المتغيرات C_1 ، ... ، C_N ، ولكن بالنسبة إلى n = 3 ، يمكن كتابة المعادلات على النحو التالي:

المعادلات. http://silicon.appspot.com/readdoc؟id=155604

الآن ، أعرف قيم N و R مقدمًا وأرغب في العثور على عدد حلول (C_1 ، ... ، C_N) الموجودة.

هل يمكن القيام بذلك بكفاءة (أسرع من تعداد الحلول)؟ (إذا كان الأمر كذلك: كيف؟ ؛ إن لم يكن: لماذا؟)

Answer 1

لنفترض أن لديك بعض التعليمات البرمجية لإنتاج جميع الحلول.

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

from math import floor, ceil

def iter_solutions(r, n, z):
    c = [None] * n
    def iter_solutions_bounded(k, pick):
        # pick is the last pick, if any, and 0 otherwise
        assert (1 <= k < n and pick == c[k]) or (k == n and pick == 0)

        min_ck = int(ceil(-pick / r))
        max_ck = int(floor((z - pick) / r))
        if k == 1:
            for ck in range(max(min_ck, 0), min(max_ck, z) + 1):
                c[0] = ck
                yield c
        else:
            for ck in range(min_ck, max_ck + 1):
                c[k - 1] = ck
                for soln in iter_solutions_bounded(k - 1, ck):
                    yield soln
    return iter_solutions_bounded(n, 0)

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

from math import floor, ceil

def memoize(f):
    cache = {}
    def g(*args):
        if args in cache:
            return cache[args]
        tmp = cache[args] = f(*args)
        return tmp
    return g

def len_range(a, b):
    if a <= b:
        return b - a
    return 0

def count_solutions(r, n, z):
    @memoize
    def count_solutions_bounded(k, pick):
        min_ck = int(ceil(-pick / r))
        max_ck = int(floor((z - pick) / r))
        if k == 1:
            return len_range(max(min_ck, 0), min(max_ck, z) + 1)
        else:
            return sum(count_solutions_bounded(k - 1, ck) for ck in range(min_ck, max_ck + 1))
    return count_solutions_bounded(n, 0)

بعض التحسينات الممكنة:

• إذا كان هذا صحيحًا ج₁ ... ج_ن هي دائما ≤ ض, ، ثم اكتشاف ذلك والعودة على الفور 0 من شأنه أن يساعد كثيرا ن. في الواقع ، فإنه سيقلل من وقت التشغيل إلى صاعقة البرق (نيوزيلندي).

• إذا كان المقصود ذلك ج₁ ... ج_ن كلها غير سالبة ، هذا أفضل. إجراء التغييرات المناسبة على min_ck و max_ck سيجعل هذا o (نيوزيلندي) مع ثابت أصغر ، ويمكن أن تكون ذاكرة التخزين المؤقت صفيف ثنائي الأبعاد مسطح بدلاً من جدول التجزئة الأبطأ الذي لدي.

• قد تكون قادرًا على القيام بعمل أفضل من خلال إنشاء ذاكرة التخزين المؤقت بشكل منهجي ، بدلاً من ملء "الطلب" بالطريقة التي يعمل بها رمز المذكرات هذا. قم أولاً ببناء ذاكرة التخزين المؤقت بالكامل لـ n = 1 ، ثم لـ n = 2 ، وهلم جرا. وبهذه الطريقة ، يمكنك تجنب التكرار ، وفي كل خطوة يمكنك التخلص من البيانات المخزنة مؤقتًا لم تعد بحاجة إليها (بعد حساب النتائج لـ N = 2 ، لا تحتاج إلى إدخالات N = 1 بعد الآن).

Answer 2

لحل هذه المشكلة ، ربما أذهب إلى عوالم برمجة القيد. يبدو أن لديك كلاسيكي all different القيد (يشبه إلى حد ما مشكلة n-queens). احصل على واحدة من حلوب القيد المجانية المدرجة أدناه. هذا سوف يمنحك حل بكفاءة تامة. ستولد بشكل أساسي شجرة البحث بأكملها ولكن مع تطبيقات القيد المتمايزة اللطيفة هناك ، ستنتهي الشجرة إلى لا شيء تقريبًا.

http://www.gecode.org/ http://minion.sourceforge.net/ http://jacop.osolpro.com/ http://research.microsoft.com/apps/pubs/default.aspx؟id=64335

ها هي قائمة ويكيبيديا:
http://en.wikipedia.org/wiki/constraint_programming#constraint_programming_libraries_for_imperative_programming_languages

Answer 3

هذا ليس حقًا حلًا كاملاً لمشكلتك ، لكنني أعتقد أنه قد يساعدك أو على الأقل يمنحك بعض الأفكار.

متطلباتك من أن تكون الحلول عدد صحيح تجعل هذه مشكلة NP. إذا نظرنا أولاً إلى استرخاء المشكلة بحيث يكون المجال هو الأرقام الحقيقية ، فأنت تطلب حل مشكلة الرضا عن 0 <= A*C <= 1 ، حيث A عبارة عن مصفوفة و C هي متجه غير معروف. هذا برنامج خطي قياسي (LP مع هدف تافهة) ، ويمكن حله بكفاءة (في الوقت متعدد الحدود). قد ترغب في استخدام هذا كاختبار تمرير أولي لتحديد الجدوى لأنه إذا لم يكن لدى LP المريح حلول ، فمن المؤكد أن LP INTEGER ليس لديه حلول بالتأكيد. ستعيد LP Solver جيدًا أيضًا نقطة ممكنة إن أمكن ، وقد تكون قادرًا على تحويل إدخالات المتجه للعثور على حل صحيح.

Answer 4

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

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