b4 doubt

[jayant]

suppose pizza dude starts from A
follows A L I G N , now does he need to return to A from N or do we stop him at N, this will affect the distance travelled by him and also the route that he needs to take.

[jayant]

also,

suppose we have a direct route from A-B .
will there be a possibility that the there exists routes A-C and C-B such that Distance(A-B) > Distance(A-C) + Distance(C-B)
hence shortest distance from A to B will be via C and not the direct path.

If Distance(A-B) > Distance(A-C) + Distance(C-B) has to be considered then good tours cannot be found in small times.

[stuart]

Originally posted by jayant@Aug 9 2003, 06:54 AM
suppose pizza dude starts from A
follows A L I G N , now does he need to return to A from N or do we stop him at N, this will affect the distance travelled by him and also the route that he needs to take.

if A L I G N was the drop-offs, then you can start and stop anywhere. you do NOT have to end in your chosen start point. For example:
A(start)->I->G->N->L(stop)

[stuart]

Originally posted by jayant@Aug 9 2003, 07:13 AM
also,

suppose we have a direct route from A-B .
will there be a possibility that the there exists routes A-C and C-B such that Distance(A-B) > Distance(A-C) + Distance(C-B)
hence shortest distance from A to B will be via C and not the direct path.

If Distance(A-B) > Distance(A-C) + Distance(C-B) has to be considered then good tours cannot be found in small times.

That's correct direct routes do NOT always mean the shortest route. And the shortest route wins over shortest time (as long as execution time is not exceeded

[jayant]

.
.
.
.

[jayant]

i just noticed:-
in case we have :-
distance{a,b} > distance{a,c} + distance{c,b}

then in our case P!=NP
hence good tours cannot be found in polynomial time. i.e we will require infinite time => cannot be solved.

=> we must have :-
distance{a,b} <= distance{a,c} + distance{c,b}
for all a,b and c such that
a,c,b belong to list of towns

[stuart]

use what ever algorithm you thing will work best with this puzzle. It up to you to select the right balance - i.e. find a algorithm that will beat everyone elses, baring in mind the shortest route is more important than time taken (within the contests limits).
That's the fun of it, trying to figure out when to stop looking for the ultimate solution in the allowed time.