Minimize daily route
Hello everybody,
I need help at an program-task I want to solve. It's more a logical question than a programming question.
The problem is:
A hiker wants to make a hiking tour over a few days. On the route are resting places with a distance to each other. He wants to plan the route, so that the maximal daily route is minimal. An example:
3 days, 6 stages, 59 km,
O--11km--O--16km--O--5km--O--5km--O--12km--O--10km--O
The O's are the resting places, the numbers are the distance between them. So here is the answer 16+5+5 = 26. I want to program it with C++ and dont know how to start. Should I go through every permutation or is there an easier way? Would be glad, if someone could help me.
I need help at an program-task I want to solve. It's more a logical question than a programming question.
The problem is:
A hiker wants to make a hiking tour over a few days. On the route are resting places with a distance to each other. He wants to plan the route, so that the maximal daily route is minimal. An example:
3 days, 6 stages, 59 km,
O--11km--O--16km--O--5km--O--5km--O--12km--O--10km--O
The O's are the resting places, the numbers are the distance between them. So here is the answer 16+5+5 = 26. I want to program it with C++ and dont know how to start. Should I go through every permutation or is there an easier way? Would be glad, if someone could help me.
The problem is known as Travelling salesman problem -- https://en.wikipedia.org/wiki/Travelling_salesman_problem
some cases require checking every permutation.
the best non full check solution I ever came up with was this:
run the greedy algorithm from each node. This removes a number of bad choices that can fool the greedy algorithm. There are still cases that fool it, but it does pretty well.
the best non full check solution I ever came up with was this:
run the greedy algorithm from each node. This removes a number of bad choices that can fool the greedy algorithm. There are still cases that fool it, but it does pretty well.
Topic archived. No new replies allowed.