خوارزمية بوزين

في نظرية الطوابير ، وهي فرع من فروع نظرية الاحتمالات الرياضية ، تُعدّ خوارزمية بوزين (أو خوارزمية الالتفاف ) خوارزمية لحساب ثابت التوحيد G( N ) في نظرية غوردون-نيويل . اقترح جيفري ب. بوزين هذه الطريقة لأول مرة في أطروحته للدكتوراه عام 1971 ^{[ 1 ]} ، ونُشرت لاحقًا في مجلة محكمة عام 1973 ^{[ 2 ].} يُعدّ حساب G( N ) ضروريًا لحساب التوزيع الاحتمالي الثابت لشبكة طوابير مغلقة ^{[ 3 ] .}

يتطلب إجراء حساب بسيط لثابت التطبيع تعداد جميع الحالات. بالنسبة لشبكة مغلقة بها N عميل متداول و M مرفق خدمة، فإن G( N ) هو مجموع${\displaystyle {\tbinom {N+M-1}{M-1}}}$تتكون الحدود الفردية من M عامل مرفوعة إلى قوى مجموعها N. تحسب خوارزمية بوزين G( N ) باستخدام NM عملية ضرب و NM عملية جمع فقط. وقد فتح هذا التحسين الكبير المجال لتطبيق نظرية جوردون-نيويل على نماذج أنظمة الحاسوب في العالم الحقيقي، بالإضافة إلى أنظمة التصنيع المرنة، وغيرها من الحالات التي قد تتشكل فيها اختناقات وطوابير انتظار ضمن شبكات مرافق الخدمة المترابطة. ^{[ 4 ]} تُحسب قيم G(1)، G(2)، ...، G( N -1)، التي يمكن استخدامها لحساب كميات أخرى مهمة، كمنتجات ثانوية للخوارزمية.

لنفترض وجود شبكة انتظار مغلقة تضم M من مرافق الخدمة و N من العملاء المترددين. بافتراض أن وقت خدمة العميل في مرفق الخدمة i يُعطى بواسطة متغير عشوائي ذي توزيع أسي بمعامل μᵢ _، وأنه بعد إتمام الخدمة في مرفق الخدمة i ، سينتقل العميل إلى مرفق الخدمة j باحتمالية pᵢⱼ _. ^{[ 3 ]}

يترك${\displaystyle \mathbb {P} (n_{1},n_{2},\cdots ,n_{M})}$لتكن احتمالية الحالة المستقرة التي يكون فيها عدد العملاء في مرفق الخدمة i مساويًا لـ n _i، حيث i = 1، 2، ...، M. ويترتب على ذلك من نظرية جوردون-نيويل أن

${\displaystyle \mathbb {P} (n_{1},n_{2},\cdots ,n_{M})={\frac {1}{{\text{G}}(N)}}}$${\displaystyle \left(X_{1}\right)^{n_{1}}}$${\displaystyle \left(X_{2}\right)^{n_{2}}}$....${\displaystyle \left(X_{M}\right)^{n_{M}}}$

تُكتب هذه النتيجة عادةً بشكل أكثر اختصارًا على النحو التالي:

${\displaystyle \mathbb {P} (n_{1},n_{2},\cdots ,n_{M})={\frac {1}{{\text{G}}(N)}}\prod _{i=1}^{M}\left(X_{i}\right)^{n_{i}}}$

يتم تحديد قيم X _{i عن طريق حل}

${\displaystyle \mu _{j}X_{j}=\sum _{i=1}^{M}\mu _{i}X_{i}p_{ij}\quad {\text{ لـ }}j=1,\ldots ,M.}$

G ( N ) هو ثابت تطبيع يتم اختياره بحيث يكون مجموع جميع${\displaystyle {\tbinom {N+M-1}{M-1}}}$قيم${\displaystyle \mathbb {P} (n_{1},n_{2},\cdots ,n_{M})}$يساوي 1. تمثل خوارزمية بوزين أول إجراء فعال لحساب G( N ). ^{[ 2 ] [ 4 ]}

تأخذ الحدود الفردية التي يجب جمعها معًا لحساب G( N ) الشكل التالي:

