0
$\begingroup$


We are learning about the travelling salesperson problem in my high school class and we are discussing how computers could solve for the problem, even though the problem is intractable, using a brute force algorithm.
I was wondering if the brute force algorithm calculates ALL possibilities for a number, n, or only UNIQUE possibilities.

For example:
If there were 4 locations, labelled A, B, C & D. Starting from A, would you include both A,B,C,D and A,D,C,B even though they are essentially the same?

Thank you for the help :)

$\endgroup$

1 Answer 1

0
$\begingroup$

In the classic variant of the Travelling Salesperson Problem, the distance from X to Y is the same as the distance from Y to X for any two locations X and Y. Hence, as you noticed, an algorithm does not need to distinguish between the two solutions A, B, C, D and A, D, C, B. However, whether a brute force algorithm considers both solutions or not would depend on how exactly it is implemented. Some will and some won't. It is not too much of a waste to consider them both -- after all, it only takes twice the time. And it may be easier to program the algorithm that way.

There is also a so-called asymmetric variant of the Travelling Salesperson Problem where the cost of moving from X to Y is not necessarily the same as the cost of moving from Y to X. Note that in this case, the two solutions A, B, C, D and A, D, C, B are not "essentially the same" anymore and it is important to consider them both.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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