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

Groups > comp.lang.c > #100217 > unrolled thread

Travelling Santa Problem

Back to article view | Back to comp.lang.c

Contents

  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

#100217 — 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?

[toc] | [next] | [standalone]

#100220

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.

[toc] | [prev] | [next] | [standalone]

#100222

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.

[toc] | [prev] | [next] | [standalone]

#100364

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/

[toc] | [prev] | [next] | [standalone]

#100304

Malcolm McLean <malcolm.mclean5@btinternet.com> writes:

> 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?

Also you've made your list, you are obliged to check it twice.

[toc] | [prev] | [next] | [standalone]

#100311

On 12/26/2016 11:55 AM, Gareth Owen wrote:
> Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
>
>> 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?
>
> Also you've made your list, you are obliged to check it twice.

;^)

Actually, this makes me think of something like: What happens if a 
little kid does something really bad right before Santa reaches their 
dwelling?


Travel problem aside for a moment,

Is there any time elapsing from the point of checking the list, and the 
point of checking it again? Imagine if a little kid did something bad 
_in_between_ the first and second observations of the list, well, should 
we check it a third time, or is it atomic? If we need to check another 
time, shall we attach a counter with a limit to the number of times we 
check as to avoid a possible lengthy loop?

This kind of reminds me of transnational memory, where there can be 
live-lock like conditions if other agents keep interfering with 
transactions, causing their commits to seem to "superfluously" fail.

Humm, is this list dynamic, does it evolve with version numbers?

;^)

[toc] | [prev] | [next] | [standalone]

#100365

On 12/26/2016 2:49 PM, Chris M. Thomasson wrote:
> On 12/26/2016 11:55 AM, Gareth Owen wrote:
>> Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
>>
>>> 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?
>>
>> Also you've made your list, you are obliged to check it twice.
>
> ;^)
>
> Actually, this makes me think of something like: What happens if a
> little kid does something really bad right before Santa reaches their
> dwelling?
>
>
> Travel problem aside for a moment,
>
> Is there any time elapsing from the point of checking the list, and the
> point of checking it again? Imagine if a little kid did something bad
> _in_between_ the first and second observations of the list, well, should
> we check it a third time, or is it atomic? If we need to check another
> time, shall we attach a counter with a limit to the number of times we
> check as to avoid a possible lengthy loop?
>
> This kind of reminds me of transnational memory,
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
_Transactional_ memory

damn it!

> where there can be
> live-lock like conditions if other agents keep interfering with
> transactions, causing their commits to seem to "superfluously" fail.
>
> Humm, is this list dynamic, does it evolve with version numbers?
>
> ;^)

[toc] | [prev] | [next] | [standalone]

#100467

Malcolm McLean <malcolm.mclean5@btinternet.com> writes:

> More programming than C, [...]

In point of fact it has nothing to do with C, and
belongs in another newsgroup.

[toc] | [prev] | [next] | [standalone]

#100552

On 25/12/2016 10:01 AM, Malcolm McLean wrote:
> 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?

Is there a newsgroup in Usenet dedicating to algorithms and mathematics? :)

-- 
   @~@   Remain silent! Drink, Blink, Stretch! Live long and prosper!!
  / v \  Simplicity is Beauty!
/( _ )\ May the Force and farces be with you!
   ^ ^   (x86_64 Ubuntu 9.10)  Linux 2.6.39.3
不借貸! 不詐騙! 不援交! 不打交! 不打劫! 不自殺! 請考慮綜援 (CSSA):
http://www.swd.gov.hk/tc/index/site_pubsvc/page_socsecu/sub_addressesa

[toc] | [prev] | [next] | [standalone]

#100555

On Thursday, December 29, 2016 at 1:09:25 PM UTC, Mr. Man-wai Chang wrote:
> On 25/12/2016 10:01 AM, Malcolm McLean wrote:
> > 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?
> 
> Is there a newsgroup in Usenet dedicating to algorithms and mathematics? :)
> 
comp.programming.

But it's virtually dead.

[toc] | [prev] | [next] | [standalone]

#100577

On 29/12/2016 9:10 PM, Malcolm McLean wrote:
>>
>> Is there a newsgroup in Usenet dedicating to algorithms and mathematics? :)
>>
> comp.programming.
>
> But it's virtually dead.

How about one dedicated to mathematics? I took a look at the list, there 
was only one called "aus.mathematics". And there are some called 
"mathematik".... ;)

-- 
   @~@   Remain silent! Drink, Blink, Stretch! Live long and prosper!!
  / v \  Simplicity is Beauty!
/( _ )\ May the Force and farces be with you!
   ^ ^   (x86_64 Ubuntu 9.10)  Linux 2.6.39.3
不借貸! 不詐騙! 不援交! 不打交! 不打劫! 不自殺! 請考慮綜援 (CSSA):
http://www.swd.gov.hk/tc/index/site_pubsvc/page_socsecu/sub_addressesa

[toc] | [prev] | [next] | [standalone]

#100580

On Thursday, December 29, 2016 at 7:51:22 AM UTC-6, Mr. Man-wai Chang wrote:
> On 29/12/2016 9:10 PM, Malcolm McLean wrote:
> >>
> >> Is there a newsgroup in Usenet dedicating to algorithms and mathematics? :)
> >>
> > comp.programming.
> >
> > But it's virtually dead.
> 
> How about one dedicated to mathematics? I took a look at the list, there 
> was only one called "aus.mathematics". And there are some called 
> "mathematik".... ;)
> 

There are sci.math and aci.logic

[toc] | [prev] | [next] | [standalone]

#100725 — Usenet newsgroups about mathematics

On 29/12/2016 9:56 PM, luser droog wrote:
> There are sci.math and aci.logic
>

Thanks!

-- 
   @~@   Remain silent! Drink, Blink, Stretch! Live long and prosper!!
  / v \  Simplicity is Beauty!
/( _ )\ May the Force and farces be with you!
   ^ ^   (x86_64 Ubuntu 9.10)  Linux 2.6.39.3
不借貸! 不詐騙! 不援交! 不打交! 不打劫! 不自殺! 請考慮綜援 (CSSA):
http://www.swd.gov.hk/tc/index/site_pubsvc/page_socsecu/sub_addressesa

[toc] | [prev] | [next] | [standalone]

#100594

Malcolm McLean <malcolm.mclean5@btinternet.com> writes:

> On Thursday, December 29, 2016 at 1:09:25 PM UTC, Mr. Man-wai Chang wrote:
<snip>
>> Is there a newsgroup in Usenet dedicating to algorithms and mathematics? :)
>> 
> comp.programming.
>
> But it's virtually dead.

  Now, if thou wouldst, when all have giv'n him over,
  From death to life thou might'st him yet recover. [1]

It might take nothing more than a few on-topic posts there...

[1] Michael Drayton, Sonnet LXI.
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#100678

On 12/24/2016 9:01 PM, 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?

Here's the real scoop on Santa:

     https://users.ece.cmu.edu/~andrew5/cute/engineer_santa.txt

-- 
Kenneth Brody

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web