Kerbside Pickup~!

[Illiad]

See attachment

 

Other than (well not) trial and error (but Ariadne's thread), is there any way to plan the most efficient route without or the least amount of overlap to pick up kerbside rubbish from each side of the blocks?

For argument's sake, you can start at any point and the town's landfill will be right where you turn out.

 

 

The edit is in brackets, ~ strike trough is not working properly Tormod.

[Tormod]

Isn't this basically just a version of the travelling salesman problem?

[Tormod]

Or maybe it's more a Hamiltonian path?

[CraigD]

:QuestionM

Does traversing a street pick up the trash from both block sides of it?

Any other conditions, like only being able to pick up on right side?

[Illiad]

both sides.. craigD

and I havent heard of either Tormod~

thx for the link~ though i admit it went over my head

maybe it will become clearer once I reread it a few times~

In the mean time, any stupid-friendly input is welcomed and appreciated

[JMJones0424]

Isn't this basically just a version of the travelling salesman problem?

 

(After some reading at wiki and googling prompted by your posts)

 

No, the traveling salesman problem is concerned with linking all of the vertices. This problem is concerned with traveling along all the sides with minimal repetitions, which makes it a version of the Chinese Postman Problem.

 

I did a google search for solution algorithms, and I think this site might be useful for you Illiad-

 

http://ie454.cankaya.edu.tr/uploads/files/Chp-03%20044-064.pdf

[Illiad]

It's a shame the thanks button is no more

Thx JMJones0424 for the very readable CPP solution~

[Qfwfq]

No, the traveling salesman problem is concerned with linking all of the vertices.

Fully agreed, likewise for the Hamiltonian path and of course repetition of streets can't be avoided.

[Illiad]

So anyway...I ended up with this ( *holds up attached picture*).

Looks unflattering with those sharp U turns (Iliad is aware tat there are other ways to traverse, but came up with this particular way first)

but did i did it right?

[Tormod]

It's a shame the thanks button is no more

Thx JMJones0424 for the very readable CPP solution~

 

But it is! Use the small +/- icons at the bottom right of the post you like!

 

[Illiad]

But it is! Use the small +/- icons at the bottom right of the post you like!

 

lol, thats 1 small button~

[CraigD]

So anyway...I ended up with this ( *holds up attached picture*).

Looks unflattering with those sharp U turns (Iliad is aware tat there are other ways to traverse, but came up with this particular way first)

but did i did it right?

Yes, if you meant to make the graph Eulerian. If you only meant to satisfy the conditions of your problem, which didn’t include starting and stopping at the same and any vertex, you could have done it by adding only 5, not 7, edges to make the graph semi-Eulerian. For example (in crude ASCII art):

A4=B4-C2
|| |  |
D4-E4-F3
|  |  |
G4=H4-I4
|     ||
J3-K4-L4
|  || |
M2-N4-O2

has a 21+5=26 step solution FCBADEBEFIHEHGDGJKLILONKNMJ.

 

I tried an older, simpler technique, Ariadne's thread. Using the decision rule of trying to first visit low-labeled vertexes (eg: A before C), it found a shortest path when started on any non-corner vertex (B D F etc). Started at A and trying high-labeled vertexes first, it found the 21+7=28 step Euclidean path ADGJMNOLKNKJKLIHGHEFIFCBEDEBA. The longest solution it found was 21+12=33 step LIFCBADEBEFEHGDGJKLONKNMJMNOLKJGHI.

 

PS: here’s the little MUMPS program that found all this for me:

k N2 m N2=N s Q="N" f N=0:1 s Q=$q(@Q) q:Q=""  s @(Q_"=0"),N2($qs(Q,2),$qs(Q,1))="" ;XMPAT1(1,0): initialize
x XMPAT1(1,0) s (A,T,P)=+P f  x XMPAT1(1,1) s A=B,P=P_","_B,T=$s(C:$p(T,",",2,$l(T,",")),1:B_","_T) s:'C N=N-1,N(A1,B1)=N(A1,B1)+1 q:'N  ;XMPAT1(1): find
s B="" f  s (B,F)=$o(N2(A,B),D) s:'B B=$p(T,",",2) s A1=$s(A<B:A,1:B),B1=$s(A<B:B,1:A),C=N(A1,B1) q:'F!'C  ;XMPAT1(1,1)

k N s (N(1,2),N(1,4),N(2,3),N(2,5),N(3,6),N(4,5),N(4,7),N(5,6),N(5,8),N(6,9),N(7,8),N(7,10),N(8,9),N(9,12),N(10,11),N(10,13),N(11,12),N(11,14),N(12,15),N(13,14),N(14,15))=0 ;the map
k LP f D=1,-1 f P=1:1:15 x XMPAT1(1) s LP($l(P,","),+P,D)="" ;find every solution

[Illiad]

Wikied it...sorry, I probably meant Ariadne's thread in my OP, and not trial and error after all. It has been edited.

... trial and error approaches a desired solution; Ariadne's thread blindly exhausts the search space completely, finding any and all solutions.

I did not know what my desired solution should be, other than it being the shortest route. Anyway there is more than 1 'shortest route'.

 

Yea, realized that I could have done that too, but it would have made 'no. of times visited' awkward (1.5), or so I thought because I didn't understand what it meant then. 1 visit consist of 1 time 'coming to' and 1 time 'going out'. 0.5 visit is then EITHER 1 time 'coming in' OR 1 time 'going out'. :doh:

 

I tried an older, simpler technique, Ariadne's thread. Using the decision rule of trying to first visit low-labeled vertexes (eg: A before C)

What does this part mean?

isn't C (labeled 2) lower than A (labeled 4)?

Ariadne thread is uhh, as wiki puts it, exhaustive. Surely it's not practical for bigger streets with more junctions.

 

thx for the input =D

[CraigD]

While a good article, the wikipedia article for the thread of Ariadne stresses its general application to the extent that it’s easy to overlook its simple application to a physical maze. In short, it’s a technique that assures only that you’ll traverse every edge of graph, not necessarily that you’ll do it in the fewest steps – in your trash collecting truck example, that all the trash will get picked up, not necessarily as quickly/efficiently as possible.

 

In short (not as short as my code snippet, but easier to read!), you can use the ToA to assure you pick up all the trash on your streets as follows:

The truck trails a cord behind it, attached to its starting point;

Whenever it reaches an intersection, it avoids going down a street where the cord already lies;

If it reaches an intersection where all the streets have the cord, it backtracks (rewinding the cord) until it reaches an uncorded street.

 

My program keeps track of the number of untraveled streets, and stops as soon as the number reaches 0. It always tries first to go north, then west, then east, then south – that’s what I meant by “trying to first visit low-labeled vertexes” – the lowness of the vertex’s A, B, C etc. label, not its number of edges (order).

 

Euler’s graph theorem – that a graph can be traversed with maximum efficiency only if it has 0 or 2 odd-ordered vertexes (I’ve long called it “the 7 bridges of Koenigsberg theorem”) – is a major step in sophistication, a higher order of abstraction and analysis, beyond the ToA – and a significant step more to program. AFAIK, the 7-step algorithm described on page 5 of the Kankaya U Combinatory Analysis course reading JMJones provided is about as terse a one as there is. Step 2-4, finding the minimum length odd vertex pairing, takes on the order of [math]n^{\frac{n}{2}}[/math] computations, so solving for a graph with a large number of odd vertexes appears hard.

 

What surprised me a little was that, for your 15-vertex graph, my simple ToA-based program did find shortest paths for nearly half (6/15 or 7/15) of the starting places.

[Illiad]

ah.. it took me a while, but i finally understand what you are trying to say (about the ToA, anyway)

 

(ToA)....assures only that you’ll traverse every edge of graph,.....Step 2-4, finding the minimum length odd vertex pairing, takes on the order of computations, so solving for a graph with a large number of odd vertexes appears hard.

These two are the essence of your post~

 

“trying to first visit low-labeled vertexes” isn't really important, but you need to give your program something (anything) so it can make decisions, correct?

Since each problem is unique, there is no way around the n^(n/2) computations, correct?

 

the 7 bridges theorem is a fun read..(much more fun than the hamilton path and TPP, both of which I'm still struggling to comprehend)

Didn't know the idea behind Eulerian graphs is so simple..

hmm, so thats what early mathematicians do for fun~

 

When i was small, someone told me if you're stuck in a maze, you can put your hand on either one side of the wall ( make sure your hand is always in contact with the wall) and continue walking, you'll eventually reach either the exit or entry, though you'll practically walk into all the dead ends the maze has.

:lol: