Solving Shortest Route Using Dynamic Programming Problem

Tadios Kiros Kenea

doi:10.17485/IJST/v15i31.1342

Article

Solving Shortest Route Using Dynamic Programming Problem

VIEWS 770
PDF 189

Indian Journal of Science and Technology

DOI: 10.17485/IJST/v15i31.1342

Year: 2022, Volume: 15, Issue: 31, Pages: 1527-1531

Original Article

Solving Shortest Route Using Dynamic Programming Problem

Tadios Kiros Kenea^1*

¹Department Of Mathematics, Arbaminch University, Arbaminch, Ethiopia

*Corresponding Author
Email: [email protected]

Received Date:20 July 2021, Accepted Date:26 May 2022, Published Date:12 August 2022

This work is licensed under a Creative Commons Attribution 4.0 International License.

Abstract

Objective:- To determine the shortest distance in salesman of dynamic programming problem. Method:- Recursive equation and arrow drawing methods are used to determine the shortest distance in salesman of dynamic programming problem. An implementation of the traveling salesman problem using dynamic programming is presented in this study which generates optimal answer. Findings:- Forward and backward recursive methods take time and complex to find optimal solution (shortest distance) but arrow drawing method is useful and simple for solving several different types of salesman problems in dynamic programming problem compared to forward and backward recursive equation method to determine shortest route in dynamic programming problem. Novelty:- Dynamic programming allows to break up the given problem into a number of sub problems or stages. At each stage there are a number of decision alternatives to be called as states. So the dynamic programming uses the idea of recursive equation to solve traveling salesman problem. The Traveling salesman problem is easy to understand and difficult to solve using forward and backward recursive equation.

Keywords: Dynamic programming; Salesman problem; Operation research; Recursion equation

References

Liang S, Fuhrman S, Somogyi R. REVEAL, a general reverse engineering algorithm for inference of genetic network architectures. Proceedings of the Pacific Symposium on Biocomputing. 1998;3:18–29.
Akutsu T, Miyano S, Kuhara S. Inferring qualitative relations in genetic networks and metabolic pathways. Bioinformatics. 2000;16(8):727–734.
Friedman N, Linial M, Nachman I, Pe'er D. Using Bayesian networks to analyze expression data. Proceedings of the fourth annual international conference on Computational molecular biology - RECOMB '00. 2000;7:601–620.
Imoto S, Kim Sunyong, Goto T, Aburatani S, Tashiro K, Kuhara S, et al. Bayesian network and nonparametric heteroscedastic regression for nonlinear modeling of genetic network. Proceedings. IEEE Computer Society Bioinformatics Conference. 2003;1:231–252.
Liu TFF, Sung WKK, Mittal A. Learning gene network using time-delayed Bayesian network. International Journal on Artificial Intelligence Tools. 2006;15(03):353–370.
Margolin AA, Wang K, Lim WK, Kustagi M, Nemenman I, Califano A. Reverse engineering cellular networks. Nature Protocols. 2006;1(2):662–671.
Margolin AA, Nemenman I, Basso K, Wiggins C, Stolovitzky G, Favera RD, et al. ARACNE: An Algorithm for the Reconstruction of Gene Regulatory Networks in a Mammalian Cellular Context. BMC Bioinformatics. 2006;7(S1).
Kimura S, Nakayama S, Hatakeyama M. Genetic network inference as a series of discrimination tasks. Bioinformatics. 2009;25(7):918–925.
Akutsu T, Tamura T, Horimoto K. Completing Networks Using Observed Data. Lecture Notes in Computer Science. 2009;5809:126–140.
Kau Ffman SA. The Origins of Order: Self-Organization and Selection in Evolution. New York, NY, USA. Oxford University Press. 1993.
Halpern IJ, Priess. Shortest path with time constraints on movement and parking. 1974;4:241–253.
Tamura T, Yamanishi Y, Tanabe M, Goto S, Kanehisa M, Horimoto K, et al. Integer programming-based method for completing signaling pathways and its application to analysis of colorectal cancer. Genome Informatics 2010. 2010;24:193–203.
Lewis R. Algorithms for Finding Shortest Paths in Networks with Vertex Transfer Penalties. Algorithms. 2020;13(11):269.

Copyright

© 2022 Kiros Kenea. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

Published By Indian Society for Education and Environment (iSee)