أطول متتالية فرعية متزايدة

في علوم الحاسوب ، تهدف مسألة إيجاد أطول متتالية متزايدة إلى إيجاد متتالية جزئية من متتالية معطاة ، بحيث تكون عناصرها مرتبة تصاعديًا، وتكون أطول ما يمكن. هذه المتتالية ليست بالضرورة متصلة أو فريدة. تُدرس المتتاليات المتزايدة في سياق تخصصات رياضية متنوعة ، تشمل الخوارزميات ، ونظرية المصفوفات العشوائية ، ونظرية التمثيل ، والفيزياء . ^{[ 1 ] [ 2 ]} يمكن حل مسألة إيجاد أطول متتالية متزايدة في زمن${\displaystyle O(n\log n),}$أين${\displaystyle n}$يشير إلى طول سلسلة الإدخال. ^{[ 3 ]}

في أول 16 حدًا من متتالية فان دير كوربوت الثنائية

٠، ٨، ٤، ١٢، ٢، ١٠، ٦، ١٤، ١، ٩، ٥، ١٣، ٣، ١١، ٧، ١٥

إحدى أطول المتتاليات الفرعية المتزايدة هي

0، 2، 6، 9، 11، 15.

يبلغ طول هذه المتتالية الفرعية ستة عناصر؛ ولا تحتوي المتتالية المدخلة على أي متتاليات فرعية متزايدة مكونة من سبعة عناصر. ليست أطول متتالية فرعية متزايدة في هذا المثال هي الحل الوحيد: على سبيل المثال،

٠، ٤، ٦، ٩، ١١، ١٥

٠، ٢، ٦، ٩، ١٣، ١٥

٠، ٤، ٦، ٩، ١٣، ١٥

وهي متواليات فرعية متزايدة أخرى ذات طول متساوٍ في نفس متوالية الإدخال.

ترتبط مشكلة أطول متتالية متزايدة ارتباطًا وثيقًا بمشكلة أطول متتالية مشتركة ، والتي لها حل برمجة ديناميكية في زمن تربيعي : أطول متتالية متزايدة من متتالية${\displaystyle S}$هي أطول سلسلة فرعية مشتركة من${\displaystyle S}$و${\displaystyle T,}$أين${\displaystyle T}$هي نتيجة عملية الفرز${\displaystyle S.}$لكن في الحالة الخاصة التي يكون فيها المدخل عبارة عن تبديل للأعداد الصحيحة${\displaystyle 1,2,\ldots ,n,}$يمكن جعل هذا النهج أكثر كفاءة، مما يؤدي إلى حدود زمنية من الشكل التالي${\displaystyle O(n\log \log n).}$^{[ 4 ]}

أكبر مجموعة متماسكة في مخطط التبديلات تُقابل أطول سلسلة فرعية متناقصة من التبديل الذي يُحدد المخطط (بافتراض أن السلسلة الأصلية غير المُبدلة مُرتبة من الأدنى إلى الأعلى). وبالمثل، فإن أكبر مجموعة مستقلة في مخطط التبديلات تُقابل أطول سلسلة فرعية غير متناقصة. لذلك، يُمكن استخدام خوارزميات أطول سلسلة فرعية متزايدة لحل مشكلة المجموعات المتماسكة بكفاءة في مخططات التبديلات. ^{[ 5 ]}

في تطابق روبنسون-شينستيد بين التباديل وجداول يونغ ، يساوي طول الصف الأول من الجدول المقابل للتبديل طول أطول سلسلة فرعية متزايدة من التبديل، ويساوي طول العمود الأول طول أطول سلسلة فرعية متناقصة. ^{[ 3 ]}

