Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #100364

Re: Travelling Santa Problem

Show all headers | View raw

gamo <gamo@telecable.es> writes:

> 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].

Well, that's one way to model it. 

There are some considerations being ignored there which I would also
ignore.  The most obvious of these is acceleration (and higher order
derivatives), which is not linear with weight -- you might as well treat
it as infinite, since it's going to smear anything resembling Earth
mammals into jelly anyway.

Rather than calculate a lot more tables based on different leg start
times, I think it would be better to explore the distance map keeping
elapsed time (or number of stops). That representation, aside from being
more compact, lends itself to branch-and-bound techniques and simplex
techniques, but wouldn't be a good fit with quantum techniques, if we
ever develop such.

> Seems solvable as far as TSP is (not).

Well, kind of. The TSP is solvable by complete enumeration, so that in
theory we know how to solve it with any number of nodes. In practice,
because it's more-than-polynomial in complexity, we can easily show that
calculating it hundreds of millions of nodes would require computing
resources that couldn't possibly be provided in this galaxy. This is
known as the "I don't care about NP-completeness, I said *infinite*
resources!" argument, and its primary purpose is to have geeky fun
chatting about elves flying to every home in the world in one night.

Comparing this problem to a standard version of the TSP is the right way
to look at it, and it does indicate that this one is at least as
hard. There's a simple proof: any solution to the problem has to include
*at least* all of the calculations needed to solve the normal travelling
salesman problem. I haven't thought it all the way through, but I think
that the additional constraint changes the dominant terms in the
complexity equation only by linear coefficients, not in the exponents,
so in computer science terms, it doesn't change the theoretical order of
difficulty. I think.

Be well.
-- 
Lowell Gilbert, embedded/networking software engineer
	 http://be-well.ilk.org/~lowell/

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Travelling Santa Problem Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-12-24 18:01 -0800
  Re: Travelling Santa Problem Krunalkumar Shah <einstein1410@gmail.com> - 2016-12-24 19:41 -0800
  Re: Travelling Santa Problem gamo <gamo@telecable.es> - 2016-12-25 05:21 +0100
    Re: Travelling Santa Problem Lowell Gilbert <lgusenet@be-well.ilk.org> - 2016-12-27 17:05 -0500
  Re: Travelling Santa Problem Gareth Owen <gwowen@gmail.com> - 2016-12-26 19:55 +0000
    Re: Travelling Santa Problem "Chris M. Thomasson" <invalid@invalid.invalid> - 2016-12-26 14:49 -0800
      Re: Travelling Santa Problem "Chris M. Thomasson" <invalid@invalid.invalid> - 2016-12-27 14:36 -0800
  Re: Travelling Santa Problem Tim Rentsch <txr@alumni.caltech.edu> - 2016-12-29 00:20 -0800
  Re: Travelling Santa Problem "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2016-12-29 21:09 +0800
    Re: Travelling Santa Problem Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-12-29 05:10 -0800
      Re: Travelling Santa Problem "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2016-12-29 21:51 +0800
        Re: Travelling Santa Problem luser droog <luser.droog@gmail.com> - 2016-12-29 05:56 -0800
          Usenet newsgroups about mathematics "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2016-12-31 14:44 +0800
      Re: Travelling Santa Problem Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-12-29 14:35 +0000
  Re: Travelling Santa Problem Ken Brody <kenbrody@spamcop.net> - 2016-12-30 11:38 -0500

csiph-web