0
$\begingroup$

I need to implement TSP algorithm by brute force for learning purposes.

I've understood there's a set of cities, let's call it V and it's possible to get a matrix representation for the costs for going from a v1 city to a v2 city. I'll assume there are not cycles, so it's no possible to going from v1 back to v1

Then, I should generate a matrix after these sum series:

Formulas

However, I really can't see in a practice way how a matrix would be outputed from restrictions.

Let's say we got 3 cities:

Madrid, Berlin and Malmo

So the path costs are (and they're not forced to be the same for ways back):

From Madrid to:

Berlin: 12
Malmo: 20

From Berlin to

Madrid: 32
Malmo: 12

From Malmo to:

Madrid: 14
Berlin: 17

So my input is:

$$\begin{bmatrix} 0 & 12 & 20 \\ 32 & 0 & 12 \\ 14 & 17 & 0\end{bmatrix}$$

How should the matrix be outputed according to the sum series?

I assume the algorithm would need to generate a matrix from this exampple:

There are 3 cities x1, x2 and x3 and got the costs matrix shown below:

$$\begin{bmatrix} 10 & 2 & 1 \\ 3 & 10 & 2 \\ 11 & 2 & 10\end{bmatrix}$$

Following, example shows the next matrix:

$$\begin{bmatrix} x_{11}+x_{12}+x_{13} & & \\ & x_{21}+x_{22}+x_{23} & \\ & & x_{31}+x_{32}+x_{33}\\x_{11} & x_{21} & x_{31} \\ x_{12} & x_{22} & x_{32} \\ x_{13}& x_{23} & x_{33} \end{bmatrix}$$

Which would be the same as:

$$\begin{bmatrix} 1&1&1&0&0&0&0&0&0\\ 0&0&0&1&1&1&0&0&0\\ 0&0&0&0&0&0&1&1&1\\ 1&0&0&1&0&0&0&1&0\\ 0&0&1&0&0&1&0&0&1\\ 0&1&0&0&1&0&0&1&0\\ \end{bmatrix}$$

Then, considering the power ser of the three cities, matrix got the following rows added:

$$\begin{bmatrix} 0&1&1 & 0&0&0 & 0&0&0 \\ 0&0&0 & 1&0&1 & 0&0&0 \\ 0&0&0 & 0&0&0 & 1&1&0 \\ 0&0&1 & 0&0&1 & 0&0&0 \\ 0&1&0 & 0&0&0 & 0&1&0 \\ 0&0&0 & 1&0&0 & 1&0&0 \end{bmatrix}$$

Finally, the whole generated matrix is:

$$\begin{bmatrix} 1&1&1&0&0&0&0&0&0\\ 0&0&0&1&1&1&0&0&0\\ 0&0&0&0&0&0&1&1&1\\ 1&0&0&1&0&0&0&1&0\\ 0&0&1&0&0&1&0&0&1\\ 0&1&0&0&1&0&0&1&0\\ 0&1&1 & 0&0&0 & 0&0&0 \\ 0&0&0 & 1&0&1 & 0&0&0 \\ 0&0&0 & 0&0&0 & 1&1&0 \\ 0&0&1 & 0&0&1 & 0&0&0 \\ 0&1&0 & 0&0&0 & 0&1&0 \\ 0&0&0 & 1&0&0 & 1&0&0 \end{bmatrix}$$

$\endgroup$
  • 1
    $\begingroup$ I can't follow your question anymore after the edit. What does the final matrix represent even? $\endgroup$ – Juho Nov 18 '13 at 20:41
  • $\begingroup$ That's exactly my question $\endgroup$ – diegoaguilar Nov 19 '13 at 20:01
2
$\begingroup$

I don't think you should build your matrix according to the integer program, but rather the distance matrix is given as input.

Label your cities in some way, for example let $1$ be Madrid, $2$ be Berlin, and $3$ be Malmo. In your matrix, the entry $(i,j)$ will contain the distance from the city $i$ to city $j$. So you'll get a $3 \times 3$ matrix with zeros on the diagonal (the distance from Madrid to Madrid is zero):

$$\begin{bmatrix} 0 & 12 & 20 \\ 32 & 0 & 12 \\ 14 & 17 & 0\end{bmatrix}$$

Notice that the matrix would be symmetric, if the distance from city $i$ to $j$ would equal the distance from $j$ to $i$.

$\endgroup$
  • $\begingroup$ Ok, but that's just the input. What about the sum series which actually makes the algorithm? $\endgroup$ – diegoaguilar Nov 17 '13 at 21:11
  • 2
    $\begingroup$ The "sum series" don't make an algorithm; they just describe the problem. Your output is not a matrix: look at the objective function, what will that give you? Do you understand the problem? Do you understand the integer program formulation? $\endgroup$ – Juho Nov 17 '13 at 21:18
  • $\begingroup$ Ok output is not a matrix, that would be actually the cities sequece which represent the lowest cost. Then I don't see how should the algorithm be completed $\endgroup$ – diegoaguilar Nov 17 '13 at 21:52
2
$\begingroup$

You write: "I should generate a matrix given by..." That seems to come out of nowhere. You didn't explain why you think that is the way to solve this problem.

Anyway, if you want to solve it by exhaustive search, that's not the way to solve the problem. Exhaustive search means something different. It means you enumerate all possible solutions, compute how good each one is, and keep the best one.

Do you know what the set of possible solutions is? What does a possible solution look like? That would be a good place for you to start. Then, you should double-check that you know how to measure how good a possible solution is. From there, the solution should be straightforward.

$\endgroup$
  • $\begingroup$ You are right about your argument, I've just edited question and express why speak about a matrix. $\endgroup$ – diegoaguilar Nov 18 '13 at 19:23
  • 1
    $\begingroup$ @Diego, I don't see anything that changes what I wrote. You're still assuming that your approach should be to generate some matrix, but this assumption is neither justified nor accurate. For instance, your edited question says "Then, I should generate a matrix..." Wait, why? That still comes out of the blue. You never say why you think you should generate a matrix. Well, as I write in my answer, the real answer is: no you shouldn't. It looks to me you took a false path early in your reasoning, by assuming your task is to generate a matrix: you might want to re-read my answer another time.... $\endgroup$ – D.W. Nov 20 '13 at 2:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.