الگوریتم تقریبات برشی بازگشتی: روشی نو جهت محاسبه اطمینان پذیری کلی شبکه

محاسبه دقیق اطمینان پذیری کلی شبکه از جمله مسائل دشوار(NP-hard) است که حجم محاسبات آن بصورت نمائی با زیاد شدن تعداد گره ها و شاخه ها در شبکه افزایش می یابد. در این مقاله یک روش تقریبی بمنظور محاسبه اطمینان پذیری کلی شبکه با دقت معین ارائه می شود . در الگوریتم ارائه شده ، نخست بر مبنای احتمال بروز خرابی در کات ست های ضعیف شبکه ، تخمینی از عدم اطمینان شبکه را پیدا می کنیم و با پیمایش و یافتن احتمال خرابی در تمامی کات ست های شبکه حدود بالا و پائین خطای ناشی از این تخمین را می یابیم . سپس با یافتن احتمال خرابیهای همزمان در دو و یا چند کات ست از مجموعه کات ست های ضعیف شبکه بطور بازگشتی دقت تخمین را بهتر و حدود بالا و پائین خطای تخمین را به یکدیگر نزدیکتر می کنیم . تکرار متوالی الگوریتم بازگشتی هنگامی خاتمه می یابد که تمام ترکیبات ممکن از خرابیهای کات ست های ضعیف در شبکه که احتمالی بیش از دقت تخمین مورد نظر را دارند، در محاسبه عدم اطمینان شبکه لحاظ گردیده باشد . بمنظور نشان دادن میزان کارآیی ر وش پیشنهاد شده، اطمینان پذیری کلی چندین شبکه نمونه را با بکارگیری روش تقریبات برشی بازگشتی بدست آورده ایم و نتایج حاصل را با روشهای قبلی مقایسه کرده ایم. نتایج مقایسه بهبود قابل توجه در دقت تخمین را نشان می دهند.

Keywords:

اطمینان پذیری کلی شبکه , تقریب برشی , کات ست ضعیف , الگوریتم بازگشتی