الگوریتم بوزِن: روشی کارآمد برای محاسبه ثابت نرمال‌سازی در نظریه صف

الگوریتم بوزِن: مقدمه

در نظریه صف، الگوریتم بوزِن (یا الگوریتم کانولوشن) روشی کارآمد برای محاسبه ثابت نرمال‌سازی G(N) در قضیه گوردن-نیول است. این الگوریتم که توسط جفری پ. بوزِن در ۱۹۷۱ معرفی شد، با کاهش چشمگیر پیچیدگی محاسباتی، امکان مدل‌سازی سیستم‌های واقعی را فراهم کرد.

مشکل و راه‌حل

محاسبه G(N) به صورت ساده نیازمند برشمردن تمام حالات ممکن است. بوزِن با استفاده از تجزیه‌ای هوشمندانه، این محاسبه را به NM ضرب و NM جمع کاهش داد. این روش نه تنها G(N) بلکه مقادیر میانی G(1) تا G(N-1) را نیز محاسبه می‌کند.

توصیف الگوریتم

الگوریتم با تقسیم اصطلاحات به دو گروه و استفاده از رابطه بازگشتی G(N) = Xm * G(N-1, M) + G(N, M-1) عمل می‌کند. این رابطه به همراه شرایط مرزی، محاسبه را بهینه می‌سازد.

اجرای الگوریتم

با استفاده از یک بردار ستونی C، الگوریتم به صورت ستون به ستون پیش می‌رود. حلقه‌های تو در تو مقادیر G(n) را محاسبه و در بردار C ذخیره می‌کنند.