Sciresol Sciresol https://indjst.org/author-guidelines Indian Journal of Science and Technology 0974-5645 10.17485/IJST/v15i31.1342 research article Solving Shortest Route Using Dynamic Programming Problem Kiros Kenea Tadios kirostadios@gmail.com 1 Department Of Mathematics, Arbaminch University Arbaminch Ethiopia 15 31 1527 20 7 2021 26 5 2022 2022 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 Article Processing Charge is partially deferred by Indian Society for Education and Environment
Introduction

Dynamic programming determines the optimum solution of a multivariable problem by decomposing it into stages, each stage is comprising of a single variable sub problem. The advantage of the decomposition is that the optimization process at each stage involves one variable only, a simpler task computationally then dealing with all the variables simultaneously. A dynamic programming model is basically a recursive equation linking the different stages of the problem in a manner that guarantees that each stage’s optimal feasible solution is also optimal and feasible for entire problem. Analysis of biological networks is one of the central research topics in computational systems biology. A Bayesian network is a graph-based model of joint multivariate probability distributions that captures properties of conditional independence between variables. Such models are attractive for their ability to describe complex stochastic processes and because they provide a clear methodology for learning from (noisy) observations. We start by showing how Bayesian networks can describe interactions between genes. Suppose that the given set of gens g1, g2,….,  gm form a regulatory network, where each node of the network is represented by gene. Associated each node, gm is a random variable Xm with unknown steady-state distribution from which the expression of gm are generated. We assume that for gene gm, where Xm,nis the gene expression of gene gm under condition n. In particular, extensive studies have been done on inference of genetic networks using gene expression time series data, and a number of computational methods have been proposed, which include methods based on Boolean networks 1, 2, Bayesian networks 3, 4, time-delayed Bayesian networks 5, mutual information 6, 7, and linear classification 8. However, there is not yet an established or standard method for inference of genetic networks, and thus it still remains a challenging problem.

Network completion is, given an initial network and an observed dataset, to modify the network by the minimum amount of modifications so that the resulting network is (most) consistent with the observed data. Since we were interested in inference of signaling networks in our previous study 9, we assumed that activity levels or quantities of one or a few kinds of proteins can only be observed. Furthermore, since measurement errors were considered to be large, and we were interested in theoretical analysis of computational complexity and sample complexity, we adopted the Boolean network10 as a model of signaling networks. In a paper by Halpern and Priess11 an algorithm is presented for finding a shortest path problem with time constraints on movement and parking. It is assumed that some arcs are closed for travelling during specified periods of time and parking in the vertices of the network is permitted when it is necessary to wait for an arc to be opened. We proved that network completion is computationally intractable even for tree-structured networks. In order to cope with this computational difficulty, we developed an integer linear programming-based method for completion of signaling pathways 12. However, this method could not handle addition of edges because of its high computational cost. To make survey the various methods/techniques available to solve traveling salesman problem 13 and analyze arrow drawing method to make critical evaluation of their time complexities. Arrow drawing method is simple and short time taking to solve the dynamic programming problem compared to recursive equation. When we apply the forward or backward recursive equation method for the given dynamic programming problem of salesman route, we lose time and complicate to construct the table to find optimal solution.

Method

In this study, we survey the various methods/techniques available to solve traveling salesman problem and analyze arrow drawing method to make critical evaluation their time complexities. Recursive equation and arrow drawing methods are the methods used to determine the shortest distance in salesman of dynamic programming problem.

The purpose of network completion is to modify a given network with the minimum number of modifications so that the resulting network is most consistent with the observed data. In this paper, we consider additions and creation of sequence in states through stages as modification operations. To find the path of minimum distance between the point of source to terminal using back ward recursion or forward recursion of dynamic programming can be obtained using the following method.

Assign the initial value of the salesman as zero. i.e the value of the stage f0x0=0

fixi = min{ d( xi-1,  xi) + fi( xi)} , i= 1,2,3,……. or

fixi = min{ d( xi-1,  xi) + fi-1( xi-1)} , i= 1,2,3,…….

let fixi  be the shortest distance to node xi  at stage i, and define d( xi-1,  xi) as the distance from the node xi-1 to node xi , then fi is computed from fi-1using the following forward recursive equation.

