كيفية حساب التباديل في الوقت الخطي ، مع تطور

Question

لدي مشكلة في جدولة الموارد في Java حيث تحتاج الأشياء إلى تسلسل ، ولكن هناك قيود على الموارد التي يمكن أن تكون بجوار بعضها البعض. القياس الجيد هو سلسلة من "الأرقام" ، حيث يمكن أن تكون أرقام معينة فقط بجوار بعضها البعض. كان حلي متكررًا ، ويعمل بشكل جيد للسلاسل الصغيرة ، ولكن وقت التشغيل هو O (x^n) ، حيث x هو عدد الأرقام الممكنة (القاعدة) ، و n هو طول السلسلة. يصبح بسرعة لا يمكن السيطرة عليها.

باستخدام مصفوفة التوافق أدناه ، إليك بعض الأمثلة على السلاسل المسموح بها
طول 1: 0 ، 1 ، 2 ، 3 ، 4
طول 2: 02 ، 03 ، 14 ، 20 ، 30 ، 41
طول 3: 020 ، 030 ، 141 ، 202 ، 203 ، 302 ، 303 ، 414

     0  1  2  3  4
   ---------------------
0|  0  0  1  1  0
1|  0  0  0  0  1
2|  1  0  0  0  0
3|  1  0  0  0  0
4|  0  1  0  0  0

بدأ حلي لحساب جميع سلاسل الطول n بسلسلة فارغة ، وتصور الرقم الأول ، وإجراء مكالمة متكررة لجميع سلاسل الطول N-1. المكالمات العودية تحقق من آخر رقم تمت إضافته وجرب جميع التباديل التي يمكن أن تكون بجوار هذا الرقم. هناك بعض التحسينات التي تم إجراؤها بحيث لا أحاول أن أحاول أن تتفق 00 ، 01 ، 04 في كل مرة ، على سبيل المثال - 02 ، 03 فقط ، لكن الأداء لا يزال ضعيفًا لأنه يقيس من القاعدة 5 (المثال) إلى قاعدة 4000.

أي أفكار حول طريقة أفضل لحساب التباديل بخلاف محاولة تعدادها جميعًا؟

Answer 1

إذا كنت ترغب فقط في عدد خيوط طول معين ، فيمكنك فقط مضاعفة مصفوفة التوافق مع نفسها عدة مرات ، وتلخيص قيمها.

ن = طول السلسلة
أ = مصفوفة التوافق
عدد الأوتار الممكنة = مجموع أ^ن-1

أمثلة قليلة:

n = 1
| 1 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 0 0 |
| 0 0 0 1 0 |
| 0 0 0 0 1 |
sum: 5

n = 3
| 2 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 1 0 |
| 0 0 1 1 0 |
| 0 0 0 0 1 |
sum: 8

n = 8
| 0 0 8 8 0 |
| 0 0 0 0 1 |
| 8 0 0 0 0 |
| 8 0 0 0 0 |
| 0 1 0 0 0 |
sum: 34

المصفوفة الأصلية (الصف أنا, ، عمودي ي) يمكن اعتبارها عدد الأوتار التي تبدأ بالرمز أنا, والذي رمزه التالي هو الرمز ي. بدلاً من ذلك ، يمكنك أن ترى ذلك بعدد من سلاسل الطول 2, ، الذي يبدأ بالرمز أنا وينتهي بالرمز ي.

تكاثر المصفوفة يحافظ على هذا الثابت ، لذلك بعد الأسعار ، أ^ن-1 سيحتوي على عدد الأوتار التي تبدأ بالرمز أنا, ، لديه طول ن, وينتهي في الرمز ي.

نرى ويكيبيديا: الأسعار عن طريق التربيع لخوارزمية لحساب أسرع من قوى المصفوفة.

(شكرًا stefan.ciobaca)

هذه الحالة المحددة تقل إلى الصيغة:

