Mixing
travelling salesman calculate route
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
A computer program takes 0.00075 seconds to calculate the best route between five cities using a brute-force approach to the travelling salesman problem. How long, to the nearest second, will it take to calculate the best route for ten cities?
algorithms
asked Jul 26 at 10:12
MackyLasmu
81
add a comment |Â
up vote
0
down vote
favorite
A computer program takes 0.00075 seconds to calculate the best route between five cities using a brute-force approach to the travelling salesman problem. How long, to the nearest second, will it take to calculate the best route for ten cities?
algorithms
asked Jul 26 at 10:12
MackyLasmu
81
Probably $frac_10 C_2_5 C_2 cdot 0.00075$
– Kenta S
Jul 26 at 10:15
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
A computer program takes 0.00075 seconds to calculate the best route between five cities using a brute-force approach to the travelling salesman problem. How long, to the nearest second, will it take to calculate the best route for ten cities?
algorithms
asked Jul 26 at 10:12
MackyLasmu
81
A computer program takes 0.00075 seconds to calculate the best route between five cities using a brute-force approach to the travelling salesman problem. How long, to the nearest second, will it take to calculate the best route for ten cities?
algorithms
asked Jul 26 at 10:12
MackyLasmu
81
asked Jul 26 at 10:12
MackyLasmu
81
asked Jul 26 at 10:12
MackyLasmu
81
asked Jul 26 at 10:12
MackyLasmu
81
81
Probably $frac_10 C_2_5 C_2 cdot 0.00075$
– Kenta S
Jul 26 at 10:15
add a comment |Â
Probably $frac_10 C_2_5 C_2 cdot 0.00075$
– Kenta S
Jul 26 at 10:15
Probably $frac_10 C_2_5 C_2 cdot 0.00075$
– Kenta S
Jul 26 at 10:15
Probably $frac_10 C_2_5 C_2 cdot 0.00075$
– Kenta S
Jul 26 at 10:15
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
2
down vote
accepted
Think about how the algorithm scales with $n$ if you must search all combinations of paths.
For two cities, if we start in city 1 and go to 2 then we have one combination
$$
12
$$
for three cities there are two routes
$$
123,132
$$
for four there are $6$
$$
1234,1243,1324,1342,1423,1432
$$
so for $n$ cities the result depends on the numbers of permutations of $n-1$ digits, (given that we start in city 1)
If the algorithm scaled like $O(n!)$ for example, where $n$ is the number of cities, then you could consider
$$
T_5 = acdot4! = a*(24 text paths) = 0.00075 \
a=1/32000 \
T_10 = a cdot 9! = 11.34 text seconds
$$
answered Jul 26 at 10:17
Benedict W. J. Irwin
1,403528
1
This assumes that testing one path takes the same time no matter how long it is. (Which is actually true up to a constant factor if the brute-force search is implemented with a bit of care, but that is not really obvious). Even so, "$11.34$" is an impressively precise answer given that the input to the problem gave only two significant digits ...
– Henning Makholm
Jul 26 at 10:35
@HenningMakholm Thank you for your comments, they are important considerations. The question gave no error tolerance. My answer assumes perfect precision and I have left it up to the OP to round to the nearest second. You are correct that this is an approximation.
– Benedict W. J. Irwin
Jul 26 at 12:28
add a comment |Â
up vote
0
down vote
For ten cities the time taken will be 0.00075 x 5 x 6 x 7 x 8 x 9 = 11.34 seconds = 11 seconds (to the nearest second).
answered Aug 2 at 15:09
MackyLasmu
81
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
Think about how the algorithm scales with $n$ if you must search all combinations of paths.
For two cities, if we start in city 1 and go to 2 then we have one combination
$$
12
$$
for three cities there are two routes
$$
123,132
$$
for four there are $6$
$$
1234,1243,1324,1342,1423,1432
$$
so for $n$ cities the result depends on the numbers of permutations of $n-1$ digits, (given that we start in city 1)
If the algorithm scaled like $O(n!)$ for example, where $n$ is the number of cities, then you could consider
$$
T_5 = acdot4! = a*(24 text paths) = 0.00075 \
a=1/32000 \
T_10 = a cdot 9! = 11.34 text seconds
$$
answered Jul 26 at 10:17
Benedict W. J. Irwin
1,403528
1
This assumes that testing one path takes the same time no matter how long it is. (Which is actually true up to a constant factor if the brute-force search is implemented with a bit of care, but that is not really obvious). Even so, "$11.34$" is an impressively precise answer given that the input to the problem gave only two significant digits ...
– Henning Makholm
Jul 26 at 10:35
@HenningMakholm Thank you for your comments, they are important considerations. The question gave no error tolerance. My answer assumes perfect precision and I have left it up to the OP to round to the nearest second. You are correct that this is an approximation.
– Benedict W. J. Irwin
Jul 26 at 12:28
add a comment |Â
up vote
2
down vote
accepted
Think about how the algorithm scales with $n$ if you must search all combinations of paths.
For two cities, if we start in city 1 and go to 2 then we have one combination
$$
12
$$
for three cities there are two routes
$$
123,132
$$
for four there are $6$
$$
1234,1243,1324,1342,1423,1432
$$
so for $n$ cities the result depends on the numbers of permutations of $n-1$ digits, (given that we start in city 1)
If the algorithm scaled like $O(n!)$ for example, where $n$ is the number of cities, then you could consider
$$
T_5 = acdot4! = a*(24 text paths) = 0.00075 \
a=1/32000 \
T_10 = a cdot 9! = 11.34 text seconds
$$
answered Jul 26 at 10:17
Benedict W. J. Irwin
1,403528
1
This assumes that testing one path takes the same time no matter how long it is. (Which is actually true up to a constant factor if the brute-force search is implemented with a bit of care, but that is not really obvious). Even so, "$11.34$" is an impressively precise answer given that the input to the problem gave only two significant digits ...
– Henning Makholm
Jul 26 at 10:35
@HenningMakholm Thank you for your comments, they are important considerations. The question gave no error tolerance. My answer assumes perfect precision and I have left it up to the OP to round to the nearest second. You are correct that this is an approximation.
– Benedict W. J. Irwin
Jul 26 at 12:28
add a comment |Â
up vote
2
down vote
accepted
up vote
2
down vote
accepted
Think about how the algorithm scales with $n$ if you must search all combinations of paths.
For two cities, if we start in city 1 and go to 2 then we have one combination
$$
12
$$
for three cities there are two routes
$$
123,132
$$
for four there are $6$
$$
1234,1243,1324,1342,1423,1432
$$
so for $n$ cities the result depends on the numbers of permutations of $n-1$ digits, (given that we start in city 1)
If the algorithm scaled like $O(n!)$ for example, where $n$ is the number of cities, then you could consider
$$
T_5 = acdot4! = a*(24 text paths) = 0.00075 \
a=1/32000 \
T_10 = a cdot 9! = 11.34 text seconds
$$
answered Jul 26 at 10:17
Benedict W. J. Irwin
1,403528
Think about how the algorithm scales with $n$ if you must search all combinations of paths.
For two cities, if we start in city 1 and go to 2 then we have one combination
$$
12
$$
for three cities there are two routes
$$
123,132
$$
for four there are $6$
$$
1234,1243,1324,1342,1423,1432
$$
so for $n$ cities the result depends on the numbers of permutations of $n-1$ digits, (given that we start in city 1)
If the algorithm scaled like $O(n!)$ for example, where $n$ is the number of cities, then you could consider
$$
T_5 = acdot4! = a*(24 text paths) = 0.00075 \
a=1/32000 \
T_10 = a cdot 9! = 11.34 text seconds
$$
answered Jul 26 at 10:17
Benedict W. J. Irwin
1,403528
edited Jul 26 at 10:25
answered Jul 26 at 10:17
Benedict W. J. Irwin
1,403528
answered Jul 26 at 10:17
Benedict W. J. Irwin
1,403528
answered Jul 26 at 10:17
Benedict W. J. Irwin
1,403528
1,403528
1
This assumes that testing one path takes the same time no matter how long it is. (Which is actually true up to a constant factor if the brute-force search is implemented with a bit of care, but that is not really obvious). Even so, "$11.34$" is an impressively precise answer given that the input to the problem gave only two significant digits ...
– Henning Makholm
Jul 26 at 10:35
@HenningMakholm Thank you for your comments, they are important considerations. The question gave no error tolerance. My answer assumes perfect precision and I have left it up to the OP to round to the nearest second. You are correct that this is an approximation.
– Benedict W. J. Irwin
Jul 26 at 12:28
add a comment |Â
1
This assumes that testing one path takes the same time no matter how long it is. (Which is actually true up to a constant factor if the brute-force search is implemented with a bit of care, but that is not really obvious). Even so, "$11.34$" is an impressively precise answer given that the input to the problem gave only two significant digits ...
– Henning Makholm
Jul 26 at 10:35
@HenningMakholm Thank you for your comments, they are important considerations. The question gave no error tolerance. My answer assumes perfect precision and I have left it up to the OP to round to the nearest second. You are correct that this is an approximation.
– Benedict W. J. Irwin
Jul 26 at 12:28
1
1
This assumes that testing one path takes the same time no matter how long it is. (Which is actually true up to a constant factor if the brute-force search is implemented with a bit of care, but that is not really obvious). Even so, "$11.34$" is an impressively precise answer given that the input to the problem gave only two significant digits ...
– Henning Makholm
Jul 26 at 10:35
This assumes that testing one path takes the same time no matter how long it is. (Which is actually true up to a constant factor if the brute-force search is implemented with a bit of care, but that is not really obvious). Even so, "$11.34$" is an impressively precise answer given that the input to the problem gave only two significant digits ...
– Henning Makholm
Jul 26 at 10:35
@HenningMakholm Thank you for your comments, they are important considerations. The question gave no error tolerance. My answer assumes perfect precision and I have left it up to the OP to round to the nearest second. You are correct that this is an approximation.
– Benedict W. J. Irwin
Jul 26 at 12:28
@HenningMakholm Thank you for your comments, they are important considerations. The question gave no error tolerance. My answer assumes perfect precision and I have left it up to the OP to round to the nearest second. You are correct that this is an approximation.
– Benedict W. J. Irwin
Jul 26 at 12:28
add a comment |Â
up vote
0
down vote
For ten cities the time taken will be 0.00075 x 5 x 6 x 7 x 8 x 9 = 11.34 seconds = 11 seconds (to the nearest second).
answered Aug 2 at 15:09
MackyLasmu
81
add a comment |Â
up vote
0
down vote
For ten cities the time taken will be 0.00075 x 5 x 6 x 7 x 8 x 9 = 11.34 seconds = 11 seconds (to the nearest second).
answered Aug 2 at 15:09
MackyLasmu
81
add a comment |Â
up vote
0
down vote
up vote
0
down vote
For ten cities the time taken will be 0.00075 x 5 x 6 x 7 x 8 x 9 = 11.34 seconds = 11 seconds (to the nearest second).
answered Aug 2 at 15:09
MackyLasmu
81
For ten cities the time taken will be 0.00075 x 5 x 6 x 7 x 8 x 9 = 11.34 seconds = 11 seconds (to the nearest second).
answered Aug 2 at 15:09
MackyLasmu
81
answered Aug 2 at 15:09
MackyLasmu
81
answered Aug 2 at 15:09
MackyLasmu
81
answered Aug 2 at 15:09
MackyLasmu
81
81
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2863286%2ftravelling-salesman-calculate-route%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Probably $frac_10 C_2_5 C_2 cdot 0.00075$
– Kenta S
Jul 26 at 10:15