fixi = min{ d( xi-1,  xi) + fi-1( xi-1)} , i= 1,2,3,…….

Starting at i = 1 the recursion sets f0x0=0 .

The equation shows that the shortest distances fixi at stage i, must be expressed in terms of the next node xi . In the dynamic programming terminology, xi is referred to as state of the system at stage i. In effect, the state of the system at stage i, is the information that links the stages together, so that optimal decisions for the remaining stages can be made without reexamining how the decisions for the previous stages are reached. The proper definition of the state allows us to consider each stage separately and guarantee that the solution is feasible for all the stages. The definition of the state leads to the following unifying framework for dynamic programming.

Example

A salesman located in a city A decides to travel city J. He knew the distances of alternative routes from city A to city J, then he drew a high way network map as shown in the figure below. The city of origin is A and the destination city is J. Other cities through which the salesman will have to pass through are named B to I. The arrow is representing routes between cities and distances in kilometers are indicated on each route. The salesman problem is to find shortest route from A to J. Use dynamic programming to solve it.

In the figure above the circular regions are cities and a numbers in the arrows are distance between the cities in kilometer.

The back ward recursive equation is

fi(xi) =min{d( xi,xi+1)+fi+1(xi+1)}, i=1,2,…..,n and d is distance between xi and xi+1

fn(xn)=0

f5(x5)=0

Stage :4

 x4 d( x4,x5)+  f5(x5) x5=J=0 Optimal solution f4(x4) x5’ H 7+0 7 J I 9+0 9 J

Stage :3

 x3 d( x3,x4)+  f4(x4) x4=H x4=I Optimal solution f3(x3) x4’ E 7+4=11 8+9=17 11 H F 7+3=10 7+9=16 10 H G 7+8=15 13 I

Stage:2

 x2 d( x2,x3)+  f3(x3) x3=E x3=F x3=G Optimal solution f2(x2) x3’ B 11+7=18 10+10=20 13+5=18 18 E,G C 11+3=14 10+8=18 13+4=17 14 E D 11+6=17 10+10=20 13+5=18 17 E

Stage :1

 x1 d( x1,x2)+  f2(x2) x2=B x2=C x2=D Optimal solution f2(x2) x3’ A 18+4=22 14+6=20 17+3=20 20 C,D Therefore, the minimum distance is 20. i.e f1(x1)=20

New method to solve dynamic programming problem

using arrow drawing method

When using arrow drawing method we can determine the shortest and longest paths in each stages but our target is to get the shortest path. Arrow drawing method is simple and short time taking to solve the dynamic programming problem compared to recursive equation. When we apply the forward or backward recursive equation method for the given dynamic programming problem of salesman route, we lose time and complicate to construct the table to find optimal solution.

Hence Adk represents Arrow drawing k sequence, Sij represents each states.

Adk= Sij +…+ Smn, where i=1,2,…, m and j= 1,2,…,n , k= number of arrow drawing sequences, where i represents stage and j represents each state.

fi( xi) = min { i=1mSij where j=1, … , n} is the way to find optimal solution.

Ad1. S11 S12 S13 … …  S1n

Ad2. S21 S22 S23 … … S2n

Ad3. S31 S32 S33 … … S3n

.... ... ...

Adk. Sm1 Sm2 Sm3 …. … Smn

fi( xi) = min { i=1mSij where j=1, … , n} is optimal solution.

Example1. A salesman located in a city A decides to travel city J. He knew the distances of alternative routes from city A to city J, then he drew a high way network map as shown in the figure below. The city of origin is A and the destination city is J. Other cities through which the salesman will have to pass through are named B to I. The arrow is representing routes between cities and distances in kilometers are indicated on each route. The salesman problem is to find shortest route from A to J. Use dynamic programming to solve it.

Solution

Using Arrow Drawing Method

Ad1. S11 S12 S13 … …  S1n

Ad2. S21 S22 S23 … … S2n

Ad3. S31 S32 S33 … … S3n

.... ... ...

Adm. Sm1 Sm2 Sm3 …. … Smn

fi( xi) = min { i=1mSij where j=1, … , n} is optimal solution.

