القيد رضا:اختيار أرقام حقيقية مع بعض الخصائص

Question

لدي مجموعة من ن أرقام حقيقية.لدي أيضا مجموعة من الوظائف ،

f_1, f_2, ..., f_m.

كل من هذه الوظائف يأخذ قائمة من الأرقام كما حجتها.لدي أيضا مجموعة من م نطاقات ،

[l_1, u_1], [l_2, u_2], ..., [l_m, u_m].

أريد أن مرارا وتكرارا اختيار مجموعة فرعية {r_1, r_2, ..., r_k} k عناصر هذه

l_i <= f_i({r_1, r_2, ..., r_k}) <= u_i for 1 <= i <= m.

علما بأن الوظائف هي على نحو سلس.تغيير عنصر واحد في {r_1, r_2, ..., r_k} لن تتغير f_i({r_1, r_2, ..., r_k}) بكثير.المتوسط و التباين هما f_i التي تستخدم عادة.

هذه هي م القيود التي لا تحتاج إلى تلبية.

وعلاوة على ذلك أريد أن أفعل هذا حتى أن مجموعة فرعية اخترت يتم توزيعها بشكل موحد على كل مجموعة من مجموعات فرعية من حجم ك التي تلبي هذه m القيود.ليس هذا فقط, ولكن أريد أن أفعل هذا بطريقة فعالة.كيف بسرعة تشغيله سوف تعتمد على كثافة حلول في غضون جميع الحلول الممكنة (إذا كان هذا هو 0.0, ثم الخوارزمية يمكن تشغيل إلى الأبد).(نفترض أن f_i (أي أنا) يمكن حسابها في كمية ثابتة من الزمن.)

علما أن n هو كبيرة بما يكفي لا أستطيع أن القوة الغاشمة المشكلة.هذا هو مجرد تكرار خلال كافة k-عنصر فرعية والعثور على تلك التي تلبي m القيود.

هل هناك طريقة لعمل هذا ؟

ما أنواع التقنيات تستخدم عادة ل CSP مثل هذا ؟ هل يمكن لأحد أن يدلني من الكتب أو المقالات التي تتحدث عن مشاكل من هذا القبيل (وليس فقط الإلكتروني بشكل عام ، ولكن Csp تنطوي المستمر ، بدلا من القيم المنفصلة)?

Answer 1

على افتراض كنت تبحث عن الكتابة الخاصة بك تطبيق واستخدام المكتبات الموجودة للقيام بذلك ، هناك خيارات في العديد من اللغات مثل بيثون-القيد, أو كريم أو شوكو جافا أو CSP C++.الطريقة التي وصفتها المشكلة يبدو أنك تبحث عن الغرض العام CSP حلالا.هل هناك أية خصائص الوظائف التي قد تساعد في الحد من التعقيد ، مثل أن تكون رتيب?

Answer 2

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

دون معرفة المزيد عن شكل f, لا يمكنك جعل أي ضمانات حول ما إذا كان الوقت هو متعدد الحدود أو لا (أو حتى لديك أي فكرة عن كيفية ضرب البقعة التي تجتمع القيد).بعد كل شيء, إذا f_1 = (x^2 + y^2 - 1) و f_2 = (1 - x^2 - y^2) و القيود f_1 < 0 و f_2 < 0, لا يمكنك إرضاء كل هذا (و دون الوصول إلى التحليليه شكل من الوظائف يمكنك الجزم).

Answer 3

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

النظر:

• أرقام = {1....100}
• م = 1 (الحفاظ على أنها بسيطة)
• F1 = متوسط
• L1 = 10
• U1 = 50

الآن كم فرعية من {1...100} هل يمكنك أن تأتي مع أن تنتج في المتوسط بين 10 و 50?

Answer 4

هذا يبدو وكأنه مشكلة صعبة جدا.لأبسط الحال مع الخطية وظائف يمكن أن نلقي نظرة على البرمجة الخطية.