تحل الخوارزمية الموضحة أدناه مشكلة إيجاد أطول سلسلة فرعية متزايدة بكفاءة باستخدام المصفوفات والبحث الثنائي . تعالج الخوارزمية عناصر السلسلة بالترتيب، مع الحفاظ على أطول سلسلة فرعية متزايدة تم العثور عليها حتى الآن. لنرمز إلى قيم السلسلة بـ${\displaystyle X[0],X[1],\ldots ,}$إلخ. ثم، بعد المعالجة${\displaystyle X[i],}$ستخزن الخوارزمية عددًا صحيحًا${\displaystyle L}$والقيم في مصفوفتين:

• ${\displaystyle L}$— يخزن طول أطول سلسلة فرعية متزايدة تم العثور عليها حتى الآن.
• ${\displaystyle M[l]}$— يخزن الفهرس${\displaystyle k}$ذات أصغر قيمة${\displaystyle X[k]}$بحيث يكون هناك تسلسل فرعي متزايد الطول${\displaystyle l}$وينتهي عند${\displaystyle X[k]}$في النطاق${\displaystyle k\leq i.}$لنفترض صراحةً أن${\displaystyle K_{i,l}}$يشير إلى مجموعة جميع المؤشرات${\displaystyle j}$بحيث${\displaystyle j\leq i}$ويوجد تسلسل فرعي متزايد الطول${\displaystyle l}$وينتهي عند${\displaystyle X[j].}$ثم${\displaystyle k=M[l]}$هو المؤشر في${\displaystyle K_{i,l}}$والتي${\displaystyle X[M[l]]}$يتم تقليلها إلى الحد الأدنى؛ مما يعني أن${\displaystyle M[l]\in K_{i,l}}$و${\displaystyle X[M[l]]=\min _{j\in K_{i,l}}X[j]}$(أو ما يعادل ذلك،${\displaystyle M[l]\in K_{i,l}}$ولكل${\displaystyle j\in K_{i,l},}$${\displaystyle X[M[l]]\leq X[j]}$إذا حققت عدة مؤشرات هذا الشرط،${\displaystyle M[l]}$وهو الأكبر.
  • للتوضيح، "توجد سلسلة فرعية متزايدة الطول${\displaystyle l}$وينتهي عند${\displaystyle X[k]}$"يعني أن هناك موجودًا"${\displaystyle l}$المؤشرات${\displaystyle i_{1}<i_{2}<\cdots <i_{l}=k}$وينتهي عند${\displaystyle k}$بحيث${\displaystyle X\left[i_{1}\right]<X\left[i_{2}\right]<\cdots <X[k].}$
  • لاحظ أن${\displaystyle 1\leq l\leq i+1,}$لأن${\displaystyle l\geq 1}$يمثل طول السلسلة الفرعية المتزايدة، و${\displaystyle k\geq 0}$يمثل مؤشر نهايتها.
  • طول${\displaystyle M}$يكون${\displaystyle 1}$أكثر من طول${\displaystyle X}$لكن من الممكن ألا تستخدم الخوارزمية جميع العناصر في هذه المصفوفة (في الواقع، إذا كان طول أطول تسلسل متزايد هو${\displaystyle L}$عندها فقط${\displaystyle M[1],\ldots ,M[L]}$(يتم استخدامها بواسطة الخوارزمية). ولكن إذا${\displaystyle M[l]}$يتم استخدام/تعريف ذلك${\displaystyle l-1\leq M[l]}$(علاوة على ذلك، في التكرار)${\displaystyle i,}$${\displaystyle M[l]\leq i}$سوف يفعل ذلك أيضًا).${\displaystyle M[0]}$غير مُعرَّف لأن المتتاليات ذات الطول${\displaystyle 0}$ليس لها فهرس نهائي (${\displaystyle M[0]}$(يمكن أن تكون أي قيمة).
• ${\displaystyle P[k]}$— يخزن فهرس السلف لـ${\displaystyle X[k]}$في أطول سلسلة فرعية متزايدة تنتهي عند${\displaystyle X[k].}$
  • طول${\displaystyle P}$يساوي ذلك الخاص بـ${\displaystyle X,}$
  • لو${\displaystyle k>0}$ثم${\displaystyle P[k]<k}$بينما${\displaystyle P[0]}$غير محدد لأن${\displaystyle X[0]}$ليس له سلف (${\displaystyle P[0]}$(يمكن أن تكون أي قيمة).

لأن الخوارزمية أدناه تستخدم الترقيم الذي يبدأ من الصفر ، وذلك للتوضيح${\displaystyle M}$مبطن بـ${\displaystyle M[0],}$والتي تبقى غير مستخدمة بحيث${\displaystyle M[l]}$يتوافق مع سلسلة فرعية بطول${\displaystyle l.}$يمكن للتنفيذ الفعلي أن يتجاوز ذلك${\displaystyle M[0]}$وتعديل المؤشرات وفقًا لذلك.

لاحظ أنه في أي نقطة من الخوارزمية، يكون التسلسل $${\displaystyle X[M[1]],X[M[2]],\ldots ,X[M[L]]}$$ يتزايد. لأنه إذا كانت هناك متتالية جزئية متزايدة الطول${\displaystyle l\geq 2}$وينتهي عند${\displaystyle X[M[l]],}$ثم هناك أيضًا سلسلة فرعية بطول${\displaystyle l-1}$تنتهي بقيمة أصغر: أي القيمة التي تنتهي عند${\displaystyle X[P[M[l]]].}$وبالتالي، يمكننا إجراء عمليات بحث ثنائية في هذا التسلسل في وقت لوغاريتمي.

ثم تسير الخوارزمية على النحو التالي:

P = مصفوفة طولها N M = مصفوفة طولها N + 1 M[0] = -1 // غير مُعرّف، لذا يمكن تعيينه لأي قيمة. L = 0 for i in range 0 to N-1: //N-1 included // البحث الثنائي عن أصغر قيمة موجبة l ≤ L // بحيث يكون X[M[l]] >= X[i] lo = 1 hi = L + 1 بينما لو < هي: mid = lo + floor((hi-lo)/2) // lo <= mid < hi إذا كان X[M[mid]] >= X[i] hi = mid وإلا : // إذا كان X[M[mid]] < X[i] لو = منتصف + 1 // بعد البحث، يكون lo == hi أكبر بمقدار 1 من // طول أطول بادئة لـ X[i] newL = lo // العنصر السابق لـ X[i] هو آخر فهرس لـ // المتتالية الفرعية ذات الطول newL-1 P[i] = M[newL-1] M[newL] = i إذا كان طول الجديد أكبر من طوله الحالي: // إذا وجدنا سلسلة فرعية أطول من أي سلسلة فرعية لدينا // لم يتم العثور عليه بعد، قم بتحديث L L = newL // إعادة بناء أطول متتالية فرعية متزايدة // يتكون من قيم X عند المؤشرات L: // ..., P[P[M[L]]], P[M[L]], M[L] S = مصفوفة طولها L k = M[L] for j in range L-1 to 0: //0 included S[j] = X[k] k = P[k] إرجاع S

لأن الخوارزمية تُجري عملية بحث ثنائي واحدة لكل عنصر من عناصر التسلسل، يمكن التعبير عن وقتها الإجمالي باستخدام ترميز Big O كما يلي:${\displaystyle O(n\log n).}$يناقش فريدمان (1975) صيغةً معدلةً من هذه الخوارزمية، والتي ينسبها إلى دونالد كنوث ؛ في الصيغة المعدلة التي يدرسها، تختبر الخوارزمية ما إذا كانت كل قيمة${\displaystyle X[i]}$يمكن استخدام هذه الطريقة لتمديد أطول سلسلة متزايدة حالية، في وقت ثابت، قبل إجراء البحث الثنائي. مع هذا التعديل، تستخدم الخوارزمية على الأكثر${\displaystyle n\log _{2}n-n\log _{2}\log _{2}n+O(n)}$المقارنات في أسوأ الحالات، وهي الحالة المثلى لخوارزمية تعتمد على المقارنة حتى العامل الثابت في${\displaystyle O(n)}$مصطلح. ^{[ 6 ]}

مثال على التشغيل

وفقًا لنظرية إردوس-سزكيريس ، فإن أي تسلسل من${\displaystyle n^{2}+1}$تحتوي الأعداد الصحيحة المميزة على متتالية فرعية متزايدة أو متناقصة بطول${\displaystyle n+1.}$^{[ 7 ] [ 8 ]} بالنسبة للمدخلات التي يكون فيها كل تبديل للمدخل متساوي الاحتمال، فإن الطول المتوقع لأطول سلسلة فرعية متزايدة هو تقريبًا${\displaystyle 2{\sqrt {n}}.}$^{[ 9 ] [ 2 ]}

في الحد كما${\displaystyle n}$تنص نظرية بايك-ديفت-يوهانسون على أنه عندما يقترب طول أطول متتالية فرعية متزايدة من متتالية عشوائية الترتيب من اللانهاية ، فإن طول أطول متتالية فرعية متزايدة من متتالية عشوائية الترتيب من${\displaystyle n}$[ 10 ]​​​​^​​​

تمت دراسة أطول سلسلة فرعية متزايدة أيضًا في سياق الخوارزميات عبر الإنترنت ، حيث تكون عناصر سلسلة من المتغيرات العشوائية المستقلة ذات التوزيع المستمر${\displaystyle F}$– أو بدلاً من ذلك، عناصر تبديل عشوائي – تُعرض كل منها على حدة لخوارزمية يجب عليها أن تقرر ما إذا كانت ستُضمّن كل عنصر أو تستبعده، دون معرفة العناصر اللاحقة. في هذا النوع من المشكلة، الذي يتيح تطبيقات مثيرة للاهتمام في سياقات متعددة، من الممكن ابتكار إجراء اختيار أمثل، يُعطى عينة عشوائية بحجم${\displaystyle n}$كمدخل، سيولد تسلسلًا متزايدًا بطول متوقع أقصى يبلغ حجمه تقريبًا${\displaystyle {\sqrt {2n}}.}$^{[ 11 ]} يبلغ تباين طول المتتالية الفرعية المتزايدة المختارة بواسطة هذا الإجراء الأمثل ما يقارب${\displaystyle {\sqrt {2n}}/3,}$ويكون توزيعها النهائي طبيعيًا تقاربيًا بعد التمركز والقياس المعتادين. ^{[ 12 ]} تنطبق النتائج التقاربية نفسها، مع حدود أكثر دقة، على المسألة المقابلة في سياق عملية وصول بواسون . ^{[ 13 ]} ويُقدَّم تحسين إضافي في سياق عملية بواسون من خلال إثبات نظرية النهاية المركزية لعملية الاختيار الأمثل، والتي تنطبق، مع تطبيع مناسب، بمعنى أكثر شمولًا مما هو متوقع. لا يُنتج البرهان نظرية النهاية الوظيفية "الصحيحة" فحسب، بل يُنتج أيضًا مصفوفة التغاير (المفردة) للعملية ثلاثية الأبعاد التي تلخص جميع العمليات المتفاعلة. ^{[ 14 ]}

• أناتولي فيرشيك الذي درس تطبيقات نظرية الزمر على أطول المتتاليات الفرعية المتزايدة في التباديل العشوائية. ^{[ 15 ]}
• أطول سلسلة فرعية متناوبة
• أطول سلسلة فرعية مشتركة
• فرز الصبر - تقنية فعالة لإيجاد طول أطول سلسلة فرعية متزايدة
• المونويد البلاستيكي - نظام جبري مُعرَّف بتحويلات تحافظ على طول أطول متتالية فرعية متزايدة

• أطول سلسلة فرعية متزايدة لعالم الخوارزميات
• أطول متتالية متزايدة مبسطة
• إيجاد عدد أطول التسلسلات الفرعية المتزايدة