نوع مقاله : مقاله پژوهشی
نویسندگان
1 استادیار دانشکده مدیریت و حسابداری دانشگاه علامه طباطبایی، تهران، (مسئول مکاتبات)
2 کارشناس ارشد مدیریت و حسابداری دانشگاه علامه طباطبایی، تهران
3 کارشناس ارشد مدیریت صنعتی، دانشگاه تربیت مدرس، تهران
چکیده
مسئله کوتاه ترین مسیر یکی از مسائل معروف بهینه سازی می باشد که توسط دانشمندان زیادی مورد مطالعه قرار گرفته است. از جمله کاربردهای این مسئله در زمینه های ارتباطی و حمل و نقل است که عموما توسط الگوریتم دیجسترا حل می شود. در این مقاله دو حوزه علمی مجزای الکترونیک و دقیق در عملیات به هم ارتباط داده شده است تا الگوریتم جدیدی جهت یافتن جواب بهینه مسئله کوتاه ترین مسیر با استفاده از قوانین و شبکه های الکتریکی پدید آید. الگوریتم پیشنهادی قادر به حل مسئله کوتاه ترین مسیر در گراف های جهت دار و بدون جهت و همچون حل مسائل طولانی ترین مسیر جهت دار می باشد. در این الگوریتم از شبکه های الکتریکی بدین طریق استفاده می شود که مقاومت الکتریکی هر شاخه معادل با وزن هر یال در مسئله کوتاه ترین مسیر فرض می شود. سپس با استفاده از قوانین اهم و ولتاژ کیرشهف، جریان در هر حلقه محاسبه می گردد. پس از آن شاخصه هایی که دارای بیشترین جریان عبوری هستند مشخص شده که در نتیجه طبق قانون اهم دارای کمترین مقاومت یا کمترین وزن در مسئله کوتاه ترین مسیر می باشند. بدین ترتیب کوتاه ترین مسیر در شبکه به دست می آید. از مزایای این الگوریتم هم گرایی سریع تر به جواب و زمان محاسبات کمتر نسبت به روشهای مرسوم به خصوص در شبکه هایی با تعداد گره های زیاد می باشد. الگوریتم مزبور برای سه مثال تشریح گردیده است.
الگوریتم مزبور برای سه مثال تشریح گردیده است.
کلیدواژه‌ها
عنوان مقاله [English]
The Algorithm for Solving Shortest-Path Problems Based on Electrical Circuit Laws
نویسندگان [English]
- Ali Khatami Firoozabadi 1
- Hossein Mohebbi 2
- Mohammad Zarei Mahmoodabadi 3
1
2
3
چکیده [English]
Shortest-path problem is one of the well-known optimization problems that has been studied by many scientists in recent years. Applications of this problem such as transportation and communication are generally solved by Dijkstra's Algorithm (Labeling). In this paper, two separate scientific fields, electronics and operation research have been linked to each other and a new algorithm has been created for to find the optimization solution of a shortest- path problem by using electric networks and rules. The proposed algorithm can solve the shortest-path problem in directed graphs and no order ones, and also can solve the longest path problems in directed graphs.
In this algorithm, electrical network are used in a way that the resistance value of each branch is equal to each edge weights in the shortest-path problems. Then with using Ohm Law and Kirchhaffs Voltage Law (KVL), the current in each circuit cycle is calculated. Then the branches that contain the most passing current are specified, and according to Ohm’s Law, has the lowest resistance or weight. Thus, the shortest path in the network is achieved. Advantage of this algorithm is faster convergence to the answer and less computing time than the conventional method, especially in networks with more nods. The mentioned algorithm has been described for three examples.
کلیدواژه‌ها [English]
- Shortest path
- Ohm law
- KVL law
- Resistance
- Electric Circuits
- Optimization Solution
)