SOLVING SHORTEST ROUTE USING DYNAMIC PROGRAMMING PROBLEM

Main Article Content

TADIOS KIROS KENEA

Abstract

Dynamic programming is a technique that allows to break up the given problem in to a number of sub problems which is stages. At each stage there are a number of decision alternatives that is states. So the dynamic programming uses the idea of recursive equation to solve traveling salesman (a road network) problem using dynamic programming. The Traveling salesman (network) problem is one of the problem in mathematics and computer science which had drown attention as it is easy to understand and difficult to solve using forward and backward recursive equation. In this paper, researchers survey the various methods available to solve traveling salesman or network problem but analyze arrow drawing method to make critical evaluation of their time complexities. Hence using arrow drawing method to computing the shortest and longest path between two given locations in a road network is an important and simplest way to find applications in various map services. An implementation of the traveling salesman or a road network problem using dynamic programming is presented in this paper which generates optimal answer.

Keywords:
Arrow drawing method, dynamic programming, network, operation research, recursion equation.

Article Details

How to Cite
KENEA, T. K. (2021). SOLVING SHORTEST ROUTE USING DYNAMIC PROGRAMMING PROBLEM. Asian Journal of Mathematics and Computer Research, 28(2), 27-33. Retrieved from https://ikpresse.com/index.php/AJOMCOR/article/view/6448
Section
Original Research Article

References

Liang S, Fuhrman S, Somogyi R. REVEAL, a general reverse engineering algorithm for inference of genetic network architectures,” in 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. Journal of Computational Biology. 2000;7(3-4):601–620.

Imoto S, Kim S, Goto T, et al. Bayesian network and nonparametric heteroscedastic regression for nonlinear modeling of genetic network. Journal of Bioinformatics and Computational Biology. 2003;1(2):231–252.

Liu TF, Sung WK, Mittal A. Learning gene network using time-delayed Bayesian network. International Journal on Artificial Intelligence Tools. 2006;15(3):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, et al. ARACNE: an algorithm for the reconstruction of gene regulatory networks in a mammalian cellular context. BMC Bioinformatics. 2006;8(Supplement 1):1, article S7.

Kimura S, Nakayama S, Hatakeyama M. Genetic network inference as a series of discrimination tasks. Bioinformatics. 2009;25(7):918–925.

Network Completion Using Dynamic Programming and Least-Squares Fitting by Natsu Nakajima et. Al; 2012;9.
Available:https://doi.org/10.1100/2012/957620

Akutsu T, Tamura T, Horimoto K. Completing networks using observed data. Lecture Notes in Artificial Intelligence. 2009;5809:126–140.

Kau ffman SA. The origins of order: self-organization and selection in evolution, Oxford University Press, New York, NY, USA; 1993.

Halpern J, Priess I. Shortest path with time constraints on movement and parking. Networks. 1974;4:241-253

Tamura T, Yamanishi Y, Tanabe M, et al. Integer programming-based method for completing signaling pathways and its application to analysis of colorectal cancer. Genome Informatics. 2010;24:193–203.