تحقیق در عملیات ( Operation Research)

بهینه سازی

تکنیکی برای بهبود عملی الگوریتم کوتاه ترین مسیر در شبکه
نویسنده : دکتر نعمت اله تقی نژاد - ساعت ٤:٢٢ ‎ق.ظ روز جمعه ٢٠ دی ۱۳٩٢
 

  

A Practical Improvement

 

 

الگوریتم shortest augmenting path وقتی d(s)≥n باشد،تمام می شود.

تحقیقات تجربی نشان داده اند که در خیلی از موارد الگوریتم پس از اینکه به maximum flow  رسید،زمان زیادی را صرف relabel کردن نودها میکند تا شرط d(s)≥n برقرار شود و الگوریتم خاتمه یابد.

این اتفاق به این دلیل می افتد که تا شرط d(s)≥n برقرار نشود،الگوریتم نمیداند که maximum flow را پیدا کرده است.

در اینجا تکنیکی پیشنهاد می شود که میتوانیم قبل از اینکه برچسب نود s در شرط d(s)≥n صدق کند، وجود maximum flow  را از طریق minimum cut شناسایی کنیم. و البته این تکنیک را در  Application to capacity scaling Algorithm بکار خواهیم گرفت.

 میتوانید فایل کامل پروژه را بصورت رایگان در زیر دریافت کنید:

دانلود

 


 
 
 



backgroundcolor= class=#2f57a2width:230px; padding-top: 5px;td width=logo