الگوریتم بوزن

**الگوریتم بوزن** در تئوری صف با توجه به تئوری احتمال در ریاضی، الگوریتمی برای برای محاسبهٔ ثابت طبیعی ((normalization constant G(K) در تئوری Gordon-Newell است. این روش را ابتدا Jeffrey P. Buzen  در سال ۱۹۷۳ مطرح کرد.
هنگامی که G محاسبه شود می‌توان توزیع احتمالی شبکه را بدست آورد. در مقابل این روش، آنالیز مقدار میانی، الگوریتمی است که می‌توان برای بدست آوردن بعضی از اندازه‌گیری‌های کارایی استفاده کرد (مانند میانگین طول صف) بدون نیاز به محاسبهٔ مستقیم ثابت طبیعی.

محرک اصلی این الگوریتم کارایی است. روش محاسبهٔ مستقیم Gordon-Newell نیاز به شمارش تمامی حالت‌هایی که سیستم می‌تواند در آن باشد است که باعث  combinatorial explosion می‌شود. الگوریتم بوزن از زمان اجرایی n۲  است که منجر به عملی شدن تئوری Gordon-Newell و  باز شدن کلاس بزرگی از صف‌ها برای مدل کردن دقیق می‌شود.
در نوشته‌های مربوط به صف‌ها، از الگوریتم بوزن گاهی به عنوان الگوریتم convolution یاد می‌کنند.

## آماده‌سازی مسئله
یک صفِ شبکه‌ای بسته را در نظر بگیرید که M جایگاه سرویس دهی و N کاربر چرخشی داشته باشند. ni را تعداد مشتریانی که در iمین جایگاه قرار دارند در نظر بگیریم؛ رابطه زیر برقرار است:
:\sum_{i=1}^M n_i = N
فرض می کنیم که زمان سرویس دهی برای یک مشتری در iمین جایگاه توسط توزیع نمایی با متغیر تصادفی با میانگین ۱/μi است و بعد از اتمام سرویس دهی در iمین جایگاه با احتمال  pij به جایگاه jمین جایگاه می‌رود.
با استفاده از تئوری Gordon-Newell توزیع تعادل (equilibrium) مشتریان در شبکه به صورت زیر است:
:P(n_1,n_2,\cdots,n_M) = \frac{1}{G(N)}\prod_{i=1}^M \left( X_i \right)^{n_i}
که می‌توان Xi  را از معادله ی زیر بدست آورد:
:\mu_j X_j = \sum_{i=1}^M \mu_i X_i p_{ij}\text{ for }j=1,\ldots,N.

(G(N ثابت طبیعی است به‌طوری‌که احتمالات بالا در مجموع یک شود. 
هدف الگوریتم بوزن این است که مقدار G را به صورت عددی محاسبه کند.

## تعداد کاربران قابل انتظار
توزیع عادی Gordon-Newell که در بالا آماده است معمولاً برای موارد تئوری است؛ با این حال می‌توان اندازه‌گیری‌های کارایی مفیدی را از آن استخراج کرد. بوزن نشان می دهد که احتمال اینکه دقیقاً k کاربر در جایگاه i باشند از معادله ی زیر بدست می‌آید.
:P(n_i = k) = \frac{X_i^k}{G(N)}[G(N-k) - X_i G(N-k-1)]

همچنین تعداد کاربرانی که انتظار می‌رود در iمین جایگاه باشند از رابطه ی زیر بدست می‌آید.
:E[n_i] = \sum_{k=1}^N X_i^k \frac{G(N-k)}{G(N)}.

توجه داشته باشید که این معادلات نیز شامل G هستند.
در معادلات بالا ارزشمندی این الگوریتم هویدا می‌شود.

## نتایج و مشتقات الگوریتم
الگوریتم تنها G را حساب نمی‌کند، بلکه تابع دو بعدی زیر را حساب می‌کند
: g(n,m) \text{ for }n=0,1,\cdots,N \text{ and }m=1,\cdots,M

هنگامی که محاسبات به پایان رسید، مقادیری که مورد نظر ما است از طریق رابطه ی زیر بدست می‌آید.
: G(n) = g(n,M) \text{ for }n=0,1,\cdots,N.

تعریف g و تابع بازگشتی برای محاسبه ی آن به ترتیب زیر است:
:
\begin{align}
g(n, m) & = \sum_{n_1 + \cdots + n_m = n} \prod_{i=1}^m (X_i)^{n_i} \\
& = \sum_{(n_1 + \cdots + n_m = n) \wedge (n_m=0)}^n \prod_{i=1}^m (X_i)^{n_i} +
\sum_{(n_1 + \cdots + n_m = n) \wedge (n_m>0)}^n \prod_{i=1}^m (X_i)^{n_i} \\
& = g(n,m-1)+X_m g(n-1,m)
\end{align}


همچنین
: g(n, 1) = (X_1)^n \text{ for }n=0,1,\cdots,N

و
: g(0, m) = 1 \text{ for }m=1,2,\cdots,M

رابطه ی بازگشتی اجازه می دهد تمامی (G(Nها در زمان محاسباتی (O(MN محاسبه شوند.

## پیاده‌سازی
فرض می کنیم که Xm  با حل معادلات مرتبط بدست آمده‌است و به عنوان ورودی برای پیاده‌سازی ما موجود است.
هرچند g به صورت ماتریس دوبعدی است، می‌توان آن را به صورت ستون به ستون، و شروع از چپ‌ترین ستون محاسبه کرد.
برنامه از یک ستون vector، C برای نشان دادن ستونی از g که در آن است استفاده می‌کند.


```pascal
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 حاوی مقادیر مورد نظر  (G(۰)، G(۱) to G(Nاست. 

## منابع

* Jain: The Convolution Algorithm (class handout)
* Menasce: Convolution Approach to Queueing Algorithms (presentation)

## پیوند به بیرون
* example.com

رده:الگوریتم‌ها
رده:الگوریتم‌های آماری
رده:فرایندهای تصادفی
رده:مقاله‌های ایجادشده توسط ایجادگر
رده:نظریه صف