>
Fa   |   Ar   |   En
   ارایه یک رویکرد ابتکاری نوین برای ساده سازی گراف اولیه مساله بیشینه جریان  
   
نویسنده خداکرمی وحید ,حاجی پور وحید ,حسنی محمدرضا
منبع پژوهش هاي مهندسي صنايع در سيستم هاي توليد - 1394 - دوره : 3 - شماره : 5 - صفحه:107 -119
چکیده    مساله بیشینه جریان شبکه به دنبال یافتن بیشترین جریانی است که در شبکه می‌تواند از ریوس منبع به ریوس چاه منتقل شود. هدف از این تحقیق بهبود و ساده‌سازی گراف اولیه است که به‌عنوان گراف پایه برای حل به الگوریتم‌های بیشینه جریان شبکه داده می‌شود. در این صورت زمان حل مساله کاهش می‌یابد. بسیاری از الگوریتم های بیشینه جریان با تکیه بر مفهوم سطح در گراف، بیشینه جریان را با پیدا کردن مسیر و ارسال آن به‌دست آورده‌اند. در این مقاله، با دقت به مفهوم عمق گراف در الگوریتم پیشنهادی، برآنیم از منظری جدید به مساله پرداخته شود تا از پیچیدگی زمانی مساله کاسته شود. در الگوریتم پیشنهادی سعی شده است با استفاده از مفهوم عمق در گراف، ابتدا با ساده‌سازی مساله از طریق حذف کمان ها و ریوس، ابعاد و پیچیدگی محاسباتی مساله کاهش یابد. این الگوریتم همچنین با مسایلی که در آنها چندین چشمه و چاه وجود دارد سازگار است. تحلیل روند و گام های حل، با استفاده از ماتریس تهیه شده از گراف مساله بسیار ساده است و با دیگر الگوریتم های ارایه شده در ادبیات نیز سازگاری دارد. لذا به‌راحتی می توان پس از چند مرحله ساده‌سازی از دیگر روش ها، به ادامه حل مساله پرداخت. در نهایت، عملکرد روش حل ارایه شده بر روی مسایل آزمایشی تولید شده با ابعاد مختلف مورد تجزیه و تحلیل قرار گرفته و الگوریتم های موجود در ادبیات مورد مقایسه قرار گرفته شده است.
کلیدواژه مساله بیشینه جریان ,گراف جهت دار ,رویکرد ابتکاری
آدرس دانشگاه بوعلی سینا, استادیار گروه مهندسی صنایع، دانشکده مهندسی، دانشگاه بوعلی سینا، همدان, ایران, دانشگاه بوعلی سینا, دانشجوی دکتری گروه مهندسی صنایع، دانشکده مهندسی، دانشگاه بوعلی سینا، همدان, ایران, دانشگاه بوعلی سینا, دانشجوی کارشناسی گروه مهندسی صنایع، دانشکده مهندسی، دانشگاه بوعلی سینا، همدان، ایران, ایران
 
 

Copyright 2015
Islamic World Science Citation Center
All Rights Reserved