این سایت در حال حاضر پشتیبانی نمی شود و امکان دارد داده های نشریات بروز نباشند
پژوهش های مهندسی صنایع در سیستم های تولید، جلد ۳، شماره ۵، صفحات ۱۰۷-۱۱۹
عنوان فارسی ارایه یک رویکرد ابتکاری نوین برای ساده سازی گراف اولیه مسأله بیشینه جریان
چکیده فارسی مقاله مسأله بیشینه جریان شبکه به دنبال یافتن بیشترین جریانی است که در شبکه می‌تواند از رئوس منبع به رئوس چاه منتقل شود. هدف از این تحقیق بهبود و ساده‌سازی گراف اولیه است که به‌عنوان گراف پایه برای حل به الگوریتم‌های بیشینه جریان شبکه داده می‌شود. در این صورت زمان حل مسأله کاهش می‌یابد. بسیاری از الگوریتم­های بیشینه جریان با تکیه بر مفهوم سطح در گراف، بیشینه جریان را با پیدا کردن مسیر و ارسال آن به‌دست آورده‌اند. در این مقاله، با دقت به مفهوم عمق گراف در الگوریتم پیشنهادی، برآنیم از منظری جدید به مسأله پرداخته شود تا از پیچیدگی زمانی مسأله کاسته شود. در الگوریتم پیشنهادی سعی شده است با استفاده از مفهوم عمق در گراف، ابتدا با ساده‌سازی مسأله از طریق حذف کمان­ها و رئوس، ابعاد و پیچیدگی محاسباتی مسأله کاهش یابد. این الگوریتم همچنین با مسائلی که در آنها چندین چشمه و چاه وجود دارد سازگار است. تحلیل روند و گام­های حل، با استفاده از ماتریس تهیه شده از گراف مسأله بسیار ساده است و با دیگر الگوریتم­های ارایه شده در ادبیات نیز سازگاری دارد. لذا به‌راحتی می­توان پس از چند مرحله ساده‌سازی از دیگر روش­ها، به ادامه حل مسأله پرداخت. در نهایت، عملکرد روش­ حل ارایه شده بر روی مسائل آزمایشی تولید شده با ابعاد مختلف مورد تجزیه و تحلیل قرار گرفته و الگوریتم­های موجود در ادبیات مورد مقایسه قرار گرفته شده است.
کلیدواژه‌های فارسی مقاله مساله بیشینه جریان، گراف جهت‌دار، رویکرد ابتکاری،
عنوان انگلیسی A Novel Heuristic Approach to Simplify Initial Graph of Maximum Flow Problem
چکیده انگلیسی مقاله Network maximum flow problem trying to find the maximum flow that can transmit from the source nodes to sink nodes. The purpose of this research is to improve and simplify the initial graph that given as a problem to solve by network maximum flow algorithm. Most of maximum flow algorithms solve the problem with finding route & transmitting based on basic feasible solution. In this paper, we attempt to present a new heuristic approach according to depth concept in graph to reduce the problem time complexity with removing arcs and nodes. This algorithm is compatible with multi-source multi-sink algorithms in the literature. Finally, to demonstrate applicability of the proposed approach, several test problems are first generated; then, the comparisons are carried out. The results show that the proposed heuristic can simplify the problem and consequently reduce the complexity of maximum flow problem
کلیدواژه‌های انگلیسی مقاله Maximum flow problem, Directed graph, Heuristic approach
نویسندگان مقاله وحید خداکرمی |
هیات علمی، دانشگاه بوعلی سینا
سازمان اصلی تایید شده: دانشگاه بوعلی سینا (Bu ali sina university)

وحید حاجی پور |
دانشگاه بوعلی سینا
سازمان اصلی تایید شده: دانشگاه بوعلی سینا (Bu ali sina university)

محمدرضا حسنی | mohammad reza
دانشگاه بوعلی سینا
سازمان اصلی تایید شده: دانشگاه بوعلی سینا (Bu ali sina university)

نشانی اینترنتی http://ier.basu.ac.ir/article_1216_6bc5791e01c4d81ac4ebaaf1d689232c.pdf
فایل مقاله اشکال در دسترسی به فایل - ./files/site1/rds_journals/1430/article-1430-246357.pdf
کد مقاله (doi)
زبان مقاله منتشر شده fa
موضوعات مقاله منتشر شده
نوع مقاله منتشر شده
برگشت به: صفحه اول پایگاه   |   نسخه مرتبط   |   نشریه مرتبط   |   فهرست نشریات