${\displaystyle \left(X_{1}\right)^{n_{1}}}$${\displaystyle \left(X_{2}\right)^{n_{2}}}$....${\displaystyle \left(X_{M}\right)^{n_{M}}}$لاحظ أن هذه المجموعة من الحدود يمكن تقسيمها إلى مجموعتين. تضم المجموعة الأولى جميع الحدود التي يكون أسها${\displaystyle \left(X_{M}\right)}$أكبر من أو يساوي 1. وهذا يعني أن${\displaystyle \left(X_{M}\right)}$يمكن استخراج العامل المرفوع للأس 1 من كل من هذه الحدود.  

بعد استبعاد العوامل${\displaystyle \left(X_{M}\right)}$تظهر نتيجة مفاجئة: الحدود المُعدّلة في المجموعة الأولى مُطابقة للحدود المُستخدمة لحساب ثابت التوحيد لنفس الشبكة بعد إزالة عميل واحد. وبالتالي، يُمكن كتابة مجموع الحدود في المجموعة الأولى على النحو التالي: " X _M مضروبًا في G( N - 1)". تُشكّل هذه الفكرة الأساس لتطوير الخوارزمية. ^{[ 4 ]}  

لننتقل الآن إلى المجموعة الثانية. أسّ X _M لكل حدّ في هذه المجموعة يساوي صفرًا. ونتيجةً لذلك، يختفي مرفق الخدمة M فعليًا من جميع حدود هذه المجموعة (لأنه يتقلص في كل حالة إلى عامل 1). وهذا يجعل العدد الإجمالي للعملاء في مرافق الخدمة المتبقية M - 1 يساوي N. تشمل المجموعة الثانية جميع الترتيبات الممكنة لهؤلاء العملاء N.

للتعبير عن هذا المفهوم بدقة، افترض أنه تم الحصول على X1 _، X2 _، ...، XM _لشبكة معينة تحتوي على M من مرافق الخدمة. لأي n ≤ N و m ≤ M، عرّف g( n,m ) على أنه ثابت التوحيد لشبكة تحتوي على n من العملاء، و m من مرافق الخدمة (1، 2، ...، m )، وقيم   X1 _، X2 _، ...، Xm _التي  تطابق أول m عنصر من التسلسل الأصلي X1 _، X2 _، ...، _XM .

وبناءً على هذا التعريف، يمكن الآن كتابة مجموع الحدود في المجموعة الثانية على النحو التالي: g( N , M -1).

ويترتب على ذلك مباشرة أن " X _M مرات G( N -1)"، وهو مجموع الحدود في المجموعة الأولى، يمكن إعادة كتابته على النحو التالي " X _M مرات g( N -1, M )".  

بالإضافة إلى ذلك، يمكن الآن إعادة كتابة ثابت التطبيع G( N ) في نظرية جوردون-نيويل على النحو التالي g( N , M ).

بما أن G( N ) يساوي المجموع الكلي للحدود في المجموعتين الأولى والثانية،

G( N ) = g( N , M ) = X _M g( N -1, M ) + g( N , M -1)

من الواضح أن علاقة التكرار هذه موجودة لأي قيمة وسيطة لـ n   من 1 إلى N ، ولأي قيمة وسيطة لـ m من 1 إلى M.

هذا يعني أن g( n,m ) = X _m g( n -1, m ) + g( n,m -1). خوارزمية بوزين هي ببساطة تطبيق تكراري لهذه العلاقة التكرارية الأساسية، بالإضافة إلى الشروط الحدية التالية.

g(0, m ) = 1 لجميع قيم m من 1 إلى M.

g( n ,1) = ( X _i ) ⁿ لـ n = 0, 1, … N

تُمكّن نظرية غوردون-نيويل المحللين من تحديد الاحتمال الثابت المرتبط بكل حالة فردية في شبكة انتظار مغلقة. يجب بعد ذلك جمع هذه الاحتمالات الفردية لتقييم احتمالات أخرى مهمة. على سبيل المثال، يجب جمع احتمال أن يكون إجمالي عدد العملاء في مركز الخدمة i أكبر من أو يساوي k ، وهو P( ni _≥ k )، على جميع _{قيم ni} ≥ k ، ولكل قيمة من هذه القيم ، _يجب جمع جميع الطرق الممكنة لتوزيع العملاء المتبقين N – ni على _مراكز الخدمة M – 1 الأخرى في الشبكة.

