f



Travelling Santa Problem

More programming than C, but seasonal.

Santa has a long list of children with presents. As he visits houses, presents are dropped off, and thus the sleigh is lighter and travels faster.

The task is to deliver as many presents as possible in one night.

Is this just the travelling salesman problem, or does it have characteristics which make it easier / more difficult?
0
Malcolm
12/25/2016 2:01:50 AM
comp.lang.c 30657 articles. 3 followers. spinoza1111 (3246) is leader. Post Follow

2 Replies
3014 Views

Similar Articles

[PageSpeed] 38

On Sunday, December 25, 2016 at 7:31:57 AM UTC+5:30, Malcolm McLean wrote:
> More programming than C, but seasonal.
> 
> Santa has a long list of children with presents. As he visits houses, presents are dropped off, and thus the sleigh is lighter and travels faster.
> 
> The task is to deliver as many presents as possible in one night.
> 
> Is this just the travelling salesman problem, or does it have characteristics which make it easier / more difficult?

Fantastic Malcolm.
another new problem. appreciate you.
I think it is bigger than the traveling sales man problem. because the station where to stop are limited in salesman case.
but here you posed similar problem for "Santa".
Really funny but good. like it.

We have to use divide and conquer strategy. each instance is itself a small sales-man problem.


Please inform me if you solved that. we will trying. and keep posting the funny cum intelligent problem.
0
Krunalkumar
12/25/2016 3:41:27 AM
El 25/12/16 a las 03:01, Malcolm McLean escribió:
> More programming than C, but seasonal.
>
> Santa has a long list of children with presents. As he visits houses, presents are dropped off, and thus the sleigh is lighter and travels faster.
>
> The task is to deliver as many presents as possible in one night.
>
> Is this just the travelling salesman problem, or does it have characteristics which make it easier / more difficult?
>

More difficult. Instead of having a distance array of n*(n-1)/2 
distances, you have t**n arrays of times in wich t[3][2] != t[2][3].
Seems solvable as far as TSP is (not).

-- 
http://gamo.eu.pn/
Do not mix your decrepitude with that of the world.
Different racing teams.
0
gamo
12/25/2016 4:21:23 AM
Reply: