Adding Elements in a Matrix

[omario]

I found this link that shows you how to make a matrix with random numbers: How to create a matrix with random values in R?

  #random symmetric matrix with diagnoal elements as 0
 A <- matrix(runif(16), 4, 4)
A1 = A %*% t(A)

out_1 = A1 - diag(diag(A1))

         [,1]     [,2]     [,3]     [,4]
[1,]     0.00 20371.54 19136.91 18380.49
[2,] 20371.54     0.00 19392.13 19476.78
[3,] 19136.91 19392.13     0.00 16651.73
[4,] 18380.49 19476.78 16651.73     0.00

• Imagine each index corresponds to a city in this matrix (out_1) - there are 4 cities.
• Any (row , column) combination corresponds to the distance between two cities (e.g. [2][3] corresponds to the distance between city 2 and city 3).
• Logically, the distance between the same two cities is the same, e.g.. [2] [3] = [3] [2]
• Logically, the distance between a city and itself is 0, e.g. [2] [2] = 0

Using this matrix (out_1), I want to calculate all "paths" from this matrix that have the following structure:

• The path must start and end from the same city, and with the exception of the first city, no other city can be visited twice.

For example, the end goal would look something like this:

- Path 1 : [1] [2] , [2] [3], [3] [4], [4] [1] = 20371.54 + 19392.13 + 16651.73 + 18380.49 = 74795.89  
- Path 2 : [2] [4] , [4] [3], [3] [1], [1] [2] = 19476.78 + 16651.73 + 19136.91 + 20371.54 =   75636.96
- ....
- Path n: [3] [4] , [4] [1], [1] [2], [2] [3] =  16651.73 + 18380.49 + 20371.54 + 19392.13 =   74795.89 

I tried to find some library in R to do this (note: I think what I am trying to do is called a "Hamiltonian Cycle of a Graph") : hamiltonian function - RDocumentation

But this did not work:

    c = c(out_1)
 hamiltonian(c, cycle = TRUE)

    Error in graph_vect2list(edges) : 
      Argument 'edges' is not a correct edge list.

How can I get a list of all such "paths" that shows the order of the cities and the total distance for each path?

Thanks!

[FJCC]

Do your paths also have the constraint that all cities must be visited and that all cities are connected? If so, I think this is a problem of generating all of the permutations of 1:4 and calculating the distance of each path represented by those permutations. The package combinat has the function permn that calculates permutations and it can also apply a function to the permutations. Is calculating the permutations and their distances what you need to do?

[pieterjanvc]

Hi,

It seems you are working on a problem very similar to the "travelling salesman" one. In this famous problem, you have to find the shortest path between all cities visiting each exactly once. What you are trying to do here is an exhaustive search of this problem by looking at all possible paths, but the combinations will explode rapidly when adding more cities which will result in your program running forever trying to run over all combinations.

The solution to this problem is NP hard, and thus so far no perfect solution has been found that can solve the issue in a reasonable time frame when the number of cities goes up.

Travelling salesman problem

Hope this helps,
PJ