عدد الأوتار الممكنة = F(ن) = 4 + Σ_ك=1..ن 2^{⌊ك-1⁄₂⌋} = F(ن-1) + 2^{⌊ن-1⁄₂⌋}

n       f(n)
----    ----
   1       5
   2       6
   3       8
   4      10
   5      14
   6      18
   7      26
   8      34
   9      50
  10      66

Answer 2

هل تريد فقط معرفة عدد سلاسل الطول المعطى الذي يمكنك بناءه مع القواعد في المصفوفة المحددة؟ إذا كان الأمر كذلك ، فإن هذا النهج مثل هذا يجب أن يعمل:

n = 5
maxlen = 100

combine = [
      [0, 0, 1, 1, 0],
      [0, 0, 0, 0, 1],
      [1, 0, 0, 0, 0],
      [1, 0, 0, 0, 0],
      [0, 1, 0, 0, 0]
   ]

# counts of strings starting with 0,1,...,4, initially for strings of length one:
counts = [1, 1, 1, 1, 1]

for size in range(2, maxlen+1):
   # calculate counts for size from count for (size-1)
   newcount = []
   for next in range(n):
      total = 0
      for head in range(n):
         if combine[next][head]:
            # |next| can be before |head|, so add the counts for |head|
            total += counts[head]
      # append, so that newcount[next] == total
      newcount.append(total)
   counts = newcount
   print "length %i: %i items" % (size, sum(counts))

Answer 3

يبدو أن الخوارزمية الخاصة بك هي الأمثل.

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

الرد على التعليق:

إذا كنت تريد فقط حسابها ، فيمكنك استخدام البرمجة الديناميكية:

دع العد [n] [m] يكون صفيفًا ، حيث يكون العد [l] [j] هو عدد مثل هذه التباديل التي يكون طولها وينتهي بـ j ،

ثم عد [l] [i] = count [l-1] [i1]+count [l-1] [i2]+... ، حيث i1 ، i2 ، ... هي الأرقام التي يمكن أن تسبق i (هذا يمكن حفظها في صفيف محسوب مسبقًا).

يمكن ملء كل خلية من العد عن طريق تجميع أرقام K (تعتمد K على المصفوفة المتوافقة) ، وبالتالي فإن التعقيد هو O (KMN) ، M هو طول التقليب ، و N هو العدد الإجمالي للأرقام.

Answer 4

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

بعد ذلك ، سيستغرق روتينك لإنشاء نتيجة متراكمة ورقم الرقم والرقم الحالي. شيء مثل:

// not really Java - and you probably don't want chars, but you'll fix it
void GenerateDigits(char[] result, int currIndex, char currDigit)
{
    if (currIndex == kMaxIndex) {
        NotifyComplete(result);
        return;
    }
    char[] validFollows = GetValidFollows(currDigit); // table lookup
    foreach (char c in validFollows) {
        result[currIndex] = c;
        GenerateDigits(result, currIndex+1, c);
    }
}

يزداد التعقيد كدالة لعدد الأرقام التي يجب توليدها ، ولكن هذه الوظيفة تعتمد على العدد الإجمالي للمتابعة المسببة لأي رقم واحد. إذا كان العدد الإجمالي للمتابعات هو نفسه بالنسبة لكل رقم ، فلنقول ، K ، فإن الوقت المناسب لإنشاء جميع التباديل الممكنة سيكون O (k^n) حيث N هو عدد الأرقام. آسف ، لا يمكنني تغيير الرياضيات. الوقت لإنشاء أرقام n في القاعدة 10 هو 10^n.

Answer 5

لست متأكدًا تمامًا مما تطلبه ، ولكن نظرًا لوجود N N! التباديل لسلسلة من الأرقام n ، لن تكون قادرًا على سردها بشكل أسرع من n!. لست متأكدًا تمامًا من كيف تعتقد أنك حصلت على وقت تشغيل O (n^2).