تحسين الديكارتي الطلبات مع أفيني التكاليف

Question

لدي التكلفة الأمثل طلب أنا لا أعرف كيف إذا كان هناك الأدب.هو قليلا من الصعب أن أشرح ، لذلك أعتذر مقدما عن طول السؤال.

هناك server أنا الوصول إلى ذلك يعمل بهذه الطريقة:

• الطلب على السجلات (r1, ...rn) وحقول (f1, ...fp)
• يمكنك فقط طلب المنتج الديكارتي (r1, ..., rp) × (f1,...fp)
• التكلفة (الوقت والمال) ترتبط مع هذا الطلب أفيني في حجم الطلب:

T((r1, ..., rn)x(f1, ..., fp) = a + b * n * p

دون فقدان عمومية (فقط عن طريق تطبيع), يمكننا أن نفترض أن b=1 وبالتالي فإن التكلفة هي:

T((r1, ...,rn)x(f1,...fp)) = a + n * p

• أحتاج فقط إلى طلب مجموعة فرعية من أزواج (r1, f(r1)), ... (rk, f(rk)), وهو الطلب الذي يأتي من المستخدمين.البرنامج بمثابة الوسيط بين المستخدم و الخادم (وهو خارجي).لدي الكثير من طلبات مثل هذه التي تأتي في (عشرات الآلاف يوميا).

بيانيا ، يمكننا أن نفكر في الأمر على النحو n x p متفرق المصفوفة التي كنت تريد أن تغطي قيم صفرية مع مستطيلة submatrix:

   r1 r2 r3 ... rp
   ------      ___
f1 |x  x|      |x|
f2 |x   |      ---
   ------
f3
..    ______
fn    |x  x|
      ------

وبعد:

• عدد submatrices التي تبقى معقولة بسبب تكلفة ثابتة
• جميع 'x' يجب أن تقع ضمن submatrix
• مجموع المساحة المغطاة يجب أن لا تكون كبيرة جدا بسبب الخطية التكلفة

سوف الاسم ز تناثر في معامل مشكلتي (عدد حاجة أزواج أكثر من مجموع ممكن أزواج ، g = k / (n * p).أنا أعرف معامل a.

هناك بعض الواضح الملاحظات:

• إذا كانت صغيرة, أفضل حل هو طلب كل سجل (الميدان) الزوج بشكل مستقل ، والتكلفة الإجمالية هي: k * (a + 1) = g * n * p * (a + 1)
• إذا كان كبير, أفضل حل هو طلب كل الديكارتي المنتج والتكلفة الإجمالية هي : a + n * p
• الحل الثاني هو الأفضل في أقرب وقت g > g_min = 1/ (a+1) * (1 + 1 / (n * p))
• بالطبع أوامر في الديكارتي المنتجات غير مهم لذا يمكن تبديل الصفوف والأعمدة من مصفوفة إلى جعل الأمر أكثر سهولة تغطيها ، على سبيل المثال:

   f1 f2 f3
r1  x    x
r2     x 
r3  x    x

يمكن إعادة ترتيب كما

   f1 f3 f2
r1  x  x
r3  x  x
r2       x

و ها هو الحل الأمثل الذي طلب (f1,f3) x (r1,r3) + (f2) x (r2)

• يحاول كل الحلول و تبحث عن انخفاض تكلفة ليس خيارا لأن combinatorics تنفجر:

for each permutation on rows: (n!)
   for each permutation on columns: (p!)
       for each possible covering of the n x p matrix: (time unknown, but large...)
           compute cost of the covering

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

وضع بعض الأرقام في العقول ، n هو في مكان ما بين 1 و 1000 و p في مكان ما بين 1 ، 200.نمط التغطية هو في الحقيقة ممتلئ الجسم ، لأن سجلات تأتي في الطبقات التي المجالات طلب متشابهة.للأسف لا أستطيع الوصول إلى فئة من سجل...

السؤال 1:وقد شخص ما فكرة ذكية التبسيط ، أو إشارة على ورقة يمكن أن تكون مفيدة ؟ كما لدي الكثير من الطلبات ، خوارزمية التي يعمل جيدا في المتوسط ما أنا أبحث عن (ولكن لا تستطيع أن تعمل سيئة جدا في بعض الحالات القصوى ، على سبيل المثال طلب كل مصفوفة عندما n و p كبيرة و طلب هو في الواقع تماما متفرق).

السؤال 2:في الواقع ، فإن المشكلة أكثر تعقيدا:التكلفة هي في الواقع أشبه شكل: a + n * (p^b) + c * n' * p', حيث b هو ثابت < 1 (مرة واحدة في السجل طلب الميدانية ، فإنه ليس مكلفا جدا أن نسأل عن المجالات الأخرى) ، n' * p' = n * p * (1 - g) هو عدد الخلايا لا أريد أن الطلب (لأنها غير صالحة, و هناك تكلفة إضافية في طلب أشياء غير صالحة).لا أستطيع حتى أن أحلم حل سريع لهذه المشكلة, ولكن لا يزال...فكرة أي شخص ؟

Answer 1

اختيار submatrices لتغطية طلب القيم هو شكل من مجموعة تغطي المشكلة وبالتالي NP كاملة.مشكلتك يضيف إلى هذه بالفعل مشكلة صعبة أن تكاليف مجموعات تختلف.

التي تسمح permutate الصفوف والأعمدة ليست هذه مشكلة كبيرة لأنه يمكنك فقط النظر في قطع submatrices.صف واحد من الأعمدة أربعة إلى سبعة و صف خمسة أعمدة أربعة اثنين سبعة هي مجموعة صحيحة لأنه يمكنك فقط مبادلة الصف الثاني و الصف خمس والحصول على اتصال submatrix صف واحد من الأعمدة الأربعة إلى الصف الثاني العمود سبعة.طبعا هذا إضافة بعض القيود - ليس كل مجموعات صالحة تحت كل التباديل - ولكن أنا لا أعتقد أن هذا هو أكبر مشكلة.

مقالة ويكيبيديا يعطي inapproximability النتائج أن المشكلة لا يمكن حلها في وقت متعدد الحدود أفضل ثم مع عامل 0.5 * log2(n) حيث n هو عدد مجموعات.في حالتك 2^(n * p) هو (متشائم جدا) الحد الأعلى لعدد مجموعات المحاصيل التي يمكنك أن تجد فقط حل حتى عامل 0.5 * n * p في وقت متعدد الحدود (إلى جانب N = NP وتجاهل متفاوتة التكاليف).

متفائل الأدنى لعدد مجموعات تجاهل التباديل من الصفوف و الأعمدة 0.5 * n^2 * p^2 مما أسفر عن أفضل بكثير عامل log2(n) + log2(p) - 0.5.ونتيجة لذلك يمكنك أن تتوقع فقط لإيجاد حل في أسوأ حالة n = 1000 و p = 200 حتى عامل عن 17 في حالة التفاؤل و حتى عامل عن 100.000 في حالة التشاؤم (لا يزال تجاهل متفاوتة التكاليف).

وبالتالي فإن أفضل ما يمكنك القيام به هو استخدام خوارزمية الكشف عن مجريات الأمور (مقالة ويكيبيديا يذكر تقريبا الأمثل الجشع الخوارزمية) و تقبل أن يكون هناك حالة حيث الخوارزمية ينفذ (جدا) سيئة.أو تذهب في الاتجاه الآخر الاستخدام الأمثل الخوارزمية وحاول أن تجد حلا جيدا أن استخدام المزيد من الوقت.في هذه الحالة أود أن أقترح محاولة استخدام أ* البحث.

Answer 2

أنا متأكد من أن هناك حقا جيدة خوارزمية هذا هناك في مكان ما ، ولكن هنا هي بلدي بديهية الأفكار:

1. إرم-بعض-مستطيلات النهج:

   • تحديد "تقريبا الأمثل" مستطيل الحجم على أساس a.
   • مكان هذه المستطيلات (ربما بشكل عشوائي) على النقاط المطلوبة حتى تغطية جميع النقاط.
   • الآن تأخذ كل مستطيل وتقليص قدر الإمكان دون "فقدان" أي من نقاط البيانات.
   • العثور على المستطيلات قريبة من بعضها البعض و تقرر ما إذا كان الجمع بينهما سيكون أرخص من إبقائها منفصلة.

2. تنمو

   • تبدأ مع كل نقطة في 1x1 المستطيل.
   • العثور على جميع المستطيلات في ن الصفوف/الأعمدة (حيث n قد تكون مبنية على a);انظر إذا كان يمكنك الجمع بينهما في مستطيل واحد دون أي تكلفة (أو سلبية التكلفة :D).
   • كرر.

3. يتقلص

   • تبدأ مع واحد كبير مستطيل ، الذي يغطي جميع النقاط.
   • البحث عن sub-المستطيل الذي أسهم زوج من الجانبين مع واحدة كبيرة ، ولكن يحتوي على عدد قليل جدا من النقاط.
   • قطع من واحدة كبيرة ، إنتاج اثنين من المستطيلات الصغيرة.
   • كرر.

4. رباعية

   • تقسيم الطائرة إلى 4 مستطيلات.لكل من هذه ، انظر إذا كان يمكنك الحصول على أفضل تكلفة recursing أخرى أو فقط بما في ذلك المستطيل كله.
   • إن مستطيلات ومعرفة ما إذا كان يمكنك دمج أي منها مع القليل من/أي تكلفة.\

أيضا: نضع في اعتبارنا أنه في بعض الأحيان سيكون من الأفضل أن يكون اثنين تداخل مستطيلات من مستطيل كبير وهو مجاميع منهم.E. g.الحال عندما المستطيلات اثنين فقط التداخل في زاوية واحدة.

Answer 3

حسنا فهم السؤال قد تغير.الأفكار الجديدة:

• متجر كل صف طويل بت السلسلة.و أزواج بت السلاسل معا ، تحاول أن تجد أزواج زيادة عدد 1 بت.تنمو هذه الأزواج في أكبر المجموعات (نوع ومحاولة مباراة كبيرة حقا هم مع بعضها البعض).ثم بناء على طلب من شأنها أن ضرب أكبر مجموعة ثم ننسى كل هذه البتات.كرر حتى كل ما فعلت.ربما التبديل من الصفوف والأعمدة في بعض الأحيان.

• البحث عن جميع الصفوف/الأعمدة مع صفر أو عدد قليل من النقاط في نفوسهم."حذف" مؤقتا.الآن كنت تبحث في ما يمكن أن يشملها طلب أن يترك منهم.الآن ربما تنطبق واحدة من التقنيات الأخرى ، والتعامل مع تجاهل الصفوف/الأعمدة بعد ذلك.طريقة أخرى في التفكير في هذا هو:التعامل مع كثافة النقاط أولا ثم الانتقال إلى sparser منها.

Answer 4

لأن القيم هي متفرق ، يمكن أن يكون العديد من المستخدمين يطلبون مماثلة القيم ؟ يتم التخزين المؤقت داخل التطبيق الخاص بك الخيار ؟ الطلبات يمكن فهرستها من قبل تجزئة هذا هو وظيفة (x,y) الموقف ، بحيث يمكنك بسهولة تحديد مؤقتا مجموعات التي تقع ضمن منطقة الصحيح من الشبكة.تخزين مؤقتا مجموعات في شجرة ، على سبيل المثال ، سوف تسمح لك لإيجاد الحد الأدنى مؤقتا فرعية تغطي على طلب مجموعة بسرعة جدا.ثم يمكنك أن تفعل الخطية البحث على مجموعة فرعية ، وهي صغيرة.

Answer 5

كنت تنظر n سجلات (صفوف) و ف الحقول (الأعمدة) المذكورة في طلب المستخدم تعيين n نقطة ف الأبعاد الفضاء ({0,1}^p) مع ith تنسيق يجري 1 المنتدى فقد X ، تحديد التسلسل الهرمي من المجموعات, مع خشن العنقودية في جذور بما في ذلك جميع X.لكل عقدة في التجميع الهرمي النظر في المنتج الذي يغطي جميع الأعمدة المطلوبة (وهذا هو الصفوف(أي subnode) × cols(أي subnode)).ثم تقرر من أسفل إلى أعلى ما إذا كان دمج الطفل أغطية (دفع غطاء كامل) ، أو الاحتفاظ بها منفصلة الطلبات.(أغطية ليست من أعمدة متجاورة ، ولكن بالضبط تلك الحاجة ؛ أيفكر قليلا ناقلات)

أنا أتفق مع Artelius أن تداخل المنتج-الطلبات يمكن أن تكون أرخص.بلدي النهج الهرمي سوف تحتاج إلى تحسين إدماج ذلك.

Answer 6

عملت قليلا على ذلك ، ومن الواضح هنا ، O(n^3) الجشع, كسر التناظر خوارزمية (السجلات والحقول تعامل بشكل منفصل) في بايثون مثل الزائفة رمز.

فكرة تافهة:نبدأ بمحاولة طلب واحد لكل سجل ، ونحن الأجدر دمج حتى لم يبق شيء يستحق أن دمج.هذا algo لديه عيب واضح أنه لا يسمح تداخل الطلبات ، ولكن أتوقع أن تعمل بشكل جيد جدا في الحياة الحقيقية الحالة (a + n * (p^b) + c * n * p * (1 - g) تكلفة وظيفة) :

# given are
# a function cost request -> positive real
# a merge function that takes two pairs of sets (f1, r1) and (f2, r2) 
# and returns ((f1 U f2), (r1 U r2))

# initialize with a request per record

requests = [({record},{field if (record, field) is needed}) for all needed records]
costs = [cost(request) for request in requests]

finished = False

while not finished: # there might be something to gain
    maximum_gain = 0
    finished = True
    this_step_merge = empty

    # loop onto all pairs of request
    for all (request1, request2) in (requests x request) such as request1 != request2:
        merged_request = merge(request1, request2)
        gain = cost(request1) + cost(request2) - cost(merged_request)

        if gain > maximum_gain:
            maximum_gain = gain
            this_step_merge = (request1, request2, merged_request)

    # if we found at least something to merge, we should continue
    if maximum_gain > 0:
        # so update the list of requests...
        request1, request2, merged_request = this_step_merge
        delete request1 from requests
        delete request2 from requests
        # ... and we are not done yet
        insert merged_request into requests
        finished = False

output requests

هذا هو O(n3 * p) لأن:

• بعد التهيئة نبدأ n طلبات
• على while حلقة يزيل بالضبط طلب واحد من المسبح في كل التكرار.

• الداخلية for حلقة تتكرر على (ni^2 - ni) / 2 متميزة أزواج من الطلبات ، مع ني من n إلى واحد في أسوأ الأحوال (عندما كنا دمج كل شيء في واحد كبير الطلب).

  1. شخص ما يمكن أن تساعدني مشيرا جدا سيئة حالات الخوارزمية.هل الصوت reasonnable استخدام هذه ؟
  2. فمن O(n^3) وهي طريقة مكلفة جدا بالنسبة كبيرة من المدخلات.أي فكرة لتحسين ذلك ؟

شكرا مقدما !