fi( xi) = min { i=1mSij where j=1, … , n} is 20 optimal solution.

There fore fi( xi) = 20 is optimal solution, the sequence

A 6 C 3 E 4 H 7 J = 20 and A 3 D 6 E 4 H 7 J = 20 is shortest route.

Discussion and results

The value of certain dynamic shortest route among the cities from A to J is 20. The recursive procedure described four different tables which is taken at least 23 lines, time taking and complex to achieve solution but as we have seen the modified method cover 19 lines, time saving and simpler even if we compared in line coverage, time and the way of solving so here was carried out from A to J. Those the same procedure is often utilized in the reverse direction from J to A which leads to an equivalent solution by backward recursion. Hence using arrow drawing method to computing the shortest and longest path between two given location in salesman problem is an important and simplest way that to find applications in various map services. An implementation of the traveling salesman problem using dynamic programming is presented in this paper which generates optimal answer. So these forward and backward recursive methods take time and complex to find optimal solution 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 methods. Fundamentally, it consists of finding optimal solution and cumulating these through various cities and stages until optimal shortest route is found large number of algorithms available to solve the dynamic shortest route problem.

Conclusion

To solve the traveling salesman route we apply the recursive equation (either forward or backward recursive). It is taking long time and very complicate if a number of states are many to get the shortest distance of salesman problem in dynamic programming problem. So that it is better to apply arrow draw method to determine the shortest distance and to take short time for solving the given problem compared to recursive equation. We can see not only the shortest distance of route but also able to identify the longest distance that helps us not to use this longest one to minimize the cost.

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 1367-4803 Oxford University Press (OUP) Friedman Nir Linial Michal Nachman Iftach Pe&apos;er Dana Using Bayesian networks to analyze expression data Proceedings of the fourth annual international conference on Computational molecular biology - RECOMB '00 2000 7 601 620 ACM Press Imoto S Kim Sunyong Goto T Aburatani S Tashiro K Kuhara S Miyano S Bayesian network and nonparametric heteroscedastic regression for nonlinear modeling of genetic network Proceedings. IEEE Computer Society Bioinformatics Conference 2003 1 231 252 IEEE Comput. Soc Liu Tie-Fei F Sung Wing-Kin K Mittal Ankush Learning gene network using time-delayed Bayesian network International Journal on Artificial Intelligence Tools 2006 15 03 353 370 0218-2130 World Scientific Pub Co Pte Lt Margolin Adam A Wang Kai Lim Wei Keat Kustagi Manjunath Nemenman Ilya Califano Andrea Reverse engineering cellular networks Nature Protocols 2006 1 2 662 671 1754-2189 Springer Science and Business Media LLC Margolin Adam A Nemenman Ilya Basso Katia Wiggins Chris Stolovitzky Gustavo Favera Riccardo Dalla Califano Andrea ARACNE: An Algorithm for the Reconstruction of Gene Regulatory Networks in a Mammalian Cellular Context BMC Bioinformatics 2006 7 S1 Springer Science and Business Media LLC Kimura Shuhei Nakayama Satoshi Hatakeyama Mariko Genetic network inference as a series of discrimination tasks Bioinformatics 2009 25 7 918 925 1367-4803 Oxford University Press (OUP) Akutsu Tatsuya Tamura Takeyuki Horimoto Katsuhisa Completing Networks Using Observed Data Lecture Notes in Computer Science 2009 5809 126 140 Springer Berlin Heidelberg Kau Ffman S A The Origins of Order: Self-Organization and Selection in Evolution Oxford University Press New York, NY, USA 1993 Halpern I J Priess Shortest path with time constraints on movement and parking 1974 4 241 253 Tamura Takeyuki Yamanishi Yoshihiro Tanabe Mao Goto Susumu Kanehisa Minoru Horimoto Katsuhisa Akutsu Tatsuya Integer programming-based method for completing signaling pathways and its application to analysis of colorectal cancer Genome Informatics 2010 2010 24 193 203 IMPERIAL COLLEGE PRESS Lewis R Algorithms for Finding Shortest Paths in Networks with Vertex Transfer Penalties Algorithms 2020 13 11 269 269 MDPI AG