يمكن حساب العديد من هذه الاحتمالات الهامشية بأقل جهد إضافي. ويتضح ذلك جليًا في حالة P( ni _≥ k). فمن الواضح أنه _يجب رفع Xi إلى القوة k أو أعلى في كل حالة يكون فيها عدد العملاء في مركز الخدمة i أكبر من أو يساوي k . وبالتالي، يمكن استخراج Xik _كعامل ^مشترك من كل احتمال من هذه الاحتمالات، مما ينتج عنه مجموعة من الاحتمالات المعدلة التي يُعطى مجموعها بالصيغة G( N - k)/G( N ). وتُفضي هذه الملاحظة إلى النتيجة البسيطة والفعالة التالية:

P( n _i ≥ k ) = ( X _i ) ^k G( N - k )/G( N )

ويمكن بعد ذلك استخدام هذه العلاقة لحساب التوزيعات الهامشية والعدد المتوقع للعملاء في كل مرفق خدمة.

${\displaystyle \mathbb {P} (n_{i}=k)={\frac {X_{i}^{k}}{G(N)}}[G(Nk)-X_{i}G(Nk-1)]\quad {\text{ لـ }}k=0,1,\ldots ,N-1,}$

${\displaystyle \mathbb {P} (n_{i}=N)={\frac {X_{i}^{N}}{G(N)}}.}$

يُعطى العدد المتوقع للعملاء في مرفق الخدمة i بالمعادلة التالية:

${\displaystyle \mathbb {E} (n_{i})=\sum _{k=1}^{N}X_{i}^{k}{\frac {G(Nk)}{G(N)}}.}$

تُعزى هذه التوصيفات للكميات ذات الأهمية من حيث G( n ) أيضًا إلى بوزن. ^{[ 2 ]}

سنفترض أن قيم X_{_m} قد حُسبت بحل المعادلات ذات الصلة، وهي متاحة كمدخلات لبرنامجنا. على الرغم من أن g( n,m ) هي مصفوفة ثنائية الأبعاد من حيث المبدأ، إلا أنه يمكن حسابها عمودًا تلو الآخر، بدءًا من أعلى العمود الأيسر، ثم النزول إلى أسفل كل عمود حتى الوصول إلى العمود التالي على اليمين. يستخدم البرنامج متجهًا عموديًا واحدًا C لتمثيل العمود الحالي من g .

تقوم الحلقة الأولى في الخوارزمية أدناه بتهيئة متجه العمود C[n] بحيث يكون C[0] = 1 و C(n) = 0 عندما يكون n ≥ 1. لاحظ أن C[0] يظل مساويًا لـ 1 خلال جميع التكرارات اللاحقة.  

في الحلقة الثانية، يتم تعيين كل قيمة متتالية لـ C(n) لـ n≥1 مساوية للقيمة المقابلة لـ g( n,m) أثناء تقدم الخوارزمية في العمود m. ويتحقق ذلك عن طريق تعيين كل قيمة متتالية لـ C(n) مساوية لما يلي:

g( n,m-1 ) بالإضافة إلى X _m مضروبة في g( n-1,m ).  

لاحظ أن g( n,m-1 ) هي القيمة السابقة لـ C(n)، و g( n-1,m ) هي القيمة الحالية لـ C(n-1).

C [ 0 ] := 1 for n := 1 step 1 until N do C [ n ] := 0 ;for m := 1 step 1 until M do for n := 1 step 1 until N do C [ n ] := C [ n ] + X [ m ] * C [ n - 1 ] ;

عند الانتهاء، تتوافق القيم النهائية لـ C[n] مع العمود M في المصفوفة g( n,m ). وبالتالي، فهي تمثل القيم المطلوبة G (0)، G (1)، ...، G (N) . ^{[ 2 ]}

• جاين: خوارزمية الالتفاف (مذكرة صفية)
• Menasce: نهج الالتفاف لخوارزميات الطوابير (عرض